Essential Topics on Constructing WCDS-based Virtual Backbone in Wireless Sensor/Mesh Networks

Chie Dou, Yung-Han Hsiao

Department of Electrical Engineering, National Yunlin University of Science and Technology, 640 Touliu, Yunlin, Taiwan，China.

DOI: 10.4236/cn.2013.52B001                

Abstract

Clustering or connected dominating set (CDS) both approaches can establish a virtual backbone (VB) in wireless sensor networks (WSNs) or wireless mesh networks (WMNs). Each cluster consisting of a cluster head (CH) and its neighboring nodes can form a dominating set. After some bridging nodes were selected, cluster heads (CHs) connected through these bridging nodes naturally formed a CDS. Although CDS provides obvious backbone architecture, however, the number of cluster heads and bridging nodes may be too large, this may cause the loss of advantages of virtual backbone. When we effectively reduce their numbers, more effectively WCDS (Weakly Connected Dominating Set) can be fining out. Some essential topics on constructing WCDS-based VB in WSN/WMN are discussed in this paper. From the point of view of three different protocol layers, including network (NWK) layer, MAC layer, and physical (PHY) layer, we explore their cross-layer research topics and design algorithms. For NWK layer, area-based WCDS algorithms and routing strategies including via VB and not via VB are discussed. For MAC layer, a WCDS-based energy-efficient MAC protocol is presented. For PHY layer, battery-aware alternative VB selections and sensor nodes with different transmission ranges are addressed.

Keywords

Weakly Connected Dominating Set; Wireless Sensor/Mesh Networks; Virtual Backbone; Cross-Layer Design

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Y. P. Chen and A. L. Liestman, “Approximating Minimum Size Weakly Connected Dominating Sets for Clustering Mobile Ad Hoc Networks,” Proceedings ofthe 3rd ACM international symposium on Mobile ad hoc networking & computing, New York, USA: ACM, 2002, pp. 165-172.
[2]	B. Han and W. Jia, “Clustering Wireless Ad Hoc Networks with Weakly Connected Dominating Set,” Journal of Parallel and Distributed Computing, Vol. 67,2007, pp. 727 – 737. doi:10.1016/j.jpdc.2007.03.001
[3]	D. Kim, Y. Wu, Y. Li, F. Zou and D. Z. Du, “Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 2, 2009, pp. 147-157.
[4]	R. Misra and C. Mandal, “Rotation of CDS via Connected Domatic Partition in Ad Hoc Sensor Networks,” IEEE Transactions on Mobile Computing, Vol. 8, No. 4, 2009, pp. 488-499.
[5]	T. Acharya, S. Chattopadhyay and R. Roy, “Multiple Disjoint Power Aware Minimum Connected Dominating Sets for Efficient Routing in Wireless Ad Hoc Network,” Proceedings International Conference on Information and Communication Technology, 2007, pp. 336-340.
[6]	F. Dai and J. Wu, “An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 10, 2004, pp. 908-920. doi:10.1109/TPDS.2004.48
[7]	J. Wu, F. Dai and S. Yang, “Iterative Local Solutions for Connected Dominating Sets in Ad Hoc Wireless Networks,” IEEE Transactions on Computers, Vol. 57, No. 5, 2008, pp. 702-715. doi:10.1109/TC.2008.25
[8]	S. Zhang, J. Fan, J. Jia and J. Wang, “An Efficient Clustering Algorithm in Wireless Sensor Networks Using Cooperative Communication,” International Journal of Distributed Sensor Network, Vol. 2012, pp. 1-11.
[9]	F. Wang, M. T. Thai and D. Z. Du, “On the Construction of 2-Connected Virtual Backbone in Wireless Networks,” IEEE Transactions on Wireless Communications, Vol. 8, No. 3, 2009, pp. 1230-1237. doi:10.1109/TWC.2009.051053
[10]	L. Ding, W. Wu, J. Wil-son, H. Du, W. Lee and D. Z. Du, “Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks,” IEEE Transactions on Parallel and Dis-tributed Systems, Vol. 22, No. 10, 2011, pp. 1601-1609. doi :10.1109/TPDS.2011.30
[11]	N. Chakchouk, B. Hamdaoui and M. Frikha, “WCDS- nduced Routing for Data-Aggregation in Wireless Sensor Networks,” Proceedings of the First International Conference on Communications and Networking, 2009, pp. 1-6.
[12]	M. H. Imtiaz, M. R. A. Sumi, S. M. Mostafa Al Mamun and Md. N. Hassan, “A New Approach for Designing and Analysis of Distributed Routing Algorithm and Protocols of Wireless Ad Hoc Network,” International Journal of Science and Advanced Technology, Vol. 1, No. 6, 2011, pp. 10-17.
[13]	D. Kim, Z. Zhang, X. Li, W. Wang, W. Wu and D. Z. Du, “A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs,” IEEE Transactions on Mobile Computing, Vol. 9, No. 8, 2010, pp. 1108-1118. doi:10.1109/TMC.2010.55
[14]	M. T. Thai, F. Wang, D. Liu, S. Zhu and D. Z. Du, “Connected Dominating Sets in Wireless Networks with Different Transmission Ranges,” IEEE Transactions on Mobile Computing, Vol. 6, No. 7, 2007, pp. 721-730. doi:10.1109/TMC.2007.1034
[15]	J. He, S. Ji, P. Fan, Y. Pan and Y. Li, “Constructing a Load-Balanced Virtual Backbone in Wireless Sensor Networks,” Proceedings of the International Conference of the IEEE ICNC, Hawaii, Vol. 30, 2012, pp. 959-963.
[16]	W. Ye, J. Heidemann, and D. Estrin, “Medium Access Control With Coordinated Adaptive Sleeping for Wire-less Sensor Networks,” IEEE/ACM Transactions on Networking, Vol. 12, No. 3, 2004, pp. 493–506. doi:10.1109/TNET.2004.828953
[17]	Injong Rhee, A. Warrier, M. Aia, Jeongki Min, and M. L. Sichitiu, “Z-MAC: A Hybrid MAC for Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, Vol. 16, No. 3, 2008, pp. 511-524. doi:10.1109/TNET.2007.900704
[18]	G.-S. Ahn, E. Miluzzo, S. G. Campbell, Andrew T. Hong and F. Cuomo, “Funneling-MAC: A Localized, Sink-Oriented MAC for Boosting Fidelity in Sensor Networks,” Proceedings of the 4th ACM Conference on Embedded Networked Sensor Systems (SenSys), Colorado, USA: ACM, 2006, pp. 293–306.
[19]	G. Pei and C. Chien, “Low Power TDMA in Large Wireless Sensor Networks,” Proceedings of the IEEE Military Communications Conference (MILCOM’01), 2001, pp. 347-351.
[20]	M. R. Jongerden and B. R. Haverkort, “Which Battery Model to Use?” IET Software, Vol. 3, No. 6, 2009, pp. 445-457. doi:10.1049/iet-sen.2009.0001