基于分组的分布式节点调度覆盖算法  

A Subset-Based Coverage-Preserving Distributed Scheduling Algorithm

作　　者：李小龙[1] 林亚平[1,2] 胡玉鹏[1] 刘永和 

机构地区：[1]湖南大学计算机与通信学院,长沙410082 [2]湖南大学软件学院,长沙410082 [3]德州大学阿灵顿分校计算机科学与工程系,阿灵顿76019

出　　处：《计算机研究与发展》2008年第1期180-187,共8页Journal of Computer Research and Development

基　　金：国家“八六三”高技术研究发展计划基金项目(2006AA01Z227);湖南省自然科学基金重点项目(06JJ20049);湖南省教育厅科学研究优秀青年基金项目(06B047)~~

摘　　要：当部署的传感器节点服从随机分布时,现有的基于分组的节点调度算法不能保证各个组内的节点均匀分布在目标区域.基于以上原因,建立了极大相似分布模型,并提出了极大相似分布的一种近似求解算法:基于分组的分布式节点调度覆盖算法.算法仅需要簇内的节点维持时钟同步,簇之间节点的时钟异步对于覆盖效果的影响可以忽略,因此适用于难以维持整个网络保持时间同步的大型传感器网络.此外,给出了在节点随机分布的条件下,采用分组调度时平均覆盖率的理论上界值.仿真实验表明,提出的这种算法能使各个组内的传感器节点较为均匀地分布在目标区域,获得的平均覆盖率接近于上界值.Recent research has found that management of node duty circles, termed sensor scheduling, is able to save significant energy and prolong the lifetime of sensor networks. Sensor scheduling schemes could be categorized into two types in terms of scheduling features： round-based scheduling scheme and subsetbased scheduling scheme respectively. Compared with round-based scheduling scheme, subset-based scheduling scheme is an effective solution because it is only carried out once after deployment. When sensor nodes are randomly deployed to a target region, existing subset-based scheduling algorithms can not guarantee that any subset of sensor nodes is uniformly distributed over the target region. Motivated by these reasons, firstly a maximum similarity distribution model is set up and an approximation algorithm, the subset-based coverage-preserving distributed scheduling algorithm is proposed. The algorithm is robust to clock asynchrony of nodes in different clusters, hence it is applicable to large-scale sensor networks, for which precise time synchronization is very hard. In addition, the analytical results for the theoretical upper bound of average coverage rate are presented, while nodes are randomly distributed over the target region. The experimental simulations demonstrate that this algorithm has the ability that sensor nodes in each subset are rather uniformly distributed over the target area, and available coverage rate approaches the upper bound.

关 键 词：传感器网络 覆盖 节点调度 分组 极大相似分布 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]