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.
Connectivity was the first problem studied from a worst-case perspective in the SINR model. In a seminal paper, Moscibroda and Wattenhofer @cite_7 formalized the problem and proposed an algorithm that connects arbitrary set of @math points in @math slots. This was improved to @math @cite_14 , @math @cite_19 , and recently to @math @cite_4 . All these works deploy centralized algorithms. No non-trivial lower bound is known. Somewhat orthogonally, a large body of work exists on randomly deployed wireless networks, starting with the influential work by Gupta and Kumar @cite_8 . Work in this setting for connectivity includes @cite_21 , which studied the probability of there existing a path between two nodes in a randomly deployed network. In @cite_16 , minimum energy connectivity structures is studied for randomly deployed networks, but interference is essentially ignored.
@cite_14 @cite_4 @cite_7 @cite_8 @cite_21 @cite_19 @cite_16
2148868861 2953216592 2098480450 2137775453 2085356235 2106388288 2170469173
To date, topology control in wireless ad hoc and sensor networks--the study of how to compute from the given communication network a subgraph with certain beneficial properties .has been considered as a static problem only; the time required to actually schedule the links of a computed topology without message collision was generally ignored. In this paper we analyze topology control in the context of the physical Signal-to-Interference-plus-Noise-Ratio (SINR) model, focusing on the question of how and how fast the links of a resulting topology can actually be realized over time.For this purpose, we define and study a generalized version of the SINR model and obtain theoretical upper bounds on the scheduling complexity of arbitrary topologies in wireless networks. Specifically, we prove that even in worst-case networks, if the signals are transmitted with correctly assigned transmission power levels, the number of time slots required to successfully schedule all links of an arbitrary topology is proportional to the squared logarithm of the number of network nodes times a previously defined static interference measure Interestingly, although originally considered without explicit accounting for signal collision in the SINR model, this static interference measure plays an important role in the analysis of link scheduling with physical link interference. Our result thus bridges the gap between static graph-based interference models and the physical SINR model. Based on these results, we also show that when it comes to scheduling, requiring the communication links to be symmetric may imply significantly higher costs as opposed to topologies allowing unidirectional links. Given @math wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in @math slots, improving on the previous best bound of @math due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of @math on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of @math slots for connectivity. This rules out a recent claim of a @math bound using oblivious power. On the other hand, using our result we show that @math slots suffice, where @math is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with @math latency is possible, improving upon the previous best known latency of @math . We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and @math -edge connected structures. We define and study the scheduling complexity in wireless networks, which expresses the theoretically achievable efficiency of MAC layer protocols. Given a set of communication requests in arbitrary networks, the scheduling complexity describes the amount of time required to successfully schedule all requests. The most basic and important network structure in wireless networks being connectivity, we study the scheduling complexity of connectivity, i.e., the minimal amount of time required until a connected structure can be scheduled. In this paper, we prove that the scheduling complexity of connectivity grows only polylogarithmically in the number of nodes. Specifically, we present a novel scheduling algorithm that successfully schedules a strongly connected set of links in time O(logn) even in arbitrary worst-case networks. On the other hand, we prove that standard MAC layer or scheduling protocols can perform much worse. Particularly, any protocol that either employs uniform or linear (a node’s transmit power is proportional to the minimum power required to reach its intended receiver) power assignment has a Ω(n) scheduling complexity in the worst case, even for simple communication requests. In contrast, our polylogarithmic scheduling algorithm allows many concurrent transmission by using an explicitly formulated non-linear power assignment scheme. Our results show that even in large-scale worst-case networks, there is no theoretical scalability problem when it comes to scheduling transmission requests, thus giving an interesting complement to the more pessimistic bounds for the capacity in wireless networks. All results are based on the physical model of communication, which takes into account that the signal-tonoise plus interference ratio (SINR) at a receiver must be above a certain threshold if the transmission is to be received correctly. When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput spl lambda (n) obtainable by each node for a randomly chosen destination is spl Theta (W spl radic (nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is spl Theta (W spl radic An) bit-meters per second. Thus even under optimal circumstances, the throughput is only spl Theta (W spl radic n) bits per second for each node for a destination nonvanishingly far away. Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions. Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity. Splitting the channel into several subchannels does not change any of the results. Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance. This paper presents a framework for the calculation of stochastic connectivity properties of wireless multihop networks. Assuming that n nodes, each node with transmission range r0, are distributed according to some spatial probability density function, we study the level of connectivity of the resulting network topology from three viewpoints. First, we analyze the number of neighbors of a given node. Second, we study the probability that there is a communication path between two given nodes. Third, we investigate the probability that the entire network is connected, i.e. each node can communicate with every other node via a multihop path. For the last-mentioned issue, we compute a tight approximation for the critical (r0 ,n )pairs that are required to keep the network connected with a probability close to one. In fact, the problem is solved for the general case of a k-connected network, accounting for the robustness against node failures. These issues are studied for uniformly distributed nodes (with and without ‘border effects’), Gaussian distributed nodes, and nodes that move according to the commonly used random waypoint mobility model. The results are of practical value for the design and simulation of wireless sensor and mobile ad hoc networks. The key application scenario of wireless sensor networks is data gathering: sensor nodes transmit data, possibly in a multi-hop fashion, to an information sink. The performance of sensor networks is thus characterized by the rate at which information can be aggregated to the sink. In this paper, we derive the first scaling laws describing the achievable rate in worst-case, i.e. arbitrarily deployed, sensor networks. We show that in the physical model of wireless communication and for a large number of practically important functions, a sustainable rate of Theta(1 log2 n) can be achieved in every network, even when nodes are positioned in a worst-case manner. In contrast, we show that the best possible rate in the protocol model is Theta(1 n), which establishes an exponential gap between these two standard models of wireless communication. Furthermore, our worst-case capacity result almost matches the rate of Theta(1 log n) that can be achieved in randomly deployed networks. The high rate is made possible by employing non-linear power assignment at nodes and by exploiting SINR-effects. Finally, our algorithm also improves the best known bounds on the scheduling complexity in wireless networks. We describe a distributed position-based network protocol optimized for minimum energy consumption in mobile wireless networks that support peer-to-peer communications. Given any number of randomly deployed nodes over an area, we illustrate that a simple local optimization scheme executed at each node guarantees strong connectivity of the entire network and attains the global minimum energy solution for stationary networks. Due to its localized nature, this protocol proves to be self-reconfiguring and stays close to the minimum energy solution when applied to mobile networks. Simulation results are used to verify the performance of the protocol.