Distributed Algorithms for Joint Routing, Scheduling, Rate and Power Control in Multi-Hop Wireless Sensor Networks

Distributed Algorithms for Joint Routing, Scheduling, Rate and Power Control in Multi-Hop Wireless Sensor Networks

1Swati Kumari, 2Anup Tiwari, 3Samir Kumar Pandey,4N. P. Tiwary

Department of Computer Science Engineering, BIT Mesra, Ranchi 834002 Department of Electrical & Electronics Engineering, Jharkhand Rai University, Ranchi 834002

Department of Mathematics, Jharkhand Rai University, Ranchi – 834002 Department of Computer Science Engineering, BIT Mesra , Ranchi – 834002

Abstract – Distributed algorithms for joint routing, scheduling, rate and power control have been proposed previously for multi-hop wireless sensor networks. We propose proportionally fair rate control by optimizing a single network parameter in a distributed manner. We also include a version of the previous distributed greedy scheduling heuristic algorithm, which has same communication complexity but less computational complexity.

Index Termsdistributed algorithm, multi-hop wireless networks, rate control, routing, scheduling, power control.

1. INTRODUCTION

   In a multi-hop wireless sensor network (MWSN), any node can generate data and transmit it to the destination node(s), by consuming some part of the battery power, via multiple hops and using wireless channel. A node fails if its battery is depleted. Since the source rates are limited by link capacities available at downstream nodes, efficient rate control and routing algorithms are required. The transmission from one node interferes with other nodes within its radio communication range because of shared wireless channel. Hence power control and scheduling needs to be designed. Thus, joint optimization of routing, scheduling, rate and power control is required in the network.

   1. Problem Addressed

      Centralized algorithms for joint routing, scheduling, rate and power control have been previously developed, in which a central node controls network parameters such as rate, traffic requirements, etc., by obtaining information globally from all nodes in the network.

      Centralized algorithms are efficient but have a few draw- backs such as single point of failure (central node failure), lack of scalability, and difficulty in obtaining global information. Thus, it is desirable to develop efficient decentralized algorithms for joint routing, scheduling, rate and power control in the network which makes use of local information. These algorithms may be scalable to thousands of nodes and reduce the communication complexity.

   2. Related Work

      Transmission consumes substantial energy; hence energy efficient transmission methods are used. This is done via compression of data transmitted ([5], [10]), optimization of number of hops used in transmission ([4], [1]), routing of data along nodes with sufficient battery power, opportunistic scheduling of wireless links [6] and transmit power control etc. In addition, joint routing, power control and link scheduling ([4], [11]), can significantly enhance the system performance.

   3. Our Contribution

      As far as we know, this is a work towards a distributed algorithm for maximizing the minimum of the ratios between the allocated rate and demanded rate for the flows of the network (i.e., optimizing a single parameter of the network in a distributed manner) subject to the primary (necessary) network constraints. We define Composite Link Price for each link in the network, which takes account into link price and power price. We also include a version of the previous distributed greedy scheduling heuristic algorithm [2], which has same communication complexity but less computational complexity.

   4. Organization

   In Section II, we describe our model and notation. Section III discusses the problem formulation and the constraints for joint routing, scheduling, rate and power control in MWSN. Section IV develops distributed algorithms for Lagrange dual problems. Section V provides simulation results. Section VI concludes the paper.

2. MODEL AND NOTATION

   We represent the network as a connected directed graph G(N,L) , where N and L are set of nodes and directed links (edges), indexed by n {1,2, .,n,..N} and l {1,2, ., l, ..L} respectively. A wireless link l = (i, j) L exists if node j N can receive packets directly from node i N, i.e., if node j is one-hop neighbor of node i. We then, define node i as source node, node j as destination node of link l, and we call link l as an attached link to node i . We consider the wireless link as a directed edge from the source node to the destination node. The communication between a source and

   destination pair is defined as a flow. The set of flows is denoted by F and indexed by f {1, 2, ., f, ..F}. Source and destination of flow f are denoted by s(f) and d(f) respectively. We consider K-hop link interference model as considered in [2]. All links in the network cannot be activated simultaneously due to primary interference model. A mode is defined as a subset of links which can be activated simultaneously (with an L- dimensional power vector, PL) in such a way that no two links of this subset interfere under the given interference model and no other link can be added to this subset without violating the interference constraint. The modes are independent sets. The set of modes is denoted by M and indexed by m. A

   = minf (rf/df) , where f F

   i.e. df rf

   where , df is the data rate requested by node s(f) for flow f and rf is the assigned / permissible data rate for flow f. Our objective is to maximize the utility function which is a function of . This fainess is of max- min type[12].

   A.The Optimization problem

   Our primal problem is as follows:

   mode gives an L-dimensional capacity vector, RL(m), which denes capacity of all links when mode m is chosen i.e., its lth element is R1(m). The capacity of link l is Rl(m) if it is

   active in mode m; else Rl(m) = 0. Let m (0.1) be the

   rf (2)

   f

   (1) subject to: df =

   l

   fraction of time mode misactive. Rate on link l of ow f is denoted by x f . A is an (N x L) Node-Link incidence matrix

   (3)

   M. (Link Capacity Constraints)

   for the wireless network, where anl = 1 if node n transmits on link l; anl = -1 if node n receives on link l; anl = 0

   m = 1(Mode Constraints) (4)

   otherwise. Xf is an L-dimensional vector which gives the f f

   rates on various links for ow f . Yf is an N-dimensional vector which gives the rate generated/consumed by the nodes for ow f . If the rate allocated for flow f is denoted as rf then Yf for node s(f) is rf , for node d(f) is -rf , and it is 0 for the remaining nodes.

   Let Pnavg denote the average available power at node n. A node n is not allowed to transmit with an average available power Pn at that node at all times due to the interference.

   A.X = Y . f F (Flow conservation constraints) (5)

   N. PNavg(Power Constraints) (6)

   where, U() is the combined concave utility of all users if fraction of their flow is transmitted, M is an (L x M) matrix with mth column being the rate vector RL(m) for mode m,

   is an M-dimensional vector of M mode activation time-

   avg

   Instead, it will transmit with a power Pn chosen from the discrete set called power-levels denoted by P. We use three power-levels in our model, i.e., P {0,P1 , P2 = 2P1}. A mode also gives an N-dimensional power vector, PN(m), which defines the transmit power of all the nodes when mode m is chosen, i.e., its nth element is Pn(m). The transmi power of node n is Pn(m). The transmit power of node n is Pn(m) if any one of its attached links is active in mode m; else Pn(m) = 0. Let Pn(l)(m) denote the transmit power on link l attached to node n in mode m, and qn(l) denote the power price of node n to which link l is attached. Let Ln denote the set of links attached to node n. Let hll is the channel gain of link l and changes due to fading.

3. PROBLEM FORMULATION AND CONSTRAINTS FOR JOINT ROUTING, SCHEDULING, RATE AND

   POWER CONTROL

   In this section, we formulate the problem for joint, routing, scheduling, rate and power control subject to various constraints. Then we use Lagrange dual to simplify the optimization problem by dividing the dual problem into two sub problems and it is well known.

   For a flow f, let node s(f) request transmission at rate df to destination node d(f). d(f) can be different for different flows. The quantity minf (rf /df), where f F, gives the highest rate suffering flow in the network. Hence, our goal is to maximize the quantity minf(rf/df) to move towards the better fairness among the nodes (users) in the network. We can now define the rate control (fairness) parameter as

   fractions m , N is an (N x M) matrix with column m of the

   n

   matrix being the transmit power vector PN(m) for mode m, and PNavg is an N-dimensional vector whose nth element is

   P

   avg.

   All constraints in the above optimization problem are convex. We consider the dual of this problem to obtain a distributed algorithm for solution.

   B. Lagrange-Dual of the Problem

   Let p and q be Lagrange Multiplier Vectors of dimensions L and N associated with Link Capacity and Power Constraints respectively. And we call p and q be Link Price and Power Price Vectors respectively. Lagrange-Dual of the problem is

   (7)

   where ,

   (8)

   subject to the constraints (2),(4), and (5).

   For D1(p,q) and D2(p,q) as defined blow, we have D(p,q)

   = D1(p,q)+D2(p,q). And this decomposition is well known([9],[3]).

   C.Rate control and Routing Sub-Problem

   subject to : (2) and (5)

   (9)

   arg maxm{ 1R1(m) – npn(m)}

   . (12)

   Hence, we get a particular mode for activation depending on link prices and power prices. Average is taken over the

   iterations to get the vector . Our goal is to find the

   This optimization problem is different from the one used in literature (see, e.g., [3]) as we use a concave increasing utility function of a scalar global parameter in place of concave increasing utility function of df , i.e., U (df ).

   D. Scheduling and Power Control Sub-Problem

   (10)

   scheduling in a distributed manner using the distributed greedy scheduling heuristic algorithm 2 presented in Appendix VII-A. To do this, we derive a new metric called Composite Link Price, which includes link price and power price in a single term.

   C. Derivation of the Composite Link Price

   subject to: (4)

   In this sub-problem, let the optimal scheduling vector be

   x(p, q) for a given link price vector p, and power price vector q. All entries of x(p, q) will be zero, except the one

   corresponding to an independent set (of link activation) with maximum aggregate difference of price-rate product, and price-power product.

4. ALGORITHMS FOR SOLVING THE SUB- PROBLEMS

   In this section, we propose an algorithm, which uses a sub- gradient method for obtaining the optimal solution. First we provide algorithms to solve the sub-problems, that are then combined to propose a complete decentralized algorithm.

   A. Rate Control and Routing Sub-Problem

   qT.PNavg is constant , since PNavg is constant for our model. Hence, maximizing D1(p, q) is same as

   Since at most one attached link to a node is active in a given mode due to the interference. Hence, the transmit power of the node is equal to the sum of transmit powers on its attached links, i.e, npn(m)=

   . n(l)Pn(l)(m). The double summation

   . . gives all links in the network.

   In our model hll2Pn(l)(m)/N0W = 1, since a sensor node

   communicates with its nearby sensor node with low power. Since interference is removed by satisfying the primary interference constraint, the capacity of link l by Shannons capacity formula is given by

   (11)

   subject to : (5)

   R

   R

   The above optimization problem gives the optimal route Xf* for the unit source flow f F (i.e., rf = 1). Since the link capacity constants are not present in this sub-problem, at the optimal point each flow f is routed along a path of least path-price pf* =pT.Xf*. With flows routed along this paths, D1(p, q) can be found by optimizing w.r.t . If a feasible value of exists for which U() = f.pf* , this value is

   Where, l is constant for link l, and can be different for different links. Therefore, the capacity of the link varies linearly with transmit power on it.

   Substituting this value in the equation (12), we obtain

   {l. Rl(m)-qn(l).Pn(l)(m)}

   optimal.Optimizing w.r.t requires computation of

   f.pf*

   which can be done in a distributed manner over

   R,

   a rooted spanning tree. Such a spanning tree can be obtained using a distributed algorithm. Least-price path can be computed using, for instance, the distributed Bellman-Ford algorithm. Let X* denote the resulting L-Dimensional vector

   l

   of link flows x *. And X* = { .Xf*}.

   f

   B. Scheduling and Power Control Sub-Problem

   We start with an initial p and q vectors, that are updated in every iteration using the link price and power price updating equations (14) and (15) respectively. Optimizing D2(p, q) gives us the mode, i.e., scheduling is done.

   {pTM. – qTN. } gives an M-dimensional

   row vector; its mth element is { lRl(m)-

   nPn(m)}. The index of the element whose value is maximum is the mode chosen in that iteration, i.e., choose

   = {l- l . qn(l)). Rl(m)

   = {plRl(m)

   where, pl = pl – l is called the Composite Link Price of link l L. The Composite Link Price includes the link price pl of the link l, and power price qn(l) of the node n to which link l is attached in a single term. Our scheduling and power control sub-problem becomes

   arg maxm { = lRl(m)},

   . where m M

   . (13)

   We use a version of the distributed greedy scheduling heuristic algorithm proposed in [2], which does not use CHECK state, which has same communication complexity but less computational complexity and is presented in

   Appendix VII-A. And we use Composite Link Prices as its input.

   1. Link Price and Power Price Update Algorithm

      Link price and power price updating will be done using the following algorithms for all proposed algorithms for solving the dual problem. Since the dual function D(p, q) is not differentiable, we cannot use the casual gradient methods and hence the dual problem is solved using the sub-gradient

      .N. of the dual function,

      g(p, q) = [M. – f -PNavg.]T

      D(p,q) at (p,q):

      p[j+1] = (p[j]+ ( fF Xf[j]-M. [j]))+

      and

      q[j+1]= (q[j]+ (N. [j]-PNavg.))+

      where, , >0 are suitably chosen small constants.

      Hence the price of link l from j to j + 1 will be updated as follows:

      pl[j+1] = (Pl[j]+ (x1[j]-Rl[j]))+. (14)

      where, p [j] is the price of the link l in jth iteration, x [j] is

      global network parameter = minf rf/df . f F subject to the network constants is solved by applying the duality theorem, wherein the system problem is decomposed into a rate control and routing sub-problem, and scheduling and power control sub-problem. They interact through link prices and power prices. Routing is based on the link prices. And scheduling is based on link prices, and also power prices.

      The above dual algorithm motivates the following joint routing scheduling, rate and power control algorithm, which uses strictly concave utility function U ( ) =.

      The network is organized in a spanning tree with a root node, which controls the global network parameter, . A spanning tree may be obtained in a distributed manner as in [7].

      ALGORITHM 1 CONCAVE UTILITY ALGORITHM

      1: Every node has the knowledge of links attached to it. From jth to ( j + 1)th iteration, it updates the price of link l , and price of node n using the link price, and power price update algorithms given in equations (14), and (15) respectively, and also calculates the Composite Link Price, which takes account into link price and power price.

      R

      2: Using any distributed algorithm for routing, the optimal route or the minimum priced path is chosen for each of the flows, and the path-prices p f* becomes available at the source nodes. Then the nodes are made aware of the flow-

      l th l rates rf passing through them.

      the aggregate flow on the link l in j iteration.

      Rl[j] is the capacity of the link l in jth iteration. Equation

      (14) says that the link price will rise if the aggregate flow on the link exceeds the capacity of the link, this will result in selection of the mode which contains these links, thus increasing the effective capacity of the links.

      Hence, the price of node n from j to j + 1 will be updated as follows:

      avg.

      qn[j+1] = (qn[j] + (Pn[j]-Pn ))+ (15)

      where, qn[j] is the power price of node n in the jth iteration,

      Pn[j] is the transmission power of node n in the jth iteration,

      3: f.PRf* is computed by passing summary messages from the leaf nodes of spanning tree towards the root node. Every node in the chain adds the partial sums received from its child nodes to its own contribution, and passes the result to its parent node.

      4:U () = is a concave function. The unique maximizer of D1(p, q) is at U() = f.PRf*. Hence, root node can obtain the network parameter

      P

      n

      avg

      . is the average available power at node n, which is

      Root node computes value of .P f*,, and

      constant for our model. Equation (15) says that the power price will rise if the transmission power of the node exceeds the average available power at that node. This will result in the selection of the mode which doesnt contain these nodes, thus conserving the energy available at these nodes.

      The updating algorithms can be implemented in a distributed manner using only local information as explained below.

   2. Distributed Algorithms for Joint Routing, Scheduling, Rate and Power Control

   We consider a network with K-hop link interference model.Based on the algorithms provided from IV-A to IV- D, a distributed sub-gradient algorithm for joint routing, scheduling, rate and power control is obtained.

   In this algorithm, optimal routing for a flow depending on link prices is obtained using a distributed routing algorithm. Utility maximization problem of the

   f R

   disseminates computed values through the spanning tree.

   5: As stated in section IV-B, the second sub-problem is solved using the distributed greedy scheduling heuristic algorithm 2, with Composite Link Price as its input.

5. SIMULATION RESULTS

   In this section, we take a network with 24 nodes and 76 links as shown in figure (1), and provide the simulation results for Concave Utility Algorithm of section IV-E.

   We consider three power-levels {0,P1, P2 = 2P1}. And we assume that all links activated in a mode transmit at same power level either P1 or P2.

   We assume average available power for each node = 0.5 units. We consider capacity of link = 1 unit/sec., if it is active in mode m with power level P1 = 1, and capacity of link = 2 units/sec., if it is active in mode m with power level P2.

   We initialize all link prices to 0.3 and all power prices to 0.4.Source and destination pairs for the flows are (1,24), (2,23),(3,22), (4,21), (5,20), (6,19), (7,18), (8,17),

   (9,16), (10,15), (11, 14), (12, 13).

   Figure 1: Example Network Graph

   Note: The number indicated against the arrow represents the link index in that direction.

   We assume equal demands for all flows, i.e. 0.5 units/sec. We assume that proportionality constant l = 1; l L.

   We consider K = 1 with power level P1, and K = 2 with power level P2, to reflect an increase in interference neighborhood with transmit power. We execute distributed greedy scheduling heuristic algorithm 2 first with K = 1 and then with K = 2 and select the value of K for which the sum in equation 13 is maximized.

   We use step size for both link price and power price update algorithms = 0.01.We obtain, the optimal value of (at 6000th iteration), i.e., the maximum fraction of throughput that can be supported in the network for each flow is given by * = 0.1614 and convergence of is shown in figure (2).

   If we neglect the initial 500 iterations before the link price becomes stable, average value of obtained by averaging the values from 500 – 6000 iterations is Average *= 0.1669

   of average * by listing out all possible modes in this network.

   Plots of Link Prices Vs Number of Iterations converge over 6000 iterations, and the plot for one of the link prices is shown in figure (2).

   Plots of Power Prices Vs Number of Iterations converge over 6000 iterations, and the plot for one of the power prices is shown in figure (2).

   We can increase the step size from 0.01 to 0.1, to reduce the number of iterations (reduces from 6000 to 1000 iterations) and the algorithm 1 gives approximately same average * is obtained.

   We have verified in a smaller network with 6 nodes and 14 links our distributed algorithm achieved 95 percent of the optimal value obtained through centralized algorithm. It is feasible to compute reference optimal value

   Figure 2: Plots of Lambda, and typical link and power prices

6. CONCLUSION

   We have proposed and studied a distributed algorithm for Joint Routing, Scheduling, Rate and Power Control in a MWSN which aims to approximate optimum throughput efficiency and fairness. We also included a version of the

   previous distributed greedy scheduling heuristic algorithm [2], which has same communication complexity but less computational complexity.

7. APPENDIX

1. Distributed Greedy Scheduling Heuristic Algorithm without CHECK States

   We include a version of previous distributed greedy scheduling heuristic algorithm [2] without CHECK states, which has same communication complexity but less computational complexity.

   Refer [2] for terminology and definitions used in the distributed greedy scheduling heuristic algorithm.

   In algorithm 2 below, the maximum priced link in its corresponding (K + 1)-hop neighborhood gets MARKED at time TmL, and OPEN links that are interfering with at least one MARKED link are CLOSED at time TmM.

   In [2], interference checking has to be done to put an OPEN link in CHECK state, and a few more computations are required to OPEN the highest priced attached CHECK link. In other words, use of CHECK state increases the computational complexity. However, the two distributed greedy scheduling heuristic algorithms have same communication complexity, since a node has to disseminate its OPEN link price or MARKED link if it has one, to the (K + 1)- hop neighbor-hoods.

   Our modified version of the distributed greedy scheduling heuristic algorithm is as follows:

   Algorithm 2 Pseudo-code for Distributed Greedy Heuristic without CHECK states

   In slot Sml

   1: Disseminate the highest OPEN attached link price to

   (K+1)- hop neighborhoods.

   L

   At time Tm

   1: if at least one attached link is OPEN then

   2: sort the attached OPEN links in descending order of link price. Let lmax be the maximum priced link among the attached OPEN links.

   3: if no OPEN link prices are recived then

   4: link lmax is MARKED and all other OPEN attached links are CLOSED, go to 15.

   5: else

   6: sort received OPEN link prices in descending order of link prices. Let lmax be the maximum priced link among the received OPEN links.

   7: end if

   8: if plmax > Plmax then

   9: link lmax is MARKED and all other OPEN attached links are CLOSED.

   10: else if Plmax = Plmax then

   11: if Link lmax ID < link IDs of the received OPEN links

   then

   12: link lmax is MARKED and all other OPEN attached links are CLOSED.

   13: end if

   14: end if

   15: end if

   In this slot, maximum priced links in their corresponding (K

   + 1)-hop neighborhood get MARKED.

   In slot SmM

   1: if any one of the attached links is MARKED then

   2: disseminate this information to (K + 1)- hop

   neighborhoods. 3: end if

   At time TmM

   1: for each attached OPEN link l do

   2: if (d(l . received MARKED link) < K) for at least one received MARKED link then

   3: link l is CLOSED. 4: else

   5: link l remains in OPEN state. 6: end if

   7: end for

   8: Algorithm status is set to TERMINATE at nodes which have no OPEN links.

   In this slot, an OPEN link is moved to CLOSED state, if it interferes with at least one MARKED link, else it remains in OPEN state ( line numbers 1 to 5 ).

   In slot SmT

   1: if at least one attached link is OPEN then

   2: send a DO NOT TERMINATE message to all nodes in the (K + 1)-hop neighborhood.

   3:else if got a DO NOT TERMINATE message then

   4: send a DO NOT TERMINATE message to all nodes in the (K + 1)-hop neighborhood.

   5: end if

   At time TmT

   1: if no DO NOT TERMINATE message is received then

   2: the algorithm has terminated, schedule all MARKED

   links. 3: else

   4: go to the (m + 1)th ROUND. 5: end if

   The algorithm terminates when no attached link is in OPEN state. In this slot, this information is disseminated to all other nodes in the network in a distributed manner. This ensures that the algorithm terminates in a synchronous fashion at each node.

   REFERENCES

   1. F. Zhao and L.J. Guibas, Wireless Sensor Networks: an information processing approach, Morgan Kaufmann, 2004.

   2. A. Sunny and J. Kuri, "Distributed Greedy Scheduling for Multihop Wireless Networks," IEEE MASS Nov.2010, workshop on wireless Mesh Tech 2010, pp 1-6.

   3. N. Sahasrabudhe and J.Kuri, "Distributed Scheduling for Multi- hop Wireless Networks," in Proceedings of the First international conference on COMmuniation Systems And NETworks. IEEE, 2009, pp. 278-285.

   4. V. Joseph, V. Sharma and U. Mukherji, "Joint Power Control, Scheduling and Routing for Multihop Energy Harvesting Sensor Networks," in Proceedings of the 4th ACM workshop on Performance monitoring and measurement of heterogeneous wireless and wired networks. ACM, 2009, pp.128-136.

   5. S.S. Pradhan, J. Kusuma, and K. Ramchandran, "Distributed Compression in a Dense Microsensor Network," IEEE Signal Processing Magazine,vol. 19, no. 2, pp. 51-60, Mar. 2002.

   6. J.H. Chang and L. Tassiulas, "Maximum lifetime routing in wireless sensor networks," IEEE/ACM Transactions on Networking, vol. 12, no.4, pp. 609-619, 2004.

   7. R.G. Gallager, P.A. Humblet, and P.M. Spira, "A distributed algorithm for minimum-weight spanning trees," ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 5, no. 1, p. 77, 1983.

   8. Dimitri P. Bertsekas, Nonlinear programming, Athena Scientific, 2003.

   9. Daniel P. Palomar and Mung Chiang, "Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications," IEEE Transactions on Automatic Control, vol. 52, no. 12, Dec. 2007.

   10. Seung Jun Baek, Gustavo de Veciana, and Xun Su, "Minimizing energy consumption in large-scale sensor networks through distributed data compression and hierarchical aggregation," IEEE Journal on Selected Areas in Communications, vol. 22, no. 6, pp. 1130-1140, Aug. 2004.

   11. X. Wang and J.J. Garcia-Luna-Aceves, "Distributed joint channel assignment, routing and scheduling for wireless mesh networks," Computer Communications, vol. 31, no. 7, pp. 1436- 1446, 2008.

   12. V. Singh and V. Sharma, "Efficient and fair scheduling of uplink and downlink in IEEE 802.16 OFDMA networks," in Proc. IEEE Wireless Communications and Networking Conference, 2006, pp. 984-990.