面向数量最少化的双层WSN中继节点部署算法  

Minimum number oriented relay node deployment algorithm in two-tiered WSN

作　　者：苗春雨[1,2] 陈丽娜[1] 戴国勇[2] 杨帆[2] 陈庆章[2] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004 [2]浙江工业大学计算机科学与技术学院,浙江杭州310023

出　　处：《通信学报》2016年第4期139-148,共10页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61379023;No.61502431);浙江省计算机科学与技术重中之重学科(浙江师范大学)基金资助项目(No.ZC323014074);浙江省科技厅公益性技术应用研究计划基金资助项目(No.2015C33060)~~

摘　　要：提出2种算法,目标是在监测区域部署中继节点,以便所有的传感节点都能和至少一个中继节点进行通信,同时保证中继节点数目最小化。整数线性规划最优解算法是对已选择出的CRegions通过数学上的整数线性规划的方法找到部署中继节点的最佳区域;传感网络规模较大时,提出启发式算法,将每一次排序后含传感节点个数最多的集合作为部署区域,经过多次循环排序后近似的找到部署中继节点的最佳位置。最后通过与2个同类算法在相同参数环境下进行仿真实验,比较仿真结果证明整数线性规划最优解算法及启发式算法在覆盖所有传感节点的前提下,部署中继节点最小化的性能较好,并且其部署时间也在可以接受的范围之内。Aiming at minimizing the number of relay nodes distributed in the sensing area while keeping the feasible communication with at least one relay node for every sensor node, two algorithms（i.e. the integral linear programming optimal algorithm and the heuristic algorithm） were proposed. First, the integral linear programming optimal algorithm was designed to find the best region of deploying relay nodes within candidate regions through integer linear programming. In the large-scale wireless sensor network, the heuristic algorithm was proposed that found the best deployment region through iteratively updating the deployment area including the most relay nodes. Finally, simulation results show that the two proposed algorithms can minimize the number of relay nodes needed with the guarantee of serving all sensor nodes.

关 键 词：中继节点 部署算法 整数线性规划 启发式算法 节点覆盖 

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