Jie Gao

1415 Computer Science Building

Stony Brook University

Stony Brook, NY 11794

631-632-9169

369 CEWIT Building

631-632-5987

jgao at cs dot sunysb dot edu

Surveys and Chapters

1. Jie Gao, Leonidas J. Guibas, Geometric Algorithms for Sensor Networks, invited to Philosophical Transactions of the Royal Society A, vol. 370, no. 1958, 27-51, Janurary 2012.

2. Jie Gao, Geometric Routing in Wireless Sensor Networks, invited to Guide to Wireless Sensor Networks, Springer-Verlag, 2009.
   

Social Network Analysis

1. Xiaomeng Ban, Jie Gao, Arnout van de Rijt, Navigation in Real-World Complex Networks through Embedding in Latent Spaces, Workshop on Algorithm Engineering and Experiments (ALENEX10), 138-148, January, 2010. Bibtex. This is an experimental paper. We take a number of real world complex networks, both social and non-social, and examine their embedding in Euclidean and hyperbolic spaces and the performance of greedy routing with the embedded coordinates. Surprisingly, even with standard techniques such as multi-dimensional scaling in constant dimensional spaces, greedy routing not only delivers a majority set of packets but also uses paths of length of roughly 6 hops at most.

2. Akshay Patil, Juan Liu, Jie Gao, Predicting Group Stability in Online Social Networks, Proceedings of the 22nd International World Wide Web Conference (WWW'13), May 13-17, 2013.

3. Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, Jie Gao, Complex Contagion and The Weakness of Long Ties in Social Networks: Revisited, Proceedings of the 14th ACM Conference on Electronic Commerce (EC'13), June 16-20, 2013. Information, diseases or viruses could spread fast in a social network due to the small world property. These are "simple contagions" as one can be infected through a single contact. Other behavior changes such as technology innovation and immigration are "complex contagions" which requires multiple simultaneous contacts. We show that complex contagion is very slow (in polynomial # rounds) for Newman-Watts model but is still fast (in polylogarithmic # rounds) in Kleinberg's small world model and Kleinberg's hierarchical model. 

Differential Geometry and Applications in Sensor Network Routing

1. Rik Sarkar, Xiaotian Yin, Jie Gao, Feng Luo, Xianfeng David Gu, Greedy Routing with Guaranteed Delivery Using Ricci Flows, Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN'09), 121-132, April, 2009. Bibtex. Here is a set of slides from a recent talk. We use Ricci flow to convert a sensor field with holes such that all the holes are circular --- greedy forwarding will never get stuck.

2. Wei Zeng, Rik Sarkar, Feng Luo, Xianfeng David Gu, Jie Gao, Resilient Routing for Sensor Networks using Hyperbolic Embedding of Universal Covering Space, Proc. of the 29th Annual IEEE Conference on Computer Communications (INFOCOM'10), 1694-1702, March, 2010. Bibtex. Also presented at the 19th Fall Workshop on Computational Geometry, Nov 13-14, 2009. We show an embedding of a sensor network to many isometric patches in the hyperbolic spaces that are nicely glued along the boundaries, s.t. the paths connecting a source in one patch to different images in other patches represent paths in the original network with different homotopy types (i.e., getting around holes in different ways). Greedy routing can be used to route in the embedded space to find paths of a given homotopy type.  

3. Rik Sarkar, Wei Zeng, Jie Gao, Xianfeng David Gu, Covering Space for In-Network Sensor Data Storage, Proc. of the 9th International Symposium on Information Processing in Sensor Networks (IPSN'10), 232-243, April, 2010. Bibtex. Here is a set of slides from a recent talk. This is a followup paper of our IPSN'09 paper. We first use Ricci flow to deform any sensor network such that the holes are all circular. Then we reflect the network against each circular hole (a special Mobius transformation) recursively to `fill up' the holes. The resulted covering space has applications in improving the load balancing performance of data-centric storage schemes (GHT, double rulings, etc) since the network shape is now regulated to be a circular, regular shape.

4. Rik Sarkar, Jie Gao, Differential Forms for Target Tracking and Aggregate Queries in Distributed Networks, Proc. of the 16th Annual International Conference on Mobile Computing and Networking (MobiCom'10), 377-388, September, 2010. Bibtex. Journal version accepted to IEEE/ACM Transactions on Networking, 2012. Slides (pptx, pdf). In this paper we maintain differential 1-form on a planar graph for target tracking and queries. Each edge is given a weight such that the integration along any cycle gives the number of targets within the cycle. When a target moves from one face to an adjacent face, we simply subtract the weight of the target from the weight of the edge just crossed. Thus target motion only trigger local updates to the differential forms. 

5. Xiaokang Yu, Xiaomeng Ban, Rik Sarkar, Wei Zeng, Xianfeng David Gu, Jie Gao, Spherical Representation and Polyhedron Routing for Load Balancing in Wireless Sensor Networks, Proc. of the 30th Annual IEEE Conference on Computer Communications (INFOCOM'11), 612-615, mini-conference, March, 2011. Also presented at 20th Fall Workshop on Computational Geometry, Oct 29-30, 2010. Bibtex. Slides (pptx).  In this paper we compute by using circle packing the Thurston embedding of a 3-connected planar graph as a skeleton graph of a convex polytope in 3D. This embedding is useful as it not only supports greedy routing with guaranteed delivery but also has nice load balancing properties -- as compared in the case of geographical routing that overloads the center of the network. . 

6. Ruirui Jiang, Xiaomeng Ban, Mayank Goswami, Wei Zeng, Jie Gao, Xianfeng David Gu, Exploration of Path Space using Sensor Network Geometry, Proc. of the 10th International Symposium on Information Processing in Sensor Networks (IPSN'11), 49-60, April, 2011. Bibtex. Slides (pptx). This builts on top of our IPSN'09 paper and exploits the freedom of the Mobius transformation for (1) multipath routing (2) fast recovery of link failures. In our IPSN'09 paper we show how to embed a network into a circular domain such that all holes are circular. Such circular domains are not unique and differ by a Mobius transformation. By choosing a proper Mobius transformation we get multiple paths (with guaranteed delivery) and we can switch to a different path when encountering a link failure.

7. Xiaokang Yu, Xiaotian Yin, Wei Han, Jie Gao, Xianfeng David Gu, Scalable Routing in 3D High Genus Sensor Networks Using Graph Embedding, Proc. of the 31st Annual IEEE Conference on Computer Communications (INFOCOM'12), mini-conference, 2681-2685, March, 2012. Slides (pptx). We use graph embedding technique to embed any graph onto a high genus surface. Then we cut the surfaces into "pants" on which hyperbolic routing can guarantee delivery. This method works for any arbitrary graph and is particularly interesting for low-density, topologically complex 3D sensor networks. 

8. Xiaomeng Ban, Mayank Goswami, Wei Zeng, Xianfeng David Gu, Jie Gao, Topology Dependent Space Filling Curves for Sensor Networks and Applications, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. By deforming a network into a regular shape (a disk, a torus or a torus with slits), one can generate a continuous, dense curve that covers the domain. This curve can be used as a "space filling curve" suitable for any network tasks requiring linearization.

9. Siming Li, Wei Zeng, Dengpan Zhou, Xianfeng David Gu, Jie Gao, Compact Conformal Map for Greedy Routing in Wireless Mobile Sensor Networks, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. This is to improve the IPSN'09 paper in the setting of a mobile network. The idea is to pre-compute a conformal map of the geometric domain on which mobile sensors are deployed. The map is encoded by a small number of parameters and pre-loaded to the mobile sensors so that each can compute its new coordinates directly under movement.  

10. Rui Shi, Mayank Goswami, Jie Gao, Xianfeng David Gu, Is Random Walk Truly Memoryless - Traffic Analysis and Source Location Privacy Under Random Walks, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. Random walk is often adopted to provide source location privacy, since a random walk longer than hitting time converges to a random stationary distribution. We show that simply using random walk by itself may not protect location privacy at all -- by monitoring the how packets following random walk hit the boundary of a sensor network on a domain, we can infer the source location with good accuracy by integrating the harmonic measure along the boundary. 

Landmark-based Routing

1. Qing Fang, Jie Gao, Leonidas J. Guibas, Vin de Silva, Li Zhang, GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05), volume 1, pages 339-350, March, 2005. Slides. Bibtex. We select landmarks in a sensor network and build the combinatorial Delaunay graph to capture the network holes. The distance vector to the landmarks are used to implement greedy point to point routing. 

2. An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark Selection and Greedy Landmark-descent Routing for Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 661-669, May, 2007. Bibtex. Using distances to landmarks, it is easier to implement "pulling" from the landmarks rather than "pushing" away by the landmarks. This paper shows how to use "pulling forces" only to get bounded stretch greedy routing.

3. Jie Gao, Leonidas J. Guibas, Steve Y. Oudot, Yue Wang, Geodesic Delaunay Triangulation and Witness Complex in the Plane, Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 571-580, January, 2008. Bibtex. Journal version under the title, Geodesic Delaunay Triangulations in Bounded Planar Domains, invited to a special issue of ACM Transactions on Algorithms (TALG), 6(4), 2010. This paper provides the theoretical foundations of "landmark Delaunay complex" used in routing (INFOCOM'05 paper by Q. Fang et.al) and localization (INFOCOM'08 paper by S. Lederer et. al). That is, how should landmarks be selected such that the landmark Delaunay complex captures the precise topological features of the underlying environment.

Other Geometric Routing Methods

1. Jehoshua Bruck, Jie Gao, Anxiao Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom’05), 88-102, August, 2005. Journal version invited to Wireless Networks (WINET) special issue from MobiCom'05. Slides. Bibtex. Use medial axis to build a routing map for routing around holes. 

2. Rik Sarkar, Xianjin Zhu, Jie Gao, Spatial Distributions in Routing Table Design for Sensor Networks, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), Mini-conference, 2766-2770, April, 2009. Bibtex. Also presented at 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Here is a talk I gave on this and the IPSN'07 paper on spatial gossip. Journal version under title "Distributed and Compact Routing Using Spatial Distributions in Wireless Sensor Networks" accepted to ACM Transactions on Sensor Networks, 9(4), Nov, 2013. We store in routing tables the paths selected with a geometric spatial distribution such that the average routing table size is \sqrt{n} and 1+\eps routing path can be achieved with local greedy routing.

3. Jie Gao, Dengpan Zhou, Resilient and Low Stretch Routing Through Embedding into Tree Metrics, Proc. of the 12th Algorithms and Data Structures Symposium (WADS'11), 438-450, August, 2011. We show that by using two hierarchical separated trees (HSTs), one can approximate a metric with constant growth rate with constant distortion. This is applied for low stretch and resilient routing.

Load Balanced Routing

1. Jie Gao, Li Zhang, Load Balanced Short Path Routing in Wireless Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 1099-1108, March, 2004. Journal version in IEEE Transactions on Parallel and Distributed Systems, Special Issue on Localized Communication, vol. 17, no. 4, 377-388, April, 2006. Slides. Bibtex. When wireless nodes are located inside a narrow strip or on a line, we can find a local greedy algorithm that delivers packets with a constant stretch such that the maximum load of any node is within a constant factor of the optimal.

2. Jie Gao, Li Zhang, Tradeoffs between Stretch Factor and Load Balancing Ratio in Routing on Growth Restricted Graphs, Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), 189-196, July, 2004. Journal version in IEEE Transactions on Parallel and Distributed Systems, 20(2), 171-179, 2009. Slides. Bibtex. In a graph where the growth rate is bounded (the number of nodes within k hops grows as a polynomial of k), the stretch factor and load balancing ratio are inversely proportional. A tight bound is proved. 

Network Localization

1. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Localization and Routing in Sensor Networks by Local Angle Information, Proc. of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), 181-192, May, 2005. Journal version in ACM Transactions on Sensor Networks, 5(1), 1-31, February, 2009. Slides. Bibtex. It is NP-hard to embed a unit disk graph even when the angles between adjacent edges are given. But, using only local angle information one can extract the restricted Delaunay graph, which is a planar graph including all Delaunay edges of length no more than 1.  

2. Amitabh Basu, Jie Gao, Joseph S.B. Mitchell, Girishkumar Sabhnani, Distributed Localization by Noisy Distance and Angle Information, Proc. of the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'06), 262-273, May, 2006. Bibtex. This paper proves various versions of localization problem are NP-hard when noisy angle and distance information is given. It also uses a distributed algorithm that iteratively refines the feasible region of each node to find its possible locations. 

3. Anand Prabhu Subramanian, Pralhad Deshpande, Jie Gao, Samir R. Das, Drive-by Localization of Roadside WiFi Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 718-725, May, 2008. Bibtex. Use directional antennas mounted on moving vehicles to localize WiFi access points.
   

4. Sol Lederer, Yue Wang, Jie Gao, Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 789-797, May, 2008. Bibtex. Slides. Journal version in ACM Transactions on Sensor Networks, 5(4), November, 2009. Bibtex. The main challenge in anchor-free localization is to avoid flip ambiguities -- a part of the network folds on top of the other. We extract a combinatorial Delaunay complex on landmarks selected in a sensor network to help network localization. The insight is that two adjacent Delaunay triangles must be embedded side-by-side. An algorithm is developed to construct a globally rigid Delaunay complex for localization of a large sensor network with complex shape. 

5. Yue Wang, Sol Lederer, Jie Gao, Connectivity-based Sensor Network Localization with Incremental Delaunay Refinement Method, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), 2401-2409, April, 2009. Also presented at 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Bibtex. Slides. This is a follow-up paper of our INFOCOM'08 paper. We developed an incremental method to select landmarks such that the resulted combinatorial Delaunay complex is rigid and well represents the sensor field shape, which is then used for anchor-free connectivity-based localization of the network.

In-network Processing, Storage and Query

1. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, Fractionally Cascaded Information in a Sensor Network, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 311-319, April, 2004. Bibtex.  The information from a sensor is stored in a cascaded manner allowing users to answer range queries efficiently. We show almost tight upper and lower bound for range queries. 

2. Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark-Based Information Storage and Retrieval in Sensor Networks, The 25th Conference of the IEEE Communication Society (INFOCOM'06), 1-12, April, 2006. Bibtex. "Double rulings" refer to schemes where information is stored along a curve such that a user query along another curve will intersect the storage curve and retrieve the data. This paper combines the double ruling with a landmark hierarchy to provide efficient in-network data query. 

3. Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 286-297, September, 2006. Bibtex. Slides. Journal version appeared in IEEE/ACM Transaction on Networking, 17(6), 1902-1915, December, 2009. Bibtex. We hash data to circles in a sensor network such that retrieval along other circles are guaranteed to find the data with cost O(d) with d as the true distance between data source and query node. 

4. Rik Sarkar, Xianjin Zhu, Jie Gao, Hierarchical Spatial Gossip for Multi-Resolution Representations in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 420-429, April, 2007. Bibtex, Slides. Journal version accepted to ACM Transactions on Sensor Networks, 8(1), Feb, 2012. We use spatial gossip to build, for each sensor v, the aggregation of all the sensors within 2^i hop from v, for i=0, ..., log n. The total communication cost for all the sensors to build their respective multi-resolution aggregates is near linear.

5. Jie Gao, Leonidas J. Guibas, John Hershberger, Nikola Milosavljevic, Sparse Data Aggregation in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 430-439, April, 2007. Bibtex. Locally detected events sparsely spread in the network autonomously discover each other in a distributed fashion and form an aggregation structure that can be used to compute cumulants, moments, or other statistical summaries on the events. The total communication cost is O(log n) |MST|.

6. Huijia Lin, Maohua Lu, Nikola Milosavljevic, Jie Gao, Leonidas J. Guibas, Composable Information Gradients in Wireless Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'08), 121-132, April, 2008. Bibtex. We propose to build a potential field with harmonic functions at data sources such that greedy routing with the potential is guaranteed to reach a source.

7. Dengpan Zhou, Jie Gao, Opportunistic Processing and Query of Motion Trajectories in Wireless Sensor Networks, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), 1197-1205, April, 2009. Bibtex.  

8. Jie Gao, Leonidas J. Guibas, Nikola Milosavljevic, Dengpan Zhou, Distributed Resource Management and Matching in Sensor Networks, Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN'09), 97-108, April, 2009. Bibtex. Slides. We study the problem of distributed matching of events (e.g., cars) with resources (e.g., empty parking spots) detected by a sensor network with the objective of minimizing the sum of distances of the matching. The key is to extract a hierarchical separated tree (HST) and apply greedy matching algorithm on the tree (match the closest pair, remove them and continue). 

9. Dengpan Zhou, Jie Gao, Maintaining Approximate Minimum Steiner Tree and k-center for Mobile Agents in a Sensor Network, Proc. of the 29th Annual IEEE Conference on Computer Communications (INFOCOM'10), 511-515, mini-conference, March, 2010. Bibtex. Also presented at the 19th Fall Workshop on Computational Geometry, Nov 13-14, 2009. We use the hierarchical well-separated tree (as shown in our previous paper in IPSN'09) to maintain a O(log n) approximate minimum Steiner tree & k-center for mobile agents such that each hop move for an agent incurs O(log n) message cost.

10. Michele Albano, Jie Gao, In-Network Coding for Resilient Sensor Data Storage and Efficient Data Mule Collection, Proc. of the 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSOR'10), 105-117, July, 2010. Bibtex. Slides. This paper uses spatial gossip for constructing random linear codes in sensor networks such that a data mule can simply pick up enough codewords from any nodes to reconstruct the original sensor data. The total communication cost for constructing the codewords is O(n polylogn).

11. Navid Azimi, Himanshu Gupta, Xiaoxiao Hou, Jie Gao, Data Preservation Under Spatial Failures in Sensor Networks, Proc. of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'10), 171-180, September, 2010. Bibtex.

Topological Methods for Sensor Networks

1. Qing Fang, Jie Gao, Leonidas J. Guibas, Locating and Bypassing Routing Holes in Sensor Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 2458-2468, March 2004. Journal version in MONET Special Issue on Foundations of Mobile Computing, 11, 187-200, 2006. Bibtex. Detect network holes locally with sensor location information.

2. Yue Wang, Jie Gao, Joseph S.B. Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 122-133, September, 2006. Bibtex, Slides. Detect network boundaries by detecting cut locus -- the collection of points with multiple shortest paths to a single source.   

3. Xianjin Zhu, Rik Sarkar, Jie Gao, Shape Segmentation and Applications in Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 1838-1846, May, 2007. Bibtex. Slides. Also presented in the 16th Fall Workshop on Computational and Combinatorial Geometry, Nov, 10-11, 2006. Journal version under the title Segmenting a Sensor Field: Algorithms and Applications in Network Design appeared in ACM Transactions on Sensor Networks, 5(2), 1-32, 2009. Bibtex. We segment a sensor field with irregular shape into nice near convex pieces such that data processing tasks can be done in each piece resulting in better overall performance. 

4. Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, Joseph S. B. Mitchell, Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 1175-1183, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007. A distributed algorithm to build a contour tree in a sensor network and the applications in iso-contour queries.

5. Xianjin Zhu, Rik Sarkar, Jie Gao, Joseph S. B. Mitchell, Light-weight Contour Tracking in Wireless Sensor Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 960-967, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007. 

6. Xianjin Zhu, Rik Sarkar, Jie Gao, Topological Data Processing for Distributed Sensor Networks with Morse-Smale Decomposition, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), Mini-conference, 2911-2915, April, 2009. Bibtex.

Sensor Network Security

1. Sol Lederer, Jie Gao, Radu Sion, Collaborative Location Certification for Sensor Networks, invited to Proc. of the 2008 IEEE Sarnoff Symposium. April, 2008. Under the title "On Certifying Location claims in Sensor Networks" presented at the Conference of Applied Cryptography and Network Security (ACNS), industrial track, 2007. Journal version published in ACM Transactions on Sensor Networks (TOSN), 6(4), 2010. Bibtex. In a hostile environment, an adversary may capture a node and use it to report bogus events to the base station representing a fake location. We propose a collaborative scheme in which the sensor nodes certify location claims.

2. Ritesh Maheshwari, Jie Gao, Samir R. Das, Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 107-115, May, 2007. Bibtex. Poster presented at IEEE SECON 2006, Sep, 2006. A wormhole attack causes far away nodes to appear to be directly connected, thus messing up the routing schemes. We observe that the fake wormhole links will violate packing properties in standard unit disk graph like models. Thus by detecting such forbidden structures one can identify and isolate bogus wormhole links using only local information.

3. Xiaomeng Ban, Rik Sarkar, Jie Gao, Local Connectivity Tests to Identify Wormholes in Wireless Networks, Proc. of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'11), 13:1-13:11, May, 2011. We defined a wormhole as adding a bipartite subgraph to the legitimate  network topology. We also present a local, distributed algorithm to detect the bipartite subgraph structure and show that the tests are sufficient and necessary.  

4. Khuong Vu, Rong Zheng, Jie Gao, Efficient Algorithms for K-Anonymous Location Privacy in Participatory Sensing, Proc. of the 31st Annual IEEE Conference on Computer Communications (INFOCOM'12), 2399-2407, March, 2012.

Other Networking Papers

Geometric Spanners, Well-Separated Pair Decompositions

1. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Geometric Spanner for Routing in Mobile Networks, Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'01), 45-55, October 2001. Journal version in IEEE Journal on Selected Areas in Communications Wireless Ad Hoc Networks (J-SAC), 23(1), 174-185, January, 2005. Bibtex. Use restricted Delaunay graph (RDG) in GPSR. RDG is a planar graph that contains all the Delaunay edges of length no greater than 1. 

2. Jie Gao, Li Zhang, Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications, Proc. the 35th ACM Symposium on Theory of Computing (STOC'03), 483-492, June, 2003. Journal version appeared in SIAM J. Computing, 35(1), 151-169, 2005. Slides. Bibtex.  We also wrote an encyclopedia entry for this topic. For a unit disk graph, one can find a well-separated pair decomposition with O(nlogn) pairs. This is useful to speed up graph problems on UDGs.

3. Jie Gao, Leonidas J. Guibas, An Nguyen, Distributed Proximity Maintenance in Ad Hoc Mobile Networks, Proc. of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS'05), 4-19, June, 2005. Here is the full version. Slides. Bibtex. Maintain a distributed spanner among mobile nodes.

4. Jie Gao, Dengpan Zhou, The Emergence of Sparse Spanners and Greedy Well Separated Pair Decomposition, Proc. of the the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'10), 50-61, June, 2010. Bibtex. Slides. Also presented at the 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Journal version published in Journal of Computational Geometry, 3(1), 1-19, 2012.  We show the following algorithm outputs a 1+e spanner with O(n/e^d) edges for n points in R^d: each node p builds an edge pq if and only if there is no edge p'q' with p',q' within distance O(e)|pq| from p,q  respectively. If we select an arbitrary pair not yet covered and put a `dumb-bell' around it as a well-separated pair. Repeat this greedy algorithm until all pairs of points are covered, we get a well-separated pair decomposition with size O(n).

Clustering Lines

Other Unclassified Work

1. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Weighted Bloom Filter, 2006 IEEE International Symposium on Information Theory (ISIT'06), July, 2006. Bibtex. A Bloom filter when the data entries have different popularity measures.