Modular Approach based Backbone Construction Using STP with CDS

Full Text (PDF, 464KB), PP.1-10

Views: 0 Downloads: 0


Rachita Nagpal 1,* Roopali Garg 1

1. Department of I.T, U.I.E.T, Panjab University, Chandigarh, 160014, India

* Corresponding author.


Received: 14 May 2015 / Revised: 25 Jun. 2015 / Accepted: 30 Jul. 2015 / Published: 8 Sep. 2015

Index Terms

Non-Probabilistic Spanning Tree, Connecting Dominating Set (CDS), Graph Sampling, Dominating Sets, Spanning tree Protocol (STP)


In a dense environment, wireless sensor network (WSN) requires more energy to work in an effective and efficient manner. Hence, energy conservation is the main objective. In the paper, we have proposed a methodology to construct a backbone using modular antennas in combination with spanning tree protocol (STP), graph sampling, and Connecting Dominating Set (CDS) strategy. The backbone construction is based upon the modular antenna based WSNs, where the dominating sets can avoid the intermediate connection in order to reduce the hop count and energy consumption. The dominating sets have been connected using the modular transmission range of the wireless sensor networks to construct the backbone. The dominating set selection procedure to construct the WSN backbone is based upon the degree of connections of the nodes, which enables the locally centralized behavior of the connected dominating sets. The proposed methodology has been proved effective resulting in the construction of an energy efficient backbone.

Cite This Paper

Rachita Nagpal, Roopali Garg,"Modular Approach based Backbone Construction Using STP with CDS", IJEM, vol.5, no.3, pp.1-10, 2015. DOI: 10.5815/ijem.2015.03.01


[1]D. Garg and R Garg, "Angled-LEACH in Wireless Sensor Networks", International Journal of Advances In Computing And information Technology, 2012

[2]R Garg and D Gupta, " Improving the Network Lifetime in WSN through Enhanced LEACH " , International Journal of Computer Applications, 2013

[3]K. Erciyes, D. Ozsoyeller and O. Dagdeviren, "Distributed algorithms to form cluster based spanning trees in wireless sensor networks." In Computational Science–ICCS 2008, pp. 519-528. Springer Berlin Heidelberg, 2008.

[4]P. Basuchowdhuri, S. Anand, D. R. Srivastava, K. Mishra and S. K. Saha, "Detection of Communities in Social Networks Using Spanning Tree" Advanced Computing, Networking and Informatics, Springer, 2014, pp. 589-597.

[5]P. Flocchini, T.M. Enriquez, L. Pagli, G. Prencipe and N. Santoro, "Distributed Minimum Spanning Tree Maintenance forTransient Node Failures", Computers, IEEE, 2012, pp. 408 – 414.

[6]X. Xiong and A. Ning, "Competitive decision algorithm for constructing maximum lifetime spanning tree in wireless sensor networks", Computer Science & Education (ICCSE), IEEE, 2014, pp. 1014-1019.

[7]S. Ren, P. Yi, D. Hong, Y. Wu and T. Zhu, "Distributed Construction of connected Dominating Sets Optimized by Minimum-Weight Spanning Tree in WirelessAd-Hoc Sensor Networks", Computational Science and Engineering (CSE), IEEE, 2014, pp. 901-908.

[8]J. Leskovec and C. Faloutsos, "Sampling from Large Graphs," ACM, 2006.

[9]R. Bhatt and R. Datta, "Utilizing graph sampling and connected dominating set for backbone construction in wireless multimedia sensor networks," in Communications (NCC), 2014 Twentieth National Conference on. IEEE, 2014, pp. 1–6.

[10]H. Du, W. Wu, Q. Ye, D. Li, W. Lee and X. Xu. "CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks." Parallel and Distributed Systems, IEEE, 2013, pp. 652-661.

[11]Y. Xiang, X. Liu, Y. Tang, J. Xiao and J Zhang. "A distributed algorithm for virtual backbone construction with cellular structure in WSNs." International Journal of Distributed Sensor Networks, 2012.

[12]Song Ci; Sharif, H.; Nuli, K., "Study of an adaptive frame size predictor to enhance energy conservation in wireless sensor networks," Selected Areas in Communications, IEEE, Volume: 23, Issue: 2, pp. 283 – 292, 2005.

[13]Tezcan, N.; Wenye Wang, "TTS: A Two-Tiered Scheduling Algorithm for Effective Energy Conservation in Wireless Sensor Networks," Communications ICC '06, IEEE, volume 7, pp 3359 – 3364, 2006.

[14]Hoang Duc Chinh; Panda, S.K., "Real-time power configuration for energy conservation in wireless sensor networks," Communication Systems (ICCS), IEEE, pp. 152 – 156, 2012.

[15]Glatz, P.M.; Hörmann, L.B.; Steger, C.; Weiss, R., "Opportunistic Network Coding for Energy Conservation in Wireless Sensor Networks," Communication Networks and Services Research Conference (CNSR), IEEE, pp. 239 – 246, 2011.

[16]R. Nagpal and R. Garg, "WSN Backbone Formation Using Non-Probabilistic Spanning Tree Algorithm" International Conference on Communication, Computing and Power Technologies, 2015, pp. 749-756, in press.