Connectivity, Coverage and Placement in Wireless Sensor Networks
SensorsPublished 28 September 2009Open access
Ji Li, Lachlan L. H. Andrew, Chuan Heng Foh, Moshe Zukerman, Hsiao‐Hwa Chen
Citations160
SJR quartileQ1
SJR score0.76
SNIP1.31
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 describes the state of the art in techniques for determining the minimum density and optimal locations of relay nodes and ordinary sensors to ensure connectivity, subject to various degrees of uncertainty in the locations of the nodes.
Abstract
Wireless communication between sensors allows the formation of flexible sensor networks, which can be deployed rapidly over wide or inaccessible areas. However, the need to gather data from all sensors in the network imposes constraints on the distances between sensors. This survey describes the state of the art in techniques for determining the minimum density and optimal locations of relay nodes and ordinary sensors to ensure connectivity, subject to various degrees of uncertainty in the locations of the nodes.
Keywords
Computer ScienceEngineering
Wireless communications: principles and practice
17,534 Citations2002Theodore S. Rappaport
Computer NetworksWireless sensor networks: a survey
17,276 Citations2002Ian F. Akyildiz, Weilian Su +2 more
The concept of sensor networks which has been made viable by the convergence of micro-electro-mechanical systems technology, wireless communications and digital electronics is described.
Energy-efficient communication protocol for wireless microsensor networks
14,115 Citations2005Wendi Heinzelman, Anantha P. Chandrakasan +1 more
Ad-hoc on-demand distance vector routing
10,319 Citations1999Charles E. Perkins, E.M. Royer
An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure and the proposed routing algorithm is quite suitable for a dynamic self starting network, as required by users wishing to utilize ad- hoc networks.
Dynamic Source Routing in Ad Hoc Wireless Networks
8,523 Citations2007David B. Johnson, David A. Maltz
This paper presents a protocol for routing in ad hoc networks that uses dynamic source routing that adapts quickly to routing changes when host movement is frequent, yet requires little or no overhead during periods in which hosts move less frequently.
IEEE Transactions on Information TheoryThe capacity of wireless networks
8,315 Citations2000Piyush Gupta, P. R. Kumar
The broadcast storm problem in a mobile ad hoc network
3,146 Citations1999Sze-Yao Ni, Yu‐Chee Tseng +2 more
This paper proposes several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcast to alleviate the broadcast storm problem, which is identified by showing how serious it is through analyses and simulations.
Proceedings of the IEEESensor networks: Evolution, opportunities, and challenges
3,061 Citations2003Chee-Yee Chong, Sanjeev Kumar
The history of research in sensor networks over the past three decades is traced, including two important programs of the Defense Advanced Research Projects Agency (DARPA) spanning this period: the Distributed Sensor Networks (DSN) and the Sensor Information Technology (SensIT) programs.
Mathematical Proceedings of the Cambridge Philosophical SocietyPercolation processes
2,009 Citations1957Simon Broadbent, J. M. Hammersley
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.
Art gallery theorems and algorithms
1,434 Citations1987Joseph O’Rourke
Proceedings of the National Academy of SciencesRandom graph models of social networks
1,363 Citations2002M. E. J. Newman, Duncan J. Watts +1 more
It is found that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
ExOR
1,354 Citations2005Sanjit Biswas, Robert Morris
ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission, which gives each transmission multiple opportunities to make progress.
IRE Transactions on Communications SystemsOptimal Transmission Ranges for Randomly Distributed Packet Radio Terminals
1,255 Citations1984Hideaki Takagi, Leonard Kleinrock
It is shown that the FM capture phenomenon with slotted ALOHA greatly improves the expected progress over the system without capture due to the more limited area of possibly interfering terminals around the receiver.
On calculating connected dominating set for efficient routing in ad hoc wireless networks
1,230 Citations1999Jie Wu, Hailan Li
This paper proposes a simple and efficient distributed algorithm for calculating connected dominating set in ad-hoc wireless networks, where connections of nodes are determined by their geographical distances.
Birkhäuser Boston eBooksCritical Power for Asymptotic Connectivity in Wireless Networks
1,139 Citations1999Piyush Gupta, P.R. Kumar
It is shown that if n nodes are placed in a disc of unit area in !
APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless
1,134 Citations2002A. Manjeshwar, Dharma P. Agrawal
This paper proposes a hybrid routing protocol (APTEEN) which allows for comprehensive information retrieval and observes that these protocols are observed to outperform existing protocols in terms of energy consumption and longevity of the network.
AlgorithmicaApproximation Algorithms for Connected Dominating Sets
1,126 Citations1998Suvajyoti Guha, Samir Khuller
This work considers the more general problem of finding a connected dominating set of a specified subset of vertices and provides a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs.
Wireless Sensor Networks
1,004 Citations2006K. Sohraby, Daniel Minoli +1 more
IEEE Transactions on ComputersGrid coverage for surveillance and target location in distributed sensor networks
926 Citations2002Krishnendu Chakrabarty, S. S. Iyengar +2 more
It is shown that grid-based sensor placement for single targets provides asymptotically complete location of multiple targets in the grid, and coding-theoretic bounds on the number of sensors are provided and methods for determining their placement in the sensor field are presented.
On the minimum node degree and connectivity of a wireless multihop network
909 Citations2002Christian Bettstetter
This paper derives an analytical expression that enables the determination of the required range r0 that creates, for a given node density ρ, an almost surely k--connected network and investigates two fundamental characteristics of a wireless multi -hop network: its minimum node degree and its k--connectivity.
IEEE PotentialsSensor networks: an overview
867 Citations2003Malik Tubaishat, Sanjay Madria
A sensor network can provide access to information anytime, anywhere by collecting, processing, analyzing and disseminating data, and actively participates in creating a smart environment.
Wireless NetworksThe Number of Neighbors Needed for Connectivity of Wireless Networks
832 Citations2004Feng Xue, P. R. Kumar
It is shown that in a network with n randomly placed nodes, each node should be connected to Θ(log n) nearest neighbors, and it appears that the critical constant may be close to one, but that remains an open problem.
Routing in ad-hoc networks using minimum connected dominating sets
771 Citations2002Bevan Das, V. Bharghavan
This paper uses an approximation to the minimum connected dominating set (MCDS) of the ad-hoc network topology as the virtual backbone, and maintains local copies of the global topology of the network, along with shortest paths between all pairs of nodes.
Routing Information Protocol
765 Citations1988C.L. Hedrick
This document specifies a routing protocol, based on the Routing Information Protocol, for the Simple Internet Protocol (SIP), as defined in [3], and a companion document will define the SNMP MIB objects for SIP-RIP (TBD).
IEEE Journal on Selected Areas in CommunicationsCEDAR: a core-extraction distributed ad hoc routing algorithm
720 Citations1999R. Sivakumar, P. Sinha +1 more
Multipoint relaying for flooding broadcast messages in mobile wireless networks
715 Citations2003Amir Qayyum, Laurent Viennot +1 more
The mechanism of multipoint relays (MPRs) to efficiently flood broadcast messages in mobile wireless networks is discussed and a heuristic to select these MPRs in a mobile wireless environment is proposed, and it is proved that the computation of a multipoint relay set with minimal size is NP-complete.
IEEE Transactions on Information TheoryClosing the Gap in the Capacity of Wireless Networks Via Percolation Theory
678 Citations2007Massimo Franceschetti, Olivier Dousse +2 more
An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics and it is shown that randomly scattered nodes can achieve, with high probability, the same 1/radicn transmission rate of arbitrarily located nodes.
IEEE Transactions on CommunicationsTransmission Range Control in Multihop Packet Radio Networks
673 Citations1986Ting‐Chao Hou, Victor O. K. Li
This paper presents a model for analyzing the performance of transmission strategies in a multihop packet radio network where each station has adjustable transmission radius and shows that the network can achieve better performance by suitably controlling the transmission range.
ACM SIGCOMM Computer Communication ReviewOpportunistic routing in multi-hop wireless networks
672 Citations2004Sanjit Biswas, Robert Morris
Extremely Opportunistic Routing is described, a new unicast routing technique for multi-hop wireless networks that reduces the total number of transmissions by nearly a factor of two over the best possible pre-determined route.
Journal of the Society for Industrial and Applied MathematicsRandom Plane Networks
652 Citations1961E. N. Gilbert
Deploying wireless sensors to achieve both coverage and connectivity
576 Citations2006Xiaole Bai, Santosh Kumar +3 more
This paper proposes an optimal deployment pattern to achieve both full coverage and 2-connectivity, and proves its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius.
Sensor placement for effective coverage and surveillance in distributed sensor networks
564 Citations2004S.S. Dhillon, Krishnendu Chakrabarty
Two algorithms are presented that address coverage optimization under the constraints of imprecise detections and terrain properties and are targeted at average coverage as well as at maximizing the coverage of the most vulnerable grid points.
American Journal of MathematicsThe Number of Circles Covering a Set
543 Citations1939Richard Kershner
Connectivity in ad-hoc and hybrid networks
525 Citations2003Olivier Dousse, Patrick Thiran +1 more
It is found that the introduction of a sparse network of base stations does significantly help in increasing the connectivity, but only when the node density is much larger in one dimension than in the other.
NetworksSimple heuristics for unit disk graphs
494 Citations1995Madhav Marathe, Heinz Breu +3 more
This work presents simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs, including maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set.
Wireless NetworksRelay sensor placement in wireless sensor networks
490 Citations2007Xiuzhen Cheng, Ding‐Zhu Du +2 more
This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected.
AlgorithmicaApproximation Algorithms for Connected Dominating Sets
447 Citations2007Suvajyoti Guha, Samir Khuller
This work focuses on the question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected.
Random Structures and AlgorithmsOnk-connectivity for a geometric random graph
441 Citations1999Mathew D. Penrose
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.
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.
IEEE Transactions on ComputersRelay Node Placement in Wireless Sensor Networks
407 Citations2006Errol L. Lloyd, Guoliang Xue
Message-optimal connected dominating sets in mobile ad hoc networks
405 Citations2002Khaled M. Alzoubi, Peng‐Jun Wan +1 more
This paper proposes the first distributed approximation algorithm to construct a MCDS for the unit-disk-graph with a emph constant approximation ratio, and emph linear time and emphlinear message complexity.
Mathematical Proceedings of the Cambridge Philosophical SocietyPercolation processes
402 Citations1957J. M. Hammersley
Journal of Communications and NetworksOn calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks
370 Citations2002Jie Wu, Fei Dai +2 more
A method of calculating power-aware connected dominating set in ad hoc wireless networks and results show that the proposed approach outperforms several existing approaches in terms of life span of the network.
Computer CommunicationsRelay node placement in large scale wireless sensor networks
337 Citations2005Jian Tang, Bin Hao +1 more
This paper formulate the relay node placement in wireless sensor networks as two optimization problems: (i) Connected Relay Node Single Cover (CRNSC) problem and (ii) 2-Connected Relays Node Double Cover (2CRNDC) problem, and presents two polynomial time approximation algorithms to solve the CRNSC problem.
IEEE Transactions on Signal ProcessingOpportunistic large arrays: cooperative transmission in wireless multihop ad hoc networks to reach far distances
326 Citations2003Anna Scaglione, Y.-W. Peter Hong
The technique proposed in this paper allows efficient flooding of a wireless network with information from a source, which is referred to as the leader, and permits us to transmit reliably to far destinations that the individual nodes are not able to reach without consuming rapidly their own battery resources, even when using multihop links.
IEEE/ACM Transactions on NetworkingImpact of interferences on connectivity in ad hoc networks
322 Citations2005Olivier Dousse, François Baccelli +1 more
It is proved that if /spl gamma/ is nonzero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops.
Information Processing LettersSteiner tree problem with minimum number of Steiner points and bounded edge-length
294 Citations1999Guohui Lin, Guoliang Xue
It is proved that this Steiner tree problem with minimum number of Steiner points and bounded edge-length is NP-complete and a polynomial time approximation algorithm is presented whose worst-case performance ratio is 5.
Localized minimum-energy broadcasting in ad-hoc networks
278 Citations2004Julien Cartigny, David Simplot +1 more
This work describes a new localized protocol where each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes (or, alternatively, geographic position of itself and its neighboring node).
IEEE Transactions on Information TheoryConnectivity properties of a packet radio network model
268 Citations1989Thomas K. Philips, Shivendra S. Panwar +1 more
A model of a packet radio network in which transmitters with range R are distributed according to a two-dimensional Poisson point process with density D is examined and it is shown that pi R/sup 2/D, the expected number of nearest neighbors of a transmitter, must grow logarithmically with the area of the network.
Journal of Communications and NetworksDistributed heuristics for connected dominating sets in wireless ad hoc networks
253 Citations2002Khaled M. Alzoubi, Peng‐Jun Wan +1 more
Two destributed heuristics with constant performance ratios are proposed, which require only single-hop neighborhood knowledge, and a message length of O (1) and O(n log n), respectively.
The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks
248 Citations2003Douglas M. Blough, Mauro Leoncini +2 more
Wireless Sensor Networks
232 Citations2004Raghavendra, C. S, Znati, Taieb +1 more
Journal of Physics A Mathematical and GeneralEfficient measurement of the percolation threshold for fully penetrable discs
225 Citations2000J. Quintanilla, Salvatore Torquato +1 more
A randomized art-gallery algorithm for sensor placement
224 Citations2001Héctor H. González-Baños
A placement strategy to compute a set of “good” locations where visual sensing will be most effective in a workspace, based on a randomized algorithm that solves a variant of the {\em art-gallery problem}.
IEEE/ACM Transactions on NetworkingLifetime Maximization for Connected Target Coverage in Wireless Sensor Networks
218 Citations2008Qun Zhao, Mohan Gurusamy
This paper model the CTC problem as a maximum cover tree (MCT) problem, determines an upper bound on the network lifetime for the MCT problem and develops a (1+w)H(M circ) approximation algorithm to solve it, which shows that the lifetime obtained is close to the upper bound.
Efficient Deployment Algorithms for Ensuring Coverage and Connectivity ofWireless Sensor Networks
214 Citations2006You‐Chiun Wang, Chun-Chi Hu +1 more
This work considers the sensing field as an arbitrary-shaped region possibly with obstacles, and allows an arbitrary relationship between the communication range and sensing range, thus eliminating the constraints of existing results.
IEEE Transactions on Parallel and Distributed SystemsExtended dominating-set-based routing in ad hoc wireless networks with unidirectional links
209 Citations2002Jie Wu
An efficient localized algorithm for determining a dominating and absorbant set of vertices (mobile hosts) is given and this set can be easily updated when the network topology changes dynamically, extending dominating-set-based routing to networks with unidirectional links.
Computing connected dominated sets with multipoint relays
198 Citations2005Cédric Adjih, Philippe Jacquet +1 more
This work proposes a scheme for computing an optimized connected dominating set from multipoint relays that allows to efficiently broadcast packets without the last hop information with performances close to multipoint relay flooding.
Connectivity vs capacity in dense ad hoc networks
190 Citations2004Olivier Dousse, Patrick Thiran
It is found that the properties of the network strongly depend on the shape of the attenuation function, and bounds on the percolation domain for large node densities are obtained, which show that either the network becomes disconnected, or the available rate per node decreases.
IEEE Communications LettersOn the connectivity in finite ad hoc networks
190 Citations2002Madhav P. Desai, D. Manjunath
This letter obtains the exact formula for the probability that the network is connected and extends this result to find bounds for the connectivity in a two-dimensional network in [0, z]/sup 2/.
IEEE Communications LettersA near-optimal sensor placement algorithm to achieve complete coverage-discrimination in sensor networks
189 Citations2005F.Y.S. Lin, Po‐Lin Chiu
A robust and scalable algorithm that can find the optimal sensor placement under the minimum cost limitation for small sensor fields and can also find a placement with minimum distance error for large sensor fields under the cost limitation is developed.
Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks
180 Citations2008Xiaole Bai, Dong Xuan +3 more
This paper proposes a new deployment-polygon based methodology, and proves their optimality among regular patterns when Rc/Rs ≥ 1, and conjecture that their patterns are globally optimal to achieve full coverage and three-connectivity, and full Coverage and five-Connectivity, under all ranges of R c/Rs.
Mobile Networks and ApplicationsConnectivity in Wireless Ad-hoc Networks with a Log-normal Radio Model
166 Citations2006Ramin Hekmat, Piet Van Mieghem
With simulations, an equation found for the calculation of the giant component size in wireless ad-hoc networks, that takes into account the level of radio signal power variations is shown to be a good measure for “connectivity”.
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms
162 Citations2007W. Zhang, Ganglin Xue +1 more
This paper studies four related fault-tolerant relay node placement problems and presents a polynomial time O(1)-approximation algorithm with a small approximation ratio for each of them.
Asymptotic critical transmission radius and critical neighbor number for <i>k</i> -connectivity in wireless ad hoc networks
152 Citations2004Peng‐Jun Wan, Chih‐Wei Yi
This paper provides a precise asymptotic distribution of the critical transmission radius for k-connectivity and an improve asymPTotic almost sure upper bound on the critical neighbor number for k.connectivity in a wireless ad hoc network whose nodes are uniformly an independently distribute in a unit-area square or disk.
Low-coordination topologies for redundancy in sensor networks
152 Citations2005Rajagopal Iyengar, Koushik Kar +1 more
This paper proposes and studies distributed, low-coordination node wakeup schemes to efficiently construct multiple independent (node-disjoint) sensor network topologies to achieve good fault tolerance, and proposes and evaluates different distributed, random and pattern-based wakeup policies for sensor nodes to construct connected-covered topologies.
IEEE Transactions on Mobile ComputingThe critical transmitting range for connectivity in mobile ad hoc networks
152 Citations2005Paolo Santi
The results can be used to improve the accuracy of RWP mobile ad hoc networks simulation, which is commonly used to evaluate the performance of ad hoc networking protocols, and provide a better understanding of the behavior of a fundamental network parameter in the presence of mobility.
Wireless sensor placement for reliable and efficient data collection
147 Citations2003Edoardo Biagioni, Galen H. Sasaki
A variety of regular deployment topologies are presented, including circular and star deployments as well as deployments in square, triangular, and hexagonal grids.
Journal of Research of the National Institute of Standards and TechnologyDistribution of link distances in a wireless network
140 Citations2001L.E. Miller
The probability distribution is found for the link distance between two randomly positioned mobile radios in a wireless network for two representative deployment scenarios: (1) the mobile locations are uniformly distributed over a rectangular area and (2) the x and y coordinates of theMobile locations have Gaussian distributions.
Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation
140 Citations2004Bin Hao, Jian Tang +1 more
A polynomial time approximation algorithm is presented and it is proved the worst-case performance given by the algorithm is bounded within O(D log n) times of the size of an optimal solution, where n is the number of sensor nodes in the network, D is the diameter of the network formed by a sufficient set of possible positions for relay nodes.
Cooperative systemsA New Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks
140 Citations2004Sergiy Butenko, Xiuzhen Cheng +2 more
This chapter proposes a new efficient heuristic algorithm for the minimum connected dominating set problem that reduces the size of the CDS by excluding some vertices using a greedy criterion and discusses a distributed version of this algorithm.
Journal of Global OptimizationApproximations for Steiner Trees with Minimum Number of Steiner Points
138 Citations2000Dong‐Hui Chen, Ding‐Zhu Du +4 more
IEEE Transactions on ComputersExtended multipoint relays to determine connected dominating sets in MANETs
136 Citations2006Jie Wu, Wei Lou +1 more
This paper provides several extensions of the source-independent MPR to generate a smaller CDS using 3-hop neighborhood information to cover each node's 2-hop neighbor set and shows that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR.
The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs.
135 Citations2003Christos Gkantsidis, Milena Mihail +1 more
This paper introduces a novel heuristic to speed up the simulation of the Markov chain, and uses metrics reminiscent of quality of service and congestion to evaluate the output graphs.
IEEE Transactions on CommunicationsOptimum transmission ranges in multihop packet radio networks in the presence of fading
131 Citations1995Michele Zorzi, Silvano Pupolin
It is shown that the optimal probability of transmission of each user is independent of the system model and is p/sub o//spl sime/0.271, which is proportional to the square root of /spl chi/.
Constrained Relay Node Placement in Wireless Sensor Networks to Meet Connectivity and Survivability Requirements
127 Citations2008Satyajayant Misra, S. D. Hong +2 more
This paper studies constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations, and presents a framework of polynomial time O(1) -approximation algorithms with small approximation ratios.
The Annals of Applied ProbabilityCovering algorithms, continuum percolation and the geometry of wireless networks
123 Citations2003Lorna Booth, Jehoshua Bruck +2 more
It is shown how a simple scaling operation can change the percolation properties of the model, leading to the almost sure existence of an unbounded connected component for large values of lambda, for any covering algorithm.
Wireless NetworksA new approach to the design and analysis of peer‐to‐peer mobile networks
123 Citations1999Imrich Chlamtac, András Faragó
This paper introduces a new model and methodological approach for dealing with the probabilistic nature of mobile networks based on the theory of random graphs, and shows that it is possible to construct a randomized distributed algorithm which provides connectivity with high probability, requiring exponentially fewer connections than the number of connections needed for an algorithm with a worst case deterministic guarantee.
SensorsNovel Deployment Schemes for Mobile Sensor Networks
122 Citations2007Jiming Chen, Shijian Li +1 more
Improved VFA is improved to overcome the factors of the convergence, the boundary in Region Of Interest, effective distance of acting force and useless moving, etc, and an expression of exponential function for the relationship of virtual force is proposed to converge rapidly.
Relay Placement for Higher Order Connectivity in Wireless Sensor Networks
121 Citations2006Abhishek Kashyap, Samir Khuller +1 more
This paper develops O(1)-approximation algorithms that find close to optimal solutions in time O((kn) for achieving k-edge connectivity of n nodes and proves that if the sensors are uniformly and identically distributed in a unit square, the expected number of relay nodes required goes to zero as the number of sensors goes to infinity.
Cooperative systemsCooperative Control: Models, Applications and Algorithms
119 Citations2003Sergiy Butenko, Robert Murphey +1 more
This work focuses on the construction of Virtual Backbone for Ad Hoc Wireless Network and the search for the Universal Concept of Complexity and a General Optimality Condition of Cooperative Agents.
Distributed low-cost backbone formation for wireless ad hoc networks
106 Citations2005Yu Wang, WeiZhao Wang +1 more
This paper proposes an efficient distributed method to construct a weighted sparse backbone with low cost and proves that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth or the network maximum node degree is bounded.
Performance study of node placement in sensor networks
106 Citations2004Mika Ishizuka, Masaki Aida
Evaluated the tolerance against both random failure and battery exhaustion from the viewpoint of stochastic node placement in sensor networks.
Cooperative systemsRecent Developments in Cooperative Control and Optimization
106 Citations2004Sergiy Butenko, Robert Murphey +1 more
IEEE Transactions on Information TheoryOn the connectivity of radio networks
103 Citations1991P. Piret
It is conjectured that the critical ranges of the two-dimensional problems are also different, and the author presents results to substantiate this conjecture.
On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment
100 Citations2003Christian Bettstetter
This paper investigates the connectivity of wireless multihop networks with uniformly randomly distributed nodes and analyzes the required transmission range that creates, for a given node density, an almost surely k-connected topology.
BioinformaticsExploring biological network structure using exponential random graph models
93 Citations2007Zachary M. Saul, Vladimir Filkov
Cooperative systemsOn the Construction of Virtual Backbone for Ad Hoc Wireless Network
88 Citations2003Sergiy Butenko, Xiuzhen Cheng +2 more
In this study, the virtual backbone is approximated by a minimum connected dominating set (MCDS) and a distributed algorithm which computes a small CDS is proposed which performs well in simulation results and theoretical analysis.
Connectivity of wireless multihop networks in a shadow fading environment
88 Citations2003Christian Bettstetter, Christian Hartmann
A tight lower bound for the minimum node density that is necessary to obtain an almost surely connected subnetwork on a bounded area of given size is given.
Proceedings of the National Academy of SciencesCOMBINATORIAL PROBLEMS IN THE THEORY OF GRAPHS. II
78 Citations1956Gillian Ford, Robert Z. Norman +1 more
IEEE Communications Surveys & TutorialsA survey of multipoint relay based broadcast schemes in wireless ad hoc networks
77 Citations2006Liang Ou, Y. Ahmet Şekercioğlu +1 more
A comprehensive survey of MPR-based broadcast schemes is presented, classified into three categories based on their objectives, and the evaluation of their performances is provided in light of their costs.
A closed form network connectivity formula one-dimensional MANETs
75 Citations2004Chuan Heng Foh, Bu‐Sung Lee
A closed form network connectivity formula for a one-dimensional mobile ad hoc network (MANET) is developed that derives the probability that a MANET is fully connected given a certain number of nodes randomly and uniformly placed along a path between a source and destination pair.
…