面向林火監測的無線傳感器布局規劃模型

李惺穎，黃水生，謝陽生，唐小明，王淑艷

（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.）