Multichannel Scheduling and Spanning Trees: Throughput-Delay Tradeoff for Fast Data Collection in Sensor Networks

作者：Ghosh Amitabha^*; Incel Ozlem Durmaz; Kumar V S Anil; Krishnamachari Bhaskar

来源：IEEE/ACM Transactions on Networking, 2011, 19(6): 1731-1744.

DOI：10.1109/TNET.2011.2146273

• Approximation algorithms
• convergecast
• multiple channels
• routing trees
• time-division multiple access (TDMA) scheduling

We investigate the tradeoff between two mutually conflicting performance objectives-throughput and delay-for fast, periodic data collection in tree-based sensor networks arbitrarily deployed in 2-D. Two primary factors that affect the data collection rate (throughput) and timeliness (delay) are: 1) efficiency of the link scheduling protocol, and 2) structure of the routing tree in terms of its node degrees and radius. In this paper, we utilize multiple frequency channels and design an efficient link scheduling protocol that gives a constant factor approximation on the optimal throughput in delivering aggregated data from all the nodes to the sink. To minimize the maximum delay subject to a given throughput bound, we also design an (alpha, beta)-bicriteria approximation algorithm to construct a Bounded-Degree Minimum-Radius Spanning Tree, with the radius of the tree at most beta times the minimum possible radius for a given degree bound Delta*, and the degree of any node at most Delta* + alpha, where alpha and beta are positive constants. Lastly, we evaluate the efficiency of our algorithms on different types of spanning trees and show that multichannel scheduling, combined with optimal routing topologies, can achieve the best of both worlds in terms of maximizing the aggregated data collection rate and minimizing the maximum packet delay.

• 出版日期2011-12
• 单位美国弗吉尼亚理工大学(Virginia Tech)