面向林火监测的无线传感器布局规划模型

李惺颖，黄水生，谢阳生，唐小明，王淑艳

（1.中国林业科学研究院 资源信息研究所，北京100091；2.吉林农业科技学院 电气与工程学院，吉林 吉林132101）

无线传感器有自动化、全天候和实时性强等特点，随着物联网技术的发展，近年已开始在森林防火领域得到广泛应用［1－3］.传感器监测网络一般由传感器节点、基站和应用中心构成［4］，传感器节点采集数据并发送到基站，由基站传输到应用中心.林区通常面积大、地形复杂，需要大量的传感器节点相互连通形成监测网络.规划传感器布局时由于受成本和生态环境等因素限制不能过于密集，而无线信号传播距离有限又不能过于稀疏，因此必须在满足监测要求的前提下，合理规划传感器的布局.

目前对传感器布局的规划研究，主要集中在如何用较少的节点满足覆盖区域最有效的要求［5－7］.文献［8］提出一种基于概率的三维无线传感器网络K－覆盖控制方法；文献［9］通过比较正三角形、正方形和正六边形等部署方法，得出了按正三角形部署节点最少且有效覆盖面积最大的结论；文献［10］基于目标区域Voronoi划分的集中式近似算法查找完全覆盖目标区域所需的最小点集；对于确定的目标点，文献［11］将目标区域网格化后，通过计算目标点和周边节点的感知概率选择节点部署位置；文献［12］利用遗传算法对传感器最优覆盖节点集进行查找，能以较小的代价找到符合覆盖条件的节点集；文献［13］提出了一种自适应多种群的遗传算法，利用多种群规划模型和动态选择操作算法，改进了标准遗传算法早熟收敛和局部搜索能力弱的缺点；文献［14］证明了借助遗传算法可以考虑传感器网络生存时间、接收功耗和数据融合等多种约束以适应实际情况.上述研究多在几何平面上进行规划，未考虑实际地形对传感器信号的影响，而在实际应用中，传感器的无线信号会受各种障碍物的阻挡和干扰，尤其在林区，起伏的地形是规划过程中必须考虑的因素.

本文提出一种林火传感器的布局规划模型，用遗传算法求解该模型的近似最优解，得到满足覆盖度要求最少数量林火传感器的布局方法.在遗传算法进化过程中，根据实际地形修正传感器的信号覆盖范围，将其作为适应性函数的参数；对其遗传选择和变异过程加以优化，防止算法早熟.实验结果表明，在有限的计算时间内，改进的遗传算法能收敛于模型的近似最优解，并在进化过程中不断提高种群个体的整体适应性.

1 林火传感器布局规划模型

设C为所有可用传感器集合，其中有N个传感器，从N个传感器中取任意个传感器的所有组合个数为M，C′为C的子集，A为C′中所有传感器地表覆盖区域并集的面积总和，a为每个传感器的地表覆盖面积，Ft为C′中所有传感器所覆盖区域的面积与传感器个数的比值，Ft的值越大表示C′的布局越好.当存在约束条件要求覆盖面积A不小于A′或使用的传感器个数card（C′）不超过K个时，能使目标函数f得到最大值的C′即为最优解.规划模型如下：

2 基于遗传算法的求解过程

遗传算法（genetic algorithm，GA）的求解过程一般为生成初始种群、基因编码、适应性评价、选择进化和判断终止几个步骤［12］.由初始种群开始，计算每代种群中个体的适应性，选择适应性高的染色体直接遗传到下一代，按适应性高低选择个体进行交叉配对或淘汰，再在选出的个体中按一定比例进行变异.在进化过程中，不断保留优秀基因，不断淘汰劣质基因，当达到预设条件时停止算法，在最后一代符合预设条件的个体中选择适应性最好的个体作为最终结果.

2.1 生成初始种群 先根据监测区域的外包矩形将其栅格化成一个m×n的栅格矩阵，传感器可位于监测区域内的任一个栅格内，坐标为（x，y），其中1≤x≤m，1≤y≤n.然后随机生成1～S组坐标作为一个种群的个体（即染色体），其中S≤m×n.在生成T个个体后，得到初始种群p为

2.3 适应性评价 林火发生后通常会由火点向周围的连续区域蔓延，传感器不需要基于感知距离对林区进行完整覆盖，只需以一定间隔布设，即可在短时间内侦测到林火并定位火点.该间隔由传感器的感知距离、无线网络的通讯距离、火点的最短侦测时间要求、传感器的能耗和持续工作时长要求等因素决定，通常是由实际情况决定的经验值.本文假设此间隔为2D，则每个传感器的覆盖范围是以其为圆心，D为半径的球体.

无线信号的传播有一定的穿透性，假设信号在穿透DS厚度的障碍物后，信号衰减L.能保证网络通讯的最低信号强度为S′，当信号强度S低于S′后通讯失效.无线信号的直线传播距离也是有限的，为便于计算，假设其传播过程中信号无衰减，但传播距离超过D后信号强度小于S′.如图1所示，a，b，c，d4个点中，a与信号源间的空间直线距离大于D，d与信号源间的障碍物过厚而不能被信号覆盖，只有b，c两点能被信号覆盖.

假设某点p与传感器节点间的障碍物厚度为DS′，空间直线距离为D，则此点可被信号覆盖的条件为

图1 无线信号的传播Fig.1 Wireless signal propagation

2.4 选择进化 当初始种群、基因编码和适应性评价函数确定后，先计算初始种群中每个个体的适应性，将适应性最高的个体直接遗传到下一代.然后用轮盘赌方法［12］选取其余个体，根据个体适应性高低决定被选中的概率高低.在选中的个体中，设定一个交叉比例Rc，将轮盘赌算法选中的个体以比例Rc随机地选为父代，进行两两交叉配对.配对时根据一个小于两个个体中染色体较短的长度随机数，交换位于该随机数上的基因，生成新的个体进入下一代.在交叉配对过程中，如果新个体中出现两个相同基因，则只保留一个基因并作为新个体进入子代.在子代产生完后，再将每个子代的个体乘以变异概率Rv，以Rv的几率选择子代的一部分个体进行变异.变异时从基因库G中随机选取一个基因，再用这个基因替换发生变异的染色体上随机位置的基因，以变异的方式强制产生初始种群中没有的基因.

2.5 判断终止 在遗传算法开始前，必须预设首要的和备用的终止条件.本文将规划目标作为终止条件，进化代数作为备用条件.假设规划目标为覆盖面积至少为Ae及使用的传感器数量不超过Ce个，如果在进化Ng代后仍然达不到则终止算法.终止过程如下：当某代种群中出现符合条件A≤Ae且card（C′）≤Ce的个体时，终止算法，在末代种群中取f＝max（Ft）为最终结果；如果在进化Hg代后仍未出现符合条件A≤Ae且card（C′）≤Ce的个体，则取末代种群中f＝max（Ft）为最终结果.

3 仿真实验

使用北京市延庆区一个12 816m×9 878m的区域进行实验，该区域地形起伏多山，最高海拔1 286m，最低海拔500m.实验机器的硬件配置为CPU 4核，主频2.5GHz，内存4Gb，操作系统为32位Win7.使用的地形数据为该区域的数字高程数据.

假设传感器通讯半径为320m，每穿过一个障碍栅格点信号损失0.8，信号失效强度为0.3.进化过程的交叉比值为0.1，变异率设置为0.01.设定停止条件为使用不超过200个传感器达到75%的覆盖率，即

在实验区内随机投放860个点作为初始种群，进化过程如图2所示（图中像素点为4格）.进化到50代时，种群中的个体减少至466个，到100代时个体减少至338个，最终结果为149个传感器，覆盖面积为70.12%.图2中的圆圈表示为更好地演示整个群体的进化趋势而使用相同的圆，并不是传感器真正的覆盖区域.

图2 进化过程Fig.2 Evolutionary process

图3 传感器的实际覆盖区域Fig.3 Actual area coverage of sensor

图4 整体适应性变化Fig.4 Change of average adaptability of population

综上所述，本文建立了一个林火传感器规划模型，在考虑地形因素的情况下基于遗传算法在一定约束下将求该模型的近似最优解作为最终规划方案.仿真实验表明，种群的整体适应性不断趋于最优解，在有限时间内能快速得到符合或接近预设条件的解集，因此，遗传算法适用于地形相关度较高的林火传感器布局规划.

［1］LU Zhi－ping，QIN Hui－bin，WANG Chun－fang.Application of Wireless Sensor Networks for Monitoring Forest Fire［J］.Journal of Hangzhou Dianzi University，2006，26（5）：48－51.（陆志平，秦会斌，王春芳.无线传感器网络在森林火灾监测中的应用 ［J］.杭州电子科技大学学报，2006，26（5）：48－51.）

［2］ZHANG Jun－guo，LI Wen－bin，HAN Ning，et al.Forest Fire Detection System Based on ZigBee Wireless Sensor Network［J］.Journal of Beijing Forestry University，2007，29（4）：41－45.（张军国，李文彬，韩宁，等.基于ZigBee无线传感器网络的森林火灾监测系统的研究 ［J］.北京林业大学学报，2007，29（4）：41－45.）

［3］ZHAO Ling，LIU Quan－li，WANG Yue，et al.Design of Forest Fire Monitoring System Based on Wireless Sensor Networks［J］.Journal of Chongqing Institute of Technology：Natural Science，2009，23（2）：157－161.（赵凌，刘全利，王越，等.基于无线传感器网络的森林火险监测系统的设计［J］.重庆工学院学报：自然科学版，2009，23（2）：157－161.）

［4］ZHANG Ning，HAN Hai.Using WSN for Forest Fire Monitoring and Rescue Application［J］.Microcomputer Information，2008，24（10）：169－171.（张宁，韩海.用于森林火灾监测和救灾的无线传感器网络 ［J］.微计算机信息，2008，24（10）：169－171.）

［5］NIE Yun－feng，SHU Jian，GONG Jia－jie，et al.Researches on Communication Coverage for Wireless Sensor Network Based on RSSI［J］.Chinese Journal of Sensors and Actuators，2011，24（7）：1066－1069.（聂云峰，舒坚，龚佳杰，等.基于RSSI的无线传感器网络通信覆盖研究 ［J］.传感技术学报，2011，24（7）：1066－1069.）

［6］YE Fan，Zhong G，Cheng J，et al.PEAS：A Robust Energy Conserving Protocol for Long－Lived Sensor Networks［C］／／Proceedings on 23rd International Conference on Distributed Computing Systems.Providence：IEEE Press，2003：28－37.

［7］WANG Xiao－rui，XING Guo－ling，ZHANG Yuan－fang，et al.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks ［C］／／Proceedings of the First International Conference on Embedded Networked Sensor Systems.New York：ACM Press，2003：28－39.

［8］JIANG Peng，CHEN Feng.Probability－Based K－Coverage Control Approach for Three－Dimensional Wireless Sensor Networks［J］.Chinese Journal of Sensors and Actuators，2009，22（5）：706－711.（蒋鹏，陈峰.基于概率的三维无线传感器网络K－覆盖控制方法 ［J］.传感技术学报，2009，22（5）：706－711.）

［9］LI Hai－hua，FAN Juan，CHEN Li.Application of Grid Method in Deployment of Wireless Sensor Networks［J］.Transducer and Microsystem Technologies，2012，31（3）：150－152.（李海华，范娟，陈利.网格法在无线传感器网络部署中的应用 ［J］.传感器与微系统，2012，31（3）：150－152.）

［10］JIANG Jie，FANG Li，ZHANG He－ying，et al.An Algorithm for Minimal Connected Cover Set Problem in Wireless Sensor Networks［J］.Journal of Software，2006，17（2）：175－184.（蒋杰，方力，张鹤颖，等.无线传感器网络最小连通覆盖集问题求解算法 ［J］.软件学报，2006，17（2）：175－184.）

［11］GUO Xiu－ming，ZHAO Chun－jiang，YANG Xin－ting，et al.A Deterministic Sensor Node Deployment Method with Target Coverage Based on Grid Scan［J］.Chinese Journal of Sensors and Actuators，2012，25（1）：104－109.（郭秀明，赵春江，杨信廷，等.基于网格扫描的实现目标点覆盖的确定性传感器节点部署方法［J］.传感技术学报，2012，25（1）：104－109.）

［12］JIA Jie，CHEN Jian，CHANG Gui－ran，et al.Optimal Coverage Algorithm of Sensor Nodes Set Selection in Wireless Sensor Network［J］.Journal of Northeastern University：Natural Science，2007，28（11）：1560－1563.（贾杰，陈剑，常桂然，等.无线传感器网络中最优覆盖节点集的求解算法 ［J］.东北大学学报：自然科学版，2007，28（11）：1560－1563.）

［13］LIU Yuan－ning，WANG Gang，ZHU Xiao－dong，et al.Feature Selection Based on Adaptive Multi－population Genetic Algorithm ［J］.Journal of Jilin University：Engineering and Technology Edition，2011，41（6）：1690－1693.（刘元宁，王刚，朱晓冬，等.基于自适应多种群遗传算法的特征选择 ［J］.吉林大学学报：工学版，2011，41（6）：1690－1693.）

［14］PAN Yan－tao，LIU Zuo－wei，ZHANG Qiang.Genetic Algorithm Design and Analysis for Lifetime Optimization of Sensor Networks［J］.Journal of Jilin University：Engineering and Technology Edition，2007，37（4）：865－869.（潘晏涛，刘作伟，张强.基于遗传算法求解传感器网络生存时间优化问题的设计及比较 ［J］.吉林大学学报：工学版，2007，37（4）：865－869.）