巷道环境中继节点部署近似算法  

Approximate algorithms of relay node deployment in roadway environment

作　　者：王群[1,2] 王潜平[1] 来梁丽[1] 

机构地区：[1]中国矿业大学计算机学院,江苏徐州221116 [2]中国矿业大学图书馆,江苏徐州221116

出　　处：《计算机工程与设计》2012年第9期3351-3355,共5页Computer Engineering and Design

摘　　要：为延长巷道中无线传感器网络的生存周期,减少感知节点进行长距离传输信息消耗能量,提出了在位置受限的巷道中部署最少数目中继节点的近似算法ACRNP。利用线性规划计算得到部署中继节点数目的下界(即最优解),并通过大量数值实验将近似算法与最优解进行比较。模拟算例表明,该近似算法的结果非常接近于最优解。据我们所知,我们是第一个将受限的中继节点部署在狭长环境中,且该近似算法近似比率为1。To prolong the network lifetime,and reduce the energy for long distance transmission,an approximate algorithm ACRNP is proposed,which is concerned with placing a minimum number of location restrained relay nodes into a roadway wireless sensor network.Linear program is used to obtain the lower critical value（optimum solution）.Result obtained by extensive experimental simulations using the approximate algorithm is very close to optimal solution.As we known,it is the first time to deploy the restrained relay nodes in the slit environment and the approximation ratio of this algorithm is 1.

关 键 词：巷道 中继 近似算法 线性规划 无线传感器网络 

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