J. Cent. South Univ. Technol. (2009) 16: 0635-0639

DOI: 10.1007/s11771-009-0105-4

A utility-optimal backoff algorithm for wireless sensor networks

LIAO Sheng-bin(廖盛斌)^{1, 2}, YANG Zong-kai(杨宗凯)^{1, 2}, CHENG Wen-qing(程文青)¹, LIU Wei(刘 威)¹

(1. Department of Electronics and Information Engineering, Huazhong University of Science and Technology,

Wuhan 430074, China;

2. Engineering and Research Center for Information Technology on Education, Huazhong Normal University,

Wuhan 430079, China)

Abstract: A novel backoff algorithm in CSMA/CA-based medium access control (MAC) protocols for clustered sensor networks was proposed. The algorithm requires that all sensor nodes have the same value of contention window (C_W) in a cluster, which is revealed by formulating resource allocation as a network utility maximization problem. Then, by maximizing the total network utility with constrains of minimizing collision probability, the optimal value of C_W (W_opt) can be computed according to the number of sensor nodes. The new backoff algorithm uses the common optimal value W_opt and leads to fewer collisions than binary exponential backoff algorithm. The simulation results show that the proposed algorithm outperforms standard 802.11 DCF and S-MAC in average collision times, packet delay, total energy consumption, and system throughput.

Key words: wireless sensor networks; network utility maximization; backoff algorithm; collision probability

1 Introduction

In typical wireless sensor network (WSN) applications, sensor nodes are distributed in a certain region, and empowered by small irreplaceable batteries. Under such an energy constraint condition, sensor nodes can only transmit a finite number of bits in their lifetime. Consequently, reducing energy consumption is a key concern in WSNs.

A number of protocols have been proposed to reduce energy consumption. One of the possible approaches is to employ network clustering. Clustering techniques can aid in reducing energy consumption [1]. A common scenario in WSNs is that data are sensed from a cluster of wireless sensor nodes and delivered to the cluster head of the cluster. A cluster head acts like a gateway between the sensor nodes within its cluster and the sink node. Successful operation of this scenario would depend on some protocol components, such as cluster formation algorithm [2], reliable routing algorithm [3] and medium access control (MAC) [4]. A significant amount of work has been done on designing energy efficient MAC protocols for clustered sensor networks [5-10]. Typical examples include the time division multiple access (TDMA) and 802.11-like CSMA/CA MAC protocols.

The BEB-based 802.11 DCF MAC protocol has been considered for WSNs because of its low cost and wide implementation. It does not require synchronization, but the cost is wasted energy due to collisions and delays due to idle channel time. The contention mechanism of our algorithm is the same as that in IEEE 802.11 using request-to-send (RTS) and clear-to-send (CTS) packets. However, it will be demonstrated that the performance of IEEE 802.11 can be significantly improved by redesign of its retransmission control algorithm in the background of clustered WSNs in this work.

Recent work on retransmission algorithm that is most closely related to the algorithm developed in this work is SSCW algorithm [10]. But differentiating the SSCW-based method, formulating the problem of data gathering in WSNs as a network utility maximization (NUM) [11] problem is presented, whose objective function is to maximize the amount of information (utility) collected in each sensor node, subjected to the wireless channel bandwidth. Then, by regarding the normalized rate sum in a cluster as the price of link contention, i.e. the degree of link contention, the fact that every node in a cluster should have the same contention window (C_W) is validated. This is a new idea in improving the performance of network protocols including IEEE 802.11. Reversing the solution of an optimization problem and then optimizing the redesign of network protocols are the main contributions in this work.

2 Resource allocation model in cluster

Before presenting the model, a basic distributed optimization algorithm [12] that solves the problem of basic NUM model with fixed link capacities is introduced. In the next section, by introducing the cost of a successful transmission into basic NUM model, a key idea is obtained: all the nodes should have the same C_W in a cluster.

2.1 Basic distributed optimization algorithm

LOW and LAPSLEY [12] presented the following basic distributed optimization algorithm.

2.1.1 Establishing model

Consider a communication network with j links, each with a fixed capacity of c_j. Let route r be a non-empty subset of J, and R be the set of possible routes. Set A_jr=1 if j∈r, so that link j lies on route r, and set A_jr=0 otherwise. This defines a 0-1 routing matrix A=(A_jr, j∈J, r∈R).

Associate route r with a user, and suppose that if rate x_r is allocated to user r, then this has utility U_r(x_r) to the user. Assume that utility U_r(x_r) is increasing, strictly concave and continuously differentiable over the range  x_r≥0.

Let U=(U_r(x_r), r∈R) and C=(c_j, j∈J). Under this model the network seeks a rate allocation x=(x_r, r∈R) which solves the following primary problem:

s.t.    Ax≤C                               (1)

x≥0

2.1.2 Solving optimization problem using Lagrange duality

The Lagrangian dual function for the above primary problem is

D(μ)       (2)

where  μ=(μ, j∈J) is the vector of Lagrange multipliers. Thus, the dual problem for primal problem is

F₂=D(μ)                                (3)

In the dual formulation, Lagrange multiplier μ_j can be interpreted as the congestion price on link j. A key observation is that sources can compute their optimal rates individually based on the total congestion price

using the following source rate algorithm:

           (4)

To solve the dual problem, one can use the following projected gradient method:

           (5)

where  α_j is the positive scalar step size, and [a]⁺ denotes the projection of a onto set R⁺ of non-negative real numbers. According to the above formulae, the solution of the optimal source rates and congestion prices of links can be solved iteratively in Eqns.(4) and (5), respectively. This suggests that the network links and the sources are treated as processors in a distributed computation system to solve the dual problem.

2.2 Resource allocation scheme

The reference scenario we assume consists of some sensor nodes randomly and uniformly distributed over a square area. The sink node, which is located outside the sensor deployment area, is assumed to have less energy constraint compared with the sensing nodes. Moreover, the network is self-organized into multiple clusters [5], and within a cluster each sensor node has sufficient communication power to directly transmit to the cluster head. Neighboring clusters are assumed to use channels that are non-overlapping in the frequency domain or otherwise orthogonal domain, so they do not interfere with each other. This is already possible in 802.11 and other networks [10].

Successful operation of the model presented in this work depends on self-reorganizing cluster formation, cluster head election and energy efficient MAC, etc. In this work, the goal is to design the MAC layer for the intra-cluster communication, because all nodes in one cluster contend the common channel resource for their data transport. In the following section, from the degree of a cluster head, the characteristics of the intra-cluster communication are analyzed by regarding the channel contention as resource allocation.

Assume that one cluster consists of S sources indexed by s, and all nodes contend for common channel access and channel capacity is C in the cluster. Because all data sensed by all nodes deliver to cluster head, then, from the viewpoint of the cluster head, its objective is to maximize the amount of information (utility) collected in each sensor node, subjected to the wireless channel bandwidth. But collisions are unavoidable due to a CSMA protocol based on IEEE 802.11, the cost of a successful transmission is introduced into basic NUM model. And then, a new optimization problem is presented as follows:

        (6)

where  U_s(x_s) is an increasing, strictly concave and continuously differentiable utility function, and each source s attains a utility U_s(x_s) when it transmits at rate x_s. And λ_s is the price per unit rate for source s using the channel. Define price vector λ=(λ₁, ???, λ_s), which can be interpreted as a channel contention price vector that reflects the degree of contention in the cluster.

Assume that rate x_s and price λ_s are normalized. According to the method presented in Section 2.1, the above problem has an optimal solution denoted by x^*(λ) for a given price vector λ. Thus, from the viewpoint of

cluster head, the normalized sum rate  is the

natural measure of the contention in the cluster, where (λ_s) is the sth item of vector x^*(λ). So, the cluster

head will adjust price vector λ according to ,

i.e. it regards the normalized rate sum as contention probability at which nodes contend for the channel. In this way, in the proposed scheme, all nodes contend for

the channel with probabilityin one cluster.

In the backoff algorithm for IEEE 802.11, each contending node maintains a backoff C_W and waits for a random amount of time bounded by the backoff window before transmission, so the backoff window indicates the degree of contention. According to the above formulation, price vector λ also reflects the degree of contention in one cluster. For all nodes contend for the channel with the same probability in a cluster, all items of price vector λ are equal. This reveals that all nodes should have equal C_W value because they all contend for the channel with the same probability and price.

3 Utility-optimal backoff algorithm

In this section, the contention of a channel shared by multiple sensor nodes that use IEEE 802.11 DCF with equal C_W in a cluster is analyzed, and then a novel utility-optimal backoff (UOB) algorithm is proposed.

Assume the probability that a sensor node transmits in a randomly chosen slot time is expressed by p_t, then S nodes contend for the channel, probability p_s that a transmission occurring on the channel is successful is exactly given by the probability at which one node transmits on the channel, i.e.

                           (7)

Then, an idle probability and collision probability in a slot can be expressed, respectively:

                                (8)

                             (9)

Because all nodes have the same C_W, the transmission probability p_t can be computed as [13]:

                                (10)

Let T be the normalized system throughput, defined as the fraction of time the channel is used to successfully transmit payload bits. Then the normalized system throughput can be expressed as

                        (11)

where  L is the length of the data packets, T_s, T_f and T_i respectively express the average time that the transmission is successful, failing and the channel is idle. T_s, T_f and T_i can be computed as

                    (12)

       (13)

                         (14)

where  α and β represent the time of a successful transmission and a collision, respectively, and their expressions can be seen in Ref.[14], and δ is the length of idle slot time in IEEE 802.11.

From ?T/?p_t=0, p_t corresponding to the optimal system throughput is derived by

           (15)

So, by jointly solving Eqns.(10) and (15), the optimal value W_opt of C_W for a given number of the sensor nodes S is gained. As cluster head knows the number of the sensor nodes in its cluster, it can calculate the optimal value W_opt, and then broadcast W_opt to the sensor nodes in its cluster. Based on this consideration, the UOB algorithm is derived as follows.

(1) The cluster head computes the corresponding optimal value W_opt of C_W according to S by solving Eqns.(10) and (15). Then, the cluster head broadcasts a control packet that specifies the optimal contention window of W_opt to be used by all nodes in its cluster.

(2) The gathering of data packets from every sensor node to the cluster head begins at time t=0 with each node selecting a random number W_n that is uniformly distributed over [0, W_opt-1]. We also assume that each node maintains two counters as that in Ref.[14]. One is a backoff counter with starting value W_n; the other counter starts with W_opt, and is called the stage counter. All active nodes monitor the medium at time t=0. If a node senses the medium idle for a slot, it will decrease both its backoff and stage counters by one after each slot period, and the backoff process will be suspended until the medium is sensed idle again for more than DIFS when a transmission is detected on the channel.

(3) When a node’s backoff counter reaches zero, the node will transmit its RTS packet to the cluster head. It waits for ACK that comes from the cluster head. If ACK does not arrive in time, the node assumes it is collided. But contrary to the standard 802.11 DCF, the node will not generate a new random backoff slot until its stage counters reach zero.

(4) For all nodes in a cluster, on each successful transaction (successful data transmission followed by an immediate ACK), the sender will continue to monitor the medium and decrease its stage counter if the channel is idle. When the stage counter of nodes reaches zero, nodes generate a new backoff process and set their stage counter to be W_opt.

4 Simulation

In this section, network simulation tool ns-2 [15] is used to evaluate the performance of UOB algorithm against IEEE 802.11 MAC protocol and S-MAC. The parameters are listed in Table 1.

Table 1 Configuration parameters for ns-2 simulation

Nodes are randomly distributed in a 100 m×100 m area with a coverage radius of 150 m. Assume ideal channel conditions (i.e. no hidden terminals and capture) and saturation throughput. That is to say, each node always has a packet available for transmission.

Since the transmission failure primarily affects the energy consumption, throughput and delay, collision times is measured for performance evaluation.

4.1 Collision times

Average collision times reflects how the collision resolution scheme works. Collision not only wastes scarce bandwidth and exhausts limited energy, but also

decreases network throughput while increasing packet latency. A qualified backoff algorithm should resolve collision effectively while keeping overheads such as delay as small as possible. Fig.1 shows that the collision times of DCF is much greater than that of UOB because UOB completely eliminates cross collision. The collision times of S-MAC is much less than that of DCF because of its common sleep schedule mechanism, and is a little more than that of UOB because of the cross collision generated by nodes in contending for the channel.

Fig.1 Comparison of average collision times of systems with different node numbers

4.2 Energy consumption

Fig.2 shows the measured total energy consumption on all nodes. UOB and S-MAC with periodic sleep are almost the same in terms of energy efficiency, but for S-MAC the periodic sleep of nodes also decreases throughput, as shown in Fig.3. For IEEE 802.11 protocol, collisions between nodes lead to much waste of energy. The energy consumption of S-MAC without periodic sleep is lower than that of DCF because it reduces idle listening by putting nodes in sleep state.

Fig.2 Comparison of total energy consumption of systems with different node numbers

Fig.3 Comparison of normalized throughput of systems with different node numbers

4.3 Throughput

Fig.3 shows the normalized throughput results of IEEE 802.11 DCF, S-MAC with periodic sleep and UOB. For IEEE 802.11 protocol, with the increase of nodes, the contention for medium is undoubtedly intensified, which induces more collisions and finally results in throughput degradation. However, UOB avoids cross collision, which is dominant in networks. The probability of successful transmission is thus enhanced greatly, leading to the increase in throughput. S-MAC also reduces the throughput because of the sleep of nodes.

4.4 Delay

Fig.4 shows that UOB increases its packet delay more gently than DCF. DCF transmits packets in longer duration due to its frequent collision. In UOB, the collision probability is reduced significantly, which in turn contributes to the smaller delay. S-MAC increases latency because of the sleep of nodes.

Fig.4 Comparison of delay of systems with different node numbers

5 Conclusions

(1) A utility-optimal backoff (UOB) algorithm for random access MAC protocols is proposed to improve the performance of sensor networks. Simulation results show that the UOB-based 802.11 DCF protocol performs significantly better than both standard 802.11 DCF and S-MAC in terms of collision times, energy consumption, throughput and delay.

(2) Differentiating from the classical analysis, an optimization model is set up by regarding channel access as a resource allocation. Every node should have the same value of contention window (C_W) in a cluster in IEEE 802.11-like MAC protocols. This is a new idea for optimizing and designing network protocols.

References

[1] OSSAMA Y, SONIA F. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks [J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366-379.

[2] MOHANMED Y, KEMAL A, ANUGEETHA K. Optimization of task allocation in a cluster-based sensor network [C]// Proceedings of the 8th IEEE International Symposium on Computers and Communication. Kemer-Antalya, 2003: 329-334.

[3] HU Zhi-gang, MA Hao, WANG Guo-jun, LIAO Lin. A reliable routing algorithm based on fuzzy petri net in mobile ad hoc networks [J]. J Cent South Univ Technol, 2005, 12(6): 715-719.

[4] JUSSI H, ZACH S, CARLOS P, PETRI M. Multihop medium access control for WSNs: An energy analysis model [J]. EURASIP Journal on Wireless Communications and Networking, 2005, 4: 523-540.

[5] INJONG R, QARRIER A, AIA M, JEONGKI M, SICHITIU M L. Z-MAC: A hybrid MAC for wireless sensor networks [J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 511-524.

[6] YE W, HEIDEMANN J, ESTRIN D. Medium access control with coordinated adaptive sleeping for wireless sensor networks [J]. IEEE/ACM Transactions on Networking, 2004, 12(3): 493-506.

[7] WU T, BISWAS S. A self-reorganizing slot allocation protocol for multi-cluster sensor networks[C]// Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. Los Angeles, 2005: 309-316.

[8] FAN Y, TAO W, BISWAS S. Toward in-band self-organization in energy-efficient MAC protocol for sensor networks [J]. IEEE Transactions on Mobile Computing, 2008, 7(2): 156-170.

[9] BURATTI C, GIORGETTI A, VERDONE R. Cross-layer design of an energy-efficient cluster formation algorithm with carrier-sensing multiple access for wireless sensor networks [J]. EURASIP Journal on Wireless Communications and Networking, 2005, 5: 672-685.

[10] TIAN Q, COYLE E J. A mac layer retransmission algorithm designed for the physical-layer characteristics of clustered sensor networks [J]. IEEE Transactions on Wireless Communications, 2006, 5(11): 3153-3164.

[11] CHANG M, LOW S H, CALDERBANK A R, DOYLE J C. Layering as optimization decomposition [J]. Proceedings of the IEEE, 2007, 95(1): 255-312.

[12] LOW S H, LAPSLEY D E. Optimal flow control. Ⅰ: Basic algorithm and convergence [J]. IEEE/ACM Transactions on Networking, 1999, 7(6): 861-874.

[13] BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination function [J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.

[14] MA Hui, LI He-wu, ZHANG Pei-yun, LUO Shi-xin, YUAN Cong. Range estimation and performance optimization for IEEE 802.11 based on filter [C]// IEEE Wireless Communications and Networking Conference. Atlanta: 2004: 1469-1475.

[15] VARADHAN K, FALL K. The ns manual [M]. UC Berkeley, LBL, USC/ISI, and Xerox PARC, 2002.

(Edited by CHEN Wei-ping)

Foundation item: Project(60772088) supported by the National Natural Science Foundation of China

Received date: 2008-10-11; Accepted date: 2008-12-29

Corresponding author: LIAO Sheng-bin, PhD; Tel: +86-13986032626; E-mail: liaoshengbin@gmail.com