A utility-optimal backoff algorithm for wireless sensor networks

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.

Keywords

wireless sensor networks / network utility maximization / backoff algorithm / collision probability

References

[1] OssamaY., SoniaF.. 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] HuZ.-g., MaH., WangG.-j., LiaoL.. 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] JussiH., ZachS., CarlosP., PetriM.. Multihop medium access control for WSNs: An energy analysis model [J]. EURASIP Journal on Wireless Communications and Networking, 2005, 4: 523-540

[5] InjongR., QarrierA., AiaM., JeongkiM., SichitiuM. L.. Z-MAC: A hybrid MAC for wireless sensor networks [J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 511-524

[6] YeW., HeidemannJ., EstrinD.. 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] FanY., TaoW., BiswasS.. 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] BurattiC., GiorgettiA., VerdoneR.. 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] TianQ., CoyleE. 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] ChangM., LowS. H., CalderbankA. R., DoyleJ. C.. Layering as optimization decomposition [J]. Proceedings of the IEEE, 2007, 95(1): 255-312

[12] LowS. H., LapsleyD. E.. Optimal flow control. I: Basic algorithm and convergence [J]. IEEE/ACM Transactions on Networking, 1999, 7(6): 861-874

[13] BianchiG.. 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.