Greedy construction of load‐balanced virtual backbones in wireless sensor networks. Issue 7 (26th March 2012)

• Record Type: Journal Article
• Authors: He, Jing (Selena); Ji, Shouling; Pan, Yi; Li, Yingshu
• Is Part Of: Wireless communications and mobile computing. Volume 14:Issue 7(2014)
• Page Start: 673
• Page End: 688
• Publication Date: 2012-03-26
• Subjects: Wireless communication systems -- Periodicals; Mobile communication systems -- Periodicals; 621.38205
• DOI: 10.1002/wcm.2218
• Languages: English
• ISSNs: 1530-8669

Abstract

<abstract abstract-type="main" id="wcm2218-abs-0001"> <title>ABSTRACT</title> <p id="wcm2218-para-0005">Inspired by the backbone concept in wired networks, a virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). A connected dominating set (CDS) is used as a virtual backbone for efficient routing and broadcasting in WSNs. Most existing works focus on constructing a minimum CDS, a <italic>k</italic>‐connect <italic>m</italic>‐dominating CDS, a minimum routing cost CDS, or a bounded‐diameter CDS. However, the <italic>load‐balance</italic> factor is not considered for CDSs in WSNs. In this paper, a greedy‐based approximation algorithm is proposed to construct load‐balanced CDS in a WSN. More importantly, we propose a new problem: the Load‐balanced Allocate Dominatee problem. Consequently, we propose an optimal centralized algorithm and an efficient probability‐based distributed algorithm to solve the Load‐balanced Allocate Dominatee problem. For a given CDS, the upper and lower bounds of the performance ratio of the distributed algorithm are analyzed in the paper. Through extensive simulations, we demonstrate that our proposed methods extend network lifetime by up to 80% compared with the most recently published CDS construction algorithm. Copyright © 2012 John Wiley &amp; Sons, Ltd.</p> </abstract>