homogeneous wireless nodes with uniform transmission ranges. In this paper, we propose two localized topology control algorithms for heterogeneous wireless multi-hop networks with nonuniform transmission ranges: Directed Relative Neighborhood Graph (DRNG) and Directed Local Minimum Spanning Tree (DLMST). In both algorithms, each node selects a set of neighhon hased on the locally collected information. We prove that (1) the topologies derived under DRNG and DLMST preserve the network connectivity; (2) the out degree of any node in the resulting topolo= by DLMST is hounded; while the out degree of ncdes in the topology hy DRNG is not hounded; and (3) the topologies generated hy DRNG and DLMST preserve the network hi-directionality. Energy efficiency 111 and network capacity are perhaps two of the most important issues in wireless ad hoc networks and sensor networks. Topology control algorithms have been proposed to maintain network connectivity while reducing energy consumption and improving network capacity. The key idea to topology control is that. instead of transmitting using the maximal power. nodes in a wireless multi-hop network collaboratively determine their transmission power and define the network topology by forming the proper neighbor relation under certain criteria. By enabling wireless nodes to use adequate transmission power (which is usually much smaller than the maximal Urnsmission power). topology control can not only save energy and prolong network Metime. but also improve spatial reuse (and hence the network capacity) [ 2 ] and mitigate the MAC-level medium contention 131. Several topology conuol algorithms [3]- [10] have been proposed to create power-efficient network topology in wireless multi-hop networks with limited mobility (a summary is given in Section 111). However. most of them assume homogeneous wireless nodes with uniform transmission ranges (except 141). The assumption of homogeneous nodes does not always hold in practice since even devices of the same type may have slightly different maximal transmission power. There also exist heterogeneous wireless networks in which devices have drama[ically different capab es. for instance. the communication network in the Future Combat System which involves wireless devices on soldiers. vehicles and UAVs. As will be exemplified in Section 111. most existing algorithms cannot be directly applied to heterogeneous wireless multi-hop networks in which the transmission range ofeach-node may be different. To the best of our knowledge. this paper is the tirst effort to address the connectivity and biilirectionality issue in the heterogeneous wireless networks. In this paper, we propose two localized topology control algorithms for heterogeneous wireless multi-hop networks with non-uniform transmission ranges: Directed Relative Neighborhood Graph (DRNG) and Directed Local Minimum Spanning Tree (DLMST). In both algorithms. the topology is constructed by'having each node build its neighbor set and adjust its transmission power based on the locally collected information. We are able to prove that (1) the topology derived under both DRNG and DLMST preserves network connectivity. i.e.. if the original topology generated by having every node use its maximal transmission power is strongly connected. then the topologies generated by both DRNG and DLMST are also strongly connectcd; (2) the out degree of any node in the topology by DLMST is bounded. while the out degree of nodes in the topology by DRNG may be unbounded: and (3) the topology generated by DRNG and DLMST preserves network hi-directionality. i.e.. if the original topology by having every node use its maximal transmission power is hi-directional. then the topology generated by either DRNG or DLMST is also hidirectional after some simple operations. Simulation results indicate that compared with the other known topology control algorithms that can be applied to heterogeneous networks. DRNG and DLMST have smaller average node degree (both logical and physical) and smaller average link length. The former reduces the MAC-level contention. while the latter implies a small transmission power needed to maintain connectivity. The rest of the paper is organized as follows. In Section II_ we give the network model. In Section 111. we summarize previous work on topology control. and give examples to show why existing algorithms cannot be directly applied to heterogeneous networks. Following that. we present both the DRNG and DLMST algorithms in Section IV. and prove several of their useful properties in Section V. Finally. we evaluate the performance of the proposed algorithms in Section VI. and conclude the paper in Section VII.
Similarly, two localized algorithms for heterogeneous wireless networks were proposed in REF to preserve a bi-connected network topology.
Topology control in heterogeneous wireless networks: problems and solutions
IEEE INFOCOM 2004
IEEE INFOCOM 2004
Computer Science