Unformatted text preview:

Clustering by Power Control in Ad Hoc NetworksVikas Kawadia and P. R. KumarDepartment of Electrical and Computer Engineering, and Coordinated Science Laboratory,University of Illinois at Urbana-Champaign, 1308 West Main St. Urbana, IL-61801.E-mail:{kawadia,prkumar}@uiuc.eduAbstract—In earlier work [1], it was shown that when nodes areuniformly distributed, then, asymptotically as the numberof nodes is increased, a common transmit power level is al-most optimal with respect to the traffic carrying capacityof the network. In [2] this observation was exploited, anda network layer protocol for power control was developedwhich ensured convergence to the lowest common powerlevel which ensured connectivity. In this paper, we con-sider the problem of power control for situations which fallshort of the asymptotic regime where nodes may be non-homogeneously dispersed in space. In such situations, oneseeks to employ per packet power control depending on thesource and destination of the packet. We address the prob-lem of clustering that results and provide three solutionsfor joint routing and clustering by power control for ad hocnetworks. The first protocol, Clusterpow provides a mech-anism for implementing QoS a la Diffserv where power istraded for latency. The second, Tunnelled Clusterpow, al-lows a finer optimization by using encapsulation. The last,MINPOW, whose basic idea is not new, provides an optimalrouting solution with respect to transmit power, but doesnot readily allow tuning of packet latencies. Our contri-bution includes a clean implementation of MINPOW at thenetwork layer without any physical layer support. We es-tablish that all three protocols are loop free, while also il-lustrating how a slightly different approach could lead topackets getting into infinite loops. We provide the softwarearchitectural framework of our implementation as a net-work layer protocol. The architecture works with any rout-ing protocol. Details of the implementation in Linux arealso provided.I. INTRODUCTIONThe power control problem is to choose the transmitpower level for every packet in a wireless ad hoc network.The per packet choice is to be guided by several consider-ations. The choice of transmit power, and thus the rangeeffect the traffic carrying capacity of the network. In [1]This material is based upon work partially supported by the US-ARO under Contracts DAAD19-00-1-0466 and DAAD 19-01010-465,DARPA under Contracts F33615-01-C-1905 and N00014-01-1-0576,ONR unser Contract N00014-99-1-0696, and AFOSR under ContractAf-DC-5-36128.(a) Homogeneous spatialdispersion of nodes(b) Nodes non-homogeneously dispersedFig. 1. Homogeneous vs clustered networksit is shown that, generally, after taking into considerationthe additional relaying burden of using small hops ver-sus the interference caused by long hops, it is optimal toreduce the transmit power level, if one wants to increasethe traffic carrying capacity of the entire network. Addi-tionally, the choice of power level directly affects batterylife. Moreover, there is an indirect affect since routing isalso affected by the ranges of the transmitters, which de-pend on the transmit power levels. In [2] it was shownthat for the commonly used propagation path loss atten-uation models, low power levels are commensurate withpower optimal routing. This was done by showing thatthe latter necessarily results in planar graphs of power op-timal routes, with only nearby nodes exchanging packets.As noted, power control directly impacts routing and thuscannot be considered in isolation. A further factor to beconsidered is that power control affects packet end-to-endlatency. With small power levels, a packet will take a largenumber of hops which linearly increases latencies due tothe packetization delay at each node.Given the complexity of considerations, how does onei) conceptualize the power control problem, ii) determinehow to trade off the multiple objectives of capacity, bat-tery life and latency, and iii) develop a protocol which ismodular and elegant enough to work with the OSI archi-tecture?A first cut solution was presented in [2]. A net-work layer protocol was developed which ensured that thetransmit power used by all the packets, at all the nodes,would converge to a common power level: the lowestpower level at which the network is connected. A soft-ware architecture was also developed with the requisiteproperties of modularity and layering. Also provided wasan implementation in the Linux kernel.When nodes are homogeneously dispersed in space,as in Fig. 1(a), which is the case asymptotically when alarge number of nodes are uniformly distributed, then thechoice of a common transmit power level has several ap-pealing features and properties. However, when nodes arenon-homogeneously dispersed as in Fig. 1(b), then choos-ing the lowest common power level for all nodes that re-sults in network connectivity will imply that the commonpower level is dictated by outlying nodes, those which arefar from others, as the node F in Fig. 2. All nodes, ex-cept F, are mutually reachable at 1 mW. We say that thesenodes form a 1 mW cluster and F is outside this clus-ter. F can be reached from some of the nodes of the 1mW cluster but only by using a power level of 100 mW.The COMPOW algorithm, which converges to the low-est power level such that the network is connected, willin this case converge to 100 mW. Thus every node in thenetwork will be forced to use 100 mW even though 1 mWis enough for most communications. Thus, the outlyingnodes force all the other nodes to use a higher power levelsince the protocol works to ensure a common power levelat all the nodes.However, such non-homogeneous scenarios are ripe forclustering. One wishes to group nodes into clusters, withpossibly multiple levels of clustering hierarchy, i.e., sev-eral clusters at level k form a cluster at level k+1, and usemultiple levels of power in a manner commensurate withthe multiple layers of clustering. The clustering of nodescannot be based just on the geographical co-ordinates ofa node since the presence of obstacles and shadowing ina wireless channel may prevent two nodes from forminga link at a certain power level, even if they are in closeproximity. Power control should also be done in conjunc-tion with routing since they affect each other. Power con-trol cannot be done without keeping connectivity in mind,which is known only through the existence of routes. Onthe other hand, routing depends on


View Full Document

Pitt CS 3510 - Clustering by Power Control

Download Clustering by Power Control
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Clustering by Power Control and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Clustering by Power Control 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?