期刊
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
卷 23, 期 8, 页码 1528-1535出版社
IEEE COMPUTER SOC
DOI: 10.1109/TPDS.2011.305
关键词
Wireless sensor networks (WSNs); backbone scheduling; sleep scheduling; virtual backbone; energy-delay tradeoff; connected dominating set; complexity analysis
资金
- US National Science Foundation (NSF) [ECCS 1128209, CNS 10655444, CCF 1028167, CNS 0948184, CCF 0830289]
- National Basic Research Program of China (973) [2009CB320705]
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [1138963, 1065444] Funding Source: National Science Foundation
Wireless Sensor Networks (WSNs) are key for various applications that involve long-term and low-cost monitoring and actuating. In these applications, sensor nodes use batteries as the sole energy source. Therefore, energy efficiency becomes critical. We observe that many WSN applications require redundant sensor nodes to achieve fault tolerance and Quality of Service (QoS) of the sensing. However, the same redundancy may not be necessary for multihop communication because of the light traffic load and the stable wireless links. In this paper, we present a novel sleep-scheduling technique called Virtual Backbone Scheduling (VBS). VBS is designed for WSNs has redundant sensor nodes. VBS forms multiple overlapped backbones which work alternatively to prolong the network lifetime. In VBS, traffic is only forwarded by backbone sensor nodes, and the rest of the sensor nodes turn off their radios to save energy. The rotation of multiple backbones makes sure that the energy consumption of all sensor nodes is balanced, which fully utilizes the energy and achieves a longer network lifetime compared to the existing techniques. The scheduling problem of VBS is formulated as the Maximum Lifetime Backbone Scheduling (MLBS) problem. Since the MLBS problem is NP-hard, we propose approximation algorithms based on the Schedule Transition Graph (STG) and Virtual Scheduling Graph (VSG). We also present an Iterative Local Replacement (ILR) scheme as a distributed implementation. Theoretical analyses and simulation studies verify that VBS is superior to the existing techniques.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据