A Survey on Topology issues in Wireless Sensor Network.
Published 1 January 2006
Mo Li, Baijian Yang
Citations75
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This survey paper provides a full view of the studies in topology control in Wireless Sensor Networks by summarizing previous achievements and analyzing existed problems, and point out possible research directions for future work.
Abstract
Abstract: Topology issues have received more and more attentions in Wireless Sensor Networks (WSN). While WSN applications are normally optimized by the given underlying network topology, another trend is to optimize WSN by means of topology control. A number of approaches have been invested in this area, such as topology directed routing, cooperating schemes, sensor coverage based topology control and network connectivity based topology control. Most of the schemes have proven to be able to provide a better network monitoring and communication performance with prolonged system lifetime. In this survey paper, we provide a full view of the studies in this area. By summarizing previous achievements and analyzing existed problems, we also point out possible research directions for future work Keywords: Wireless sensor networks, Topology,
Keywords
Computer ScienceEngineering
IEEE Communications MagazineA survey on sensor networks
13,670 Citations2002Ian F. Akyildiz, Weilian Su +2 more
GPSR
7,032 Citations2000Brad Karp, H. T. Kung
Greedy Perimeter Stateless Routing is presented, a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions and its scalability on densely deployed wireless networks is demonstrated.
ACM Computing SurveysVoronoi diagrams—a survey of a fundamental geometric data structure
4,317 Citations1991Franz Aurenhammer
IEEE Personal CommunicationsGPS-less low-cost outdoor localization for very small devices
3,572 Citations2000Nirupama Bulusu, John Heidemann +1 more
This work reviews localization techniques and evaluates the effectiveness of a very simple connectivity metric method for localization in outdoor environments that makes use of the inherent RF communications capabilities of these devices.
Versatile low power media access for wireless sensor networks
3,356 Citations2004Joseph Polastre, Jason Hill +1 more
B-MAC's flexibility results in better packet delivery rates, throughput, latency, and energy consumption than S-MAC, and the need for flexible protocols to effectively realize energy efficient sensor network applications is illustrated.
Ad Hoc NetworksSecure routing in wireless sensor networks: attacks and countermeasures
2,939 Citations2003Chris Karlof, David Wagner
Geography-informed energy conservation for Ad Hoc routing
2,825 Citations2001Ya Xu, John Heidemann +1 more
A geographical adaptive fidelity algorithm that reduces energy consumption in ad hoc wireless networks by identifying nodes that are equivalent from a routing perspective and then turning off unnecessary nodes, keeping a constant level of routing fidelity.
IEEE/ACM Transactions on NetworkingMedium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks
2,737 Citations2004W. Ye, John Heidemann +1 more
This paper proposes S-MAC, a medium access control (MAC) protocol designed for wireless sensor networks that enables low-duty-cycle operation in a multihop network and reveals fundamental tradeoffs on energy, latency and throughput.
An adaptive energy-efficient MAC protocol for wireless sensor networks
2,664 Citations2003Tijs van Dam, Koen Langendoen
T-MAC, a contention-based Medium Access Control protocol for wireless sensor networks, introduces an adaptive duty cycle in a novel way: by dynamically ending the active part of it to handle load variations in time and location.
ComputerDenial of service in sensor networks
1,711 Citations2002A.D. Wood, John A. Stankovic
To identify denial-of-service vulnerabilities, the authors analyzed two effective sensor network protocols that did not initially consider security and demonstrate that consideration of security at design time is the best way to ensure successful network deployment.
IEEE Journal on Selected Areas in CommunicationsMinimum energy mobile wireless networks
1,690 Citations1999Volkan Rodoplu, T.H. Meng
Auerbach Publications eBooksMaintaining Sensing Coverage and Connectivity in Large Sensor Networks
1,506 Citations2005Honghai Zhang, Jennifer C. Hou
A decentralized density control algorithm, Optimal Geographical Density Control (OGDC), is devised for density control in large scale sensor networks and can maintain coverage as well as connectivity, regardless of the relationship between the radio range and the sensing range.
Wireless NetworksLANDMARC: Indoor Location Sensing Using Active RFID
1,426 Citations2004Lionel M. Ni, Yunhao Liu +2 more
This paper presents LANDMARC, a location sensing prototype system that uses Radio Frequency Identification (RFID) technology for locating objects inside buildings and demonstrates that active RFID is a viable and cost-effective candidate for indoor location sensing.
Span
1,369 Citations2001Benjie Chen, Kyle Jamieson +2 more
A randomized algorithm where coordinators rotate with time is given, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology.
Geographical and Energy Aware Routing: a recursive data dissemination protocol for wireless sensor networks
1,346 Citations2002Yan Yu, Ramesh Govindan +1 more
The proposed Geographic and Energy Aware Routing (GEAR) algorithm uses energy aware neighbor selection to route a packet towards the target region and Recursive Geographic Forwarding or Restricted flooding algorithm to disseminate the packet inside the destina-
Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem
1,330 Citations2002Andrew Howard, Maja J. Matarić +1 more
This paper presents a potential-field-based approach to deployment of a mobile sensor network, where the fields are constructed such that each node is repelled by both obstacles and by other nodes, thereby forcing the network to spread itself throughout the environment.
Integrated coverage and connectivity configuration in wireless sensor networks
1,269 Citations2003Xiaorui Wang, Guoliang Xing +4 more
The design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of Coverage Configuration Protocol (CCP) and integrate SPAN to provide both coverage and connectivity guarantees are presented.
Wireless NetworksRouting with Guaranteed Delivery in Ad Hoc Wireless Networks
1,203 Citations2001Prosenjit Bose, Pat Morin +2 more
A coverage-preserving node scheduling scheme for large wireless sensor networks
1,129 Citations2002Di Tian, Nicolas D. Georganas
A node-scheduling scheme, which can reduce system overall energy consumption, therefore increasing system lifetime, by turning off some redundant nodes, and guarantees that the original sensing coverage is maintained after turning off redundant nodes.
PEAS: a robust energy conserving protocol for long-lived sensor networks
890 Citations2004Fan Ye, G. Zhong +3 more
A robust energy-conserving protocol that can build long-lived, resilient sensor networks using a very large number of small sensors with short battery lifetime, PEAS can extend a sensor network's functioning time in linear proportion to the deployed sensor population.
Compass routing on geometric networks.
848 Citations1999Evangelos Kranakis, Harvinder Singh +1 more
A close look at maps of numerous cities around the world, show that the previous way to explore a new, and unknown city will in general yield walks that will be close to the optimal ones to travel from one location to another.
The coverage problem in a wireless sensor network
811 Citations2003Chi-Fu Huang, Yu‐Chee Tseng
This paper forms the coverage problem as a decision problem, whose goal is to determine whether every point in the service area of the sensor network is covered by at least k sensors, where k is a given parameter.
Power Control in Ad-Hoc Networks : Theory, Architecture Algorithm and Implementation of the COMPOW protocol
710 Citations2002Swetha Narayanaswamy
The solution is shown to simultaneously satisfy the three objectives of maximizing the traffic carrying capacity of the entire network, extending battery life through providing low power routes, and reducing the contention at the MAC layer.
Geometric ad-hoc routing
662 Citations2003Fabian Kühn, Rogert Wattenhofer +2 more
A new geometric routing algorithm is proposed which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal and the formerly necessary assumption that the distance between network nodes may not fall below a constant value is dropped.
Movement-assisted sensor deployment
547 Citations2005Guiling Wang, Guohong Cao +1 more
This work designs and evaluates distributed self-deployment protocols for mobile sensors, VEC, VEC, VOR, and minimax based on the principle of moving sensors from densely deployed areas to sparsely deployed areas, which can provide high coverage within a short deploying time and limited movement.
Differentiated surveillance for sensor networks
508 Citations2003Ting Yan, Tian He +1 more
This paper proposes a differentiated surveillance service for sensor networks based on an adaptable energy-efficient sensing coverage protocol that outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and asmuch as 130% increase in the half-life of the network.
Locating and bypassing routing holes in sensor networks
469 Citations2005Qing Fang, Jie Gao +1 more
A distributed algorithm is described, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes, and it is shown that these hole-surrounding routes can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.
Topology control for wireless sensor networks
440 Citations2003Jianping Pan, Y. Thomas Hou +3 more
This paper focuses on the topology control process for ANs and BSs, which constitute the upper tier of a two-tiered WSN, and proposes approaches to maximize the topological network lifetime of the WSN by arranging BS location and inter-AN relaying optimally.
Asynchronous wakeup for ad hoc networks
437 Citations2003Rong Zheng, Jennifer C. Hou +1 more
Simulation studies indicate that the proposed asynchronous wakeup protocol is quite effective under various traffic characteristics and loads: energy saving can be as high as 70%, while the packet delivery ratio is comparable to that without power management.
Theoretical Computer SciencePower consumption in packet radio networks
424 Citations2000Lefteris M. Kirousis, Evangelos Kranakis +2 more
For points in three dimensions it is shown that the problem of deciding whether a complete range assignment of a given cost exists, is NP-hard and an O(n 2 ) time approximation algorithm is given which provides a completerange assignment with cost within a factor of two of the minimum.
IEEE Transactions on Mobile ComputingThe critical transmitting range for connectivity in sparse wireless ad hoc networks
417 Citations2003Paolo Santi, Douglas M. Blough
The critical transmitting range for connectivity in wireless ad hoc networks is analyzed and insight into how mobility affects connectivity is yielded and useful trade offs between communication capability and energy consumption are revealed.
Discrete mathematics and its applicationsVoronoi Diagrams and Delaunay Triangulations
393 Citations2004Steven Fortune
The Voronoi diagrams and Delaunay triangulations have been rediscovered or applied in many areas of math ematics and the natural sciences and are central topics in computational geometry with hundreds of papers discussing algorithms and extensions.
AnySee: Peer-to-Peer Live Streaming
362 Citations2006Xiaofei Liao, Hai Jin +3 more
Statistics prove that this design is scalable and robust, and it is believed that the wide deployment of AnySee will soon benefit many more Internet users as it outperforms previous schemes in resource utilization and the QoS of streaming services.
JAM: a jammed-area mapping service for sensor networks
349 Citations2004A.D. Wood, John A. Stankovic +1 more
A mapping protocol for nodes that surround a jammer which allows network applications to reason about the region as an entity, rather than as a collection of broken links and congested nodes is described.
Topology management for sensor networks
317 Citations2002Curt Schurgers, Vlasios Tsiatsis +2 more
A hybrid scheme, which takes advantage of both setup latency and network density to increase the nodes' lifetime, and integrates efficiently with existing approaches that leverage the fact that nearby nodes can be equivalent for traffic forwarding.
Power-saving protocols for IEEE 802.11-based multi-hop ad hoc networks
308 Citations2003Yu‐Chee Tseng, Chih‐Shun Hsu +1 more
This paper considers the design of power-saving protocols for mobile ad hoc networks (MANETs) that allow mobile hosts to switch to a low-power sleep mode and proposes three power management protocols, namely dominating-awake-interval, periodically-fully-aw Wake-Interval, and quorum-based protocols, which are directly applicable to IEEE 802.11-based MANETs.
Sending messages to mobile users in disconnected ad-hoc wireless networks
306 Citations2000Qun Li, Daniela Rus
This paper develops algorithms that minimize the trajectory modifications under two different assumptions: (a) the movements of all the nodes in the system are known and (b) the Moves of the hosts in the System are not known.
A bidding protocol for deploying mobile sensors
253 Citations2004Guiling Wang, Guohong Cao +1 more
A bidding protocol to assist the movement of mobile sensors in which mobile sensors can move from dense areas to sparse areas to improve the overall coverage.
Telecommunication SystemsCoverage, Exploration and Deployment by a Mobile Robot and Communication Network
208 Citations2004Maxim A. Batalin, Gaurav S. Sukhatme
An efficient minimalist algorithm which assumes that global information is not available is presented which deploys a network of radio beacons which assists the robot in coverage and also used by the robot for navigation.
Contour map matching for event detection in sensor networks
205 Citations2006Wenwei Xue, Qiong Luo +2 more
This paper proposes simple SQL extensions to allow users to specify common types of events as patterns in contour maps and study energy-efficient techniques of contour map construction and maintenance for the authors' pattern-based event detection.
Location-aware topology matching in P2P systems
182 Citations2005Yunhao Liu, Xiaomei Liu +3 more
A location-aware topology matching (LTM) technique, an algorithm of building an efficient overlay by disconnecting low productive connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries is proposed.
IEEE Transactions on Parallel and Distributed SystemsLocation awareness in unstructured peer-to-peer systems
170 Citations2005Yunhao Liu, Li Xiao +3 more
A location-aware topology matching (LTM) technique is proposed, which builds an efficient overlay by disconnecting slow connections and choosing physically closer nodes as logical neighbors while still retaining the search scope and reducing response time for queries.
Lecture notes in computer scienceHardness Results for the Power Range Assignment Problem in Packet Radio Networks
164 Citations1999Andrea Clementi, Paolo Penna +1 more
The minimum range assignment problem consists of assigning transmission ranges to the stations of a multi-hop packet radio network so as to minimize the total power consumption provided that the transmission range assigned to the station ensures the strong connectivity of the network.
Routing performance in the presence of unidirectional links in multihop wireless networks
160 Citations2002Mahesh K. Marina, Samir R. Das
The results indicate that the marginal benefit of using a high-overhead routing protocol to utilize unidirectional links is questionable and all three techniques for AODV improve performance by avoiding unid Directional links the ReversePathSearch technique being the most effective.
On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks
118 Citations2002Douglas M. Blough, Mauro Leoncini +2 more
A constrained version of the range assignment problem for wireless ad hoc networks, where the value the node transmitting ranges must be assigned in such a way that the resulting communication graph is strongly connected and the energy cost is minimum, indicates that weak symmetry is a desirable property of therange assignment.
Symmetric Connectivity with Minimum Power Consumption in Radio Networks
118 Citations2002Gruiă Cälinescu, Ion Măndoiu +1 more
This work studies the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that enough power is provided to the node to ensure that the network is connected.
A distributed approach to solving overlay mismatching problem
102 Citations2004Y. Liu, Z. Zhuang +2 more
This work proposes adaptive connection establishment (ACE), an algorithm of building an overlay multicast tree among each source node and the peers within a certain diameter from the source peer, and further optimizing the neighbor connections that are not on the tree, while retaining the search scope.
An intelligent deployment and clustering algorithm for a distributed mobile sensor network
73 Citations2004Nojeong Heo, Pramod K. Varshney
This paper proposes an intelligent energy-efficient deployment algorithm for cluster-based WSN by a synergistic combination of cluster structuring and a peer-to-peer deployment scheme and is shown to exhibit excellent performance.
Distributed caching and adaptive search in multilayer P2P networks
65 Citations2004C. Wang, Li Xiao +2 more
The simulation study shows that, with the help of the index caching and search space division, the DiCAS protocol can significantly reduce the network search traffic in unstructured P2P systems without degrading query success rate.
Optimizing overlay topology by reducing cut vertices
60 Citations2006Xiaomei Liu, Li Xiao +2 more
A distributed mechanism, CAM, is proposed, which efficiently detects the cut vertices before they fail and neutralizes them into normal overlay nodes with slight overhead so that the possibility of network decomposition is minimized after they fail.
Lecture notes in computer scienceA Coverage-Preserving Density Control Algorithm for Wireless Sensor Networks
52 Citations2004Jie Jiang, Wenhua Dou
Experimental results show that the proposed decentralized and localized density control algorithm outperforms the PEAS algorithm and the sponsor area based algorithm with respect to the number of working sensors needed, thus longer system lifetime can be obtained, while preserving completely the sensing coverage of the original network.