We consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. Combinatorially, this means a) finding a set of links that form a strongly connected spanning graph on a set of @math points in the plane, and b) scheduling it efficiently in the SINR model of interference. The nodes must converge on a solution in a distributed manner, having no means of communication beyond the sole wireless channel. We give distributed connectivity algorithms that run in time @math , where @math is the ratio between the longest and shortest distances among nodes. Given that algorithm without prior knowledge of the instance are essentially limited to using uniform power, this is close to best possible. Our primary aim, however, is to find efficient structures, measured in the number of slots used in the final schedule of the links. Our main result is algorithms that match the efficiency of centralized solutions. Specifically, the networks can be scheduled in @math slots using (arbitrary) power control, and in @math slots using a simple oblivious power scheme. Additionally, the networks have the desirable properties that the latency of a converge-cast and of any node-to-node communication is optimal @math time.
Distributed connectivity of wireless networks has also been the subject of research. In @cite_15 , connectivity in mobile networks was studied from a graph-theoretic perspective with no explicit interference model. Indeed, connectivity maintenance problem has been well studied in control theory and robotics @cite_15 @cite_6 @cite_22 , but with different underlying assumptions, typically without the use of the SINR interference model. Sensor connectivity has also been studied @cite_27 without reference to any particular interference model. In @cite_17 , a heuristic was proposed for connectivity maintenance in multi-hop wireless networks. A more rigorous study was done in @cite_9 but with the assumption of an underlying MAC layer that resolves interference problems.
@cite_22 @cite_9 @cite_6 @cite_27 @cite_15 @cite_17
2141327408 2148570604 2121221698 2076865372 2166188160 2142928312
A distributed control law that guarantees connectivity maintenance in a network of multiple mobile agents is presented. The control law, which lets the agents perform formation manoeuvres, respects sensor limitations by allowing each agent to only take into account agents within its sensing radius. In contrast to previous approaches to the problem, the proposed control law does not attain infinite values whenever an edge of the communication graph tends to be lost. This is achieved via the use of decentralised navigation functions, which are bounded potential fields. The navigation functions are defined to take into account the connectivity maintenance objective. The authors first treat the case of connectivity maintenance for a static communication graph and then extend the result to the case of dynamic graphs. The results are illustrated on a formation control problem. The topology of wireless multihop ad hoc networks can be controlled by varying the transmission power of each node. We propose a simple distributed algorithm where each node makes local decisions about its transmission power and these local decisions collectively guarantee global connectivity. Specifically, based on the directional information, a node grows it transmission power until it finds a neighbor node in every direction. The resulting network topology increases the network lifetime by reducing the transmission power and reduces traffic interference by having low node degrees. Moreover, we show that the routes in the multihop network are efficient in power consumption. We give an approximation scheme in which the power consumption of each route can be made arbitrarily close to the optimal by carefully choosing the parameters. Simulation results demonstrate significant performance improvements. This paper presents a solution to the limited information rendezvous problem over dynamic interaction graphs. In particular, we show how we, by adding appropriate weights to the edges in the graphs, can guarantee that the graph stays connected. In previous work on graph-based coordination, connectedness have been assumed, and this paper thus shows how to overcome this limitation even when the graphs are subject to dynamic changes. Wireless sensor networks have attracted a lot of attention recently. Such environments may consist of many inexpensive nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes through wireless links. For a sensor network to operate successfully, sensors must maintain both sensing coverage and network connectivity. This issue has been studied in [2003] and Zhang and Hou [2004a], both of which reach a similar conclusion that coverage can imply connectivity as long as sensors' communication ranges are no less than twice their sensing ranges. In this article, without relying on this strong assumption, we investigate the issue from a different angle and develop several necessary and sufficient conditions for ensuring coverage and connectivity of a sensor network. Hence, the results significantly generalize the results in [2003] and Zhang and Hou [2004a]. This work is also a significant extension of our earlier work [Huang and Tseng 2003; 2004], which addresses how to determine the level of coverage of a given sensor network but does not consider the network connectivity issue. Our work is the first work allowing an arbitrary relationship between sensing ranges and communication distances of sensor nodes. We develop decentralized solutions for determining, or even adjusting, the levels of coverage and connectivity of a given network. Adjusting levels of coverage and connectivity is necessary when sensors are overly deployed, and we approach this problem by putting sensors to sleep mode and tuning their transmission powers. This results in prolonged network lifetime. Control of mobile networks raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In particular, in applications involving mobile sensor networks and multi-agent systems, a great new challenge is the development of distributed motion algorithms that guarantee connectivity of the overall network. In this paper, we address this challenge using a novel control decomposition. First, motion control is performed in the continuous state space, where nearest neighbor potential fields are used to maintain existing links in the network. Second, distributed coordination protocols in the discrete graph space ensure connectivity of the switching network topology. Coordination is based on locally updated estimates of the abstract network topology by every agent as well as distributed auctions that enable tie breaking whenever simultaneous link deletions may violate connectivity. Integration of the overall system results in a distributed, multi- agent, hybrid system for which we show that, under certain secondary objectives on the agents and the assumption that the initial network is connected, the resulting motion always satisfies connectivity of the network. Our approach can also account for communication time delays in the network as well as collision avoidance, while its efficiency and scalability properties are illustrated in nontrivial computer simulations. We consider the problem of adjusting the transmit powers of nodes in a multihop wireless network (also called an ad hoc network) to create a desired topology. We formulate it as a constrained optimization problem with two constraints-connectivity and biconnectivity, and one optimization objective-maximum power used. We present two centralized algorithms for use in static networks, and prove their optimality. For mobile networks, we present two distributed heuristics that adaptively adjust node transmit powers in response to topological changes and attempt to maintain a connected topology using minimum power. We analyze the throughput, delay, and power consumption of our algorithms using a prototype software implementation, an emulation of a power-controllable radio, and a detailed channel model. Our results show that the performance of multihop wireless networks in practice can be substantially increased with topology control.