Distributed Topology Control in Wireless SensorNetworks with Asymmetric LinksJilei Liu and Baochun LiDepartment of Electrical and Computer EngineeringUniversity of Toronto{jennie,bli}@eecg.toronto.eduAbstract— Topology control with per-node transmission poweradjustment in wireless sensor networks has been shown to beeffective with respect to prolonging network lifetime via powerconservation and increasing network capacity via better spatialbandwidth reuse. In this work, we consider the problem oftopology control in a network of heterogeneous wireless deviceswith different maximum transmission ranges, where asymmetricwireless links are not uncommon. In such an environment, wepresent a distributed topology control algorithm to calculate theper-node minimum transmission power, so that (1) reachabilitybetween any two nodes is guaranteed to be the same as in theinitial topology; and (2) nodal transmission power is minimizedto cover the least number of surrounding nodes. Analysis andsimulation results demonstrate the correctness and effectivenessof our proposed algorithm.I. INTRODUCTIONWireless sensor networks are formed by a collection ofpower-conscious wireless-capable sensors without the supportof pre-existing infrastructure, possibly by unplanned deploy-ment. Topology control via per-node transmission power ad-justment has been shown to be effective in extending networklifetime and increasing network capacity (due to better spatialreuse of spectrum). The flip side of the coin is, with a reducedtransmission range on each node, basic reachability from onenode to another may be jeopardized. This problem is furtherexacerbated when we consider a network of heterogeneouswireless devices with different maximum transmission ranges,where asymmetric (or uni-directional) wireless links are notuncommon in the topology.There exists considerable previous work addressing thetopology control problem of minimizing nodal transmissionpower, with guarantees of network connectivity. For example,Wattenhofer et al. [1] proposed a fully distributed algorithmthat only relies on directional information between nodes.Ramanathan et al. [2] presented a centralized topology con-trol algorithm, along with a distributed heuristic. It has notdiscussed, however, guarantees on connectivity. Unlike theabove deterministic guarantee of connectivity, Santi et al. [3]analyzed the connectivity of a sensor ad hoc network usinga probabilistic approach in order to find out the minimumtransmission power to be used at all nodes. The lower andupper bound on the probability of network connectivity arederived for certain transmission range assignments. Lloyd etal. [4] continued research towards this direction, with soundtheoretical analysis on the properties of generic topologycontrol protocols in minimizing the maximum power adoptedand the total energy consumed in the network. Rodoplu et al.[5] presented an topology control algorithm that is most similarto our proposal, requiring location information and workingon vicinity topologies on each node in a distributed fashion.With the wealth of results related to topology control, none ofthe previous work has extensive discussions on the problemintroduced by asymmetric (uni-directional) wireless links, andproposed algorithms tailored to this specific scenario.When the existence of asymmetric links is not assumed inorder to simplify the problem to tractable theoretical models,the following two issues are unavoidably introduced. First, ifall links in the original topology are symmetric, it is impossibleto assume the use of different transmission ranges amongnodes. Second, if asymmetric links are allowed to exist inthe finalized topology, the derived minimum-power topologymay become more power-efficient since transmission rangesmay be further reduced.By placing asymmetric wireless links in the scope andspotlight of our work, we design a distributed topology con-trol algorithm that enjoys the following favorable properties:First, the algorithm converges rapidly. For stationary sensornetworks, the minimum power topology is finalized in a singlepass. Second, the algorithm is not complex computationally,while still effective to guarantee the bi-directional multi-hop reachability between nodes in the network. Third, sinceinformation exchange between nodes is limited to the localneighborhood, the algorithm scales well to large networks.The remainder of the paper is organized as follows. Sec. IIdescribes our system model. Our distributed topology controlalgorithm is presented and analyzed in Sec. III and IV. InSec. V, we show the correctness and effectiveness of ouralgorithm with simulation results. We conclude the paper andsummarize its highlights in Sec. VI.II. MODELIn this work, we consider a wireless sensor network as anetwork of heterogeneous sensors, referred to as nodes.Allnodes are arbitrarily deployed in a two-dimensional plane.Each node is equipped with an omni-directional antenna withadjustable transmission power. Since nodes are heterogeneous,they have different maximum transmission powers and radioranges. For node i,weusePito denote its transmission power,Pimaxas its maximum transmission power (or, alternatively,full power), and Pijas the transmission power required fornode i to reach node j. Under the assumption that thetransmission medium is symmetric (and that asymmetric linksare only due to the different ranges), we have Pij= Pji.Since Pimax= Pjmaxfor i = j, in the situation wherePimax≥ Pij>Pjmax, there exists an asymmetric link−→Lijin the network topology since Pji>Pjmax(impossible forj to reach i with its full power). Our work focuses on suchasymmetric links.Due to the existence of asymmetric links, the topologywhere each node transmits with its maximum transmissionpower is naturally a directed graph, referred to as the maximumtopology−→G =(V,−→L ).−→G can be either strongly connected,weakly connected, or disconnected. In a strongly connected−→G,there is a directed, possibly multi-hop, path from any source toany destination. In a weakly connected−→G, there exists pairs ofnodes that only one of them can reach the other via multiplehops. Finally, in a disconnected−→G, their exist pairs of nodesthat can not reach each other.The objective of our distributed topology control algorithmis to derive a minimum-power topology−→Gthat is strongly con-nected, guaranteeing multi-hop reachability from any sourceto any destination in the