面向林火監(jiān)測的無線傳感器布局規(guī)劃模型

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

（1.中國林業(yè)科學(xué)研究院 資源信息研究所，北京100091；2.吉林農(nóng)業(yè)科技學(xué)院 電氣與工程學(xué)院，吉林 吉林132101）

無線傳感器有自動化、全天候和實時性強等特點，隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，近年已開始在森林防火領(lǐng)域得到廣泛應(yīng)用［1－3］.傳感器監(jiān)測網(wǎng)絡(luò)一般由傳感器節(jié)點、基站和應(yīng)用中心構(gòu)成［4］，傳感器節(jié)點采集數(shù)據(jù)并發(fā)送到基站，由基站傳輸?shù)綉?yīng)用中心.林區(qū)通常面積大、地形復(fù)雜，需要大量的傳感器節(jié)點相互連通形成監(jiān)測網(wǎng)絡(luò).規(guī)劃傳感器布局時由于受成本和生態(tài)環(huán)境等因素限制不能過于密集，而無線信號傳播距離有限又不能過于稀疏，因此必須在滿足監(jiān)測要求的前提下，合理規(guī)劃傳感器的布局.

目前對傳感器布局的規(guī)劃研究，主要集中在如何用較少的節(jié)點滿足覆蓋區(qū)域最有效的要求［5－7］.文獻［8］提出一種基于概率的三維無線傳感器網(wǎng)絡(luò)K－覆蓋控制方法；文獻［9］通過比較正三角形、正方形和正六邊形等部署方法，得出了按正三角形部署節(jié)點最少且有效覆蓋面積最大的結(jié)論；文獻［10］基于目標(biāo)區(qū)域Voronoi劃分的集中式近似算法查找完全覆蓋目標(biāo)區(qū)域所需的最小點集；對于確定的目標(biāo)點，文獻［11］將目標(biāo)區(qū)域網(wǎng)格化后，通過計算目標(biāo)點和周邊節(jié)點的感知概率選擇節(jié)點部署位置；文獻［12］利用遺傳算法對傳感器最優(yōu)覆蓋節(jié)點集進行查找，能以較小的代價找到符合覆蓋條件的節(jié)點集；文獻［13］提出了一種自適應(yīng)多種群的遺傳算法，利用多種群規(guī)劃模型和動態(tài)選擇操作算法，改進了標(biāo)準(zhǔn)遺傳算法早熟收斂和局部搜索能力弱的缺點；文獻［14］證明了借助遺傳算法可以考慮傳感器網(wǎng)絡(luò)生存時間、接收功耗和數(shù)據(jù)融合等多種約束以適應(yīng)實際情況.上述研究多在幾何平面上進行規(guī)劃，未考慮實際地形對傳感器信號的影響，而在實際應(yīng)用中，傳感器的無線信號會受各種障礙物的阻擋和干擾，尤其在林區(qū)，起伏的地形是規(guī)劃過程中必須考慮的因素.

本文提出一種林火傳感器的布局規(guī)劃模型，用遺傳算法求解該模型的近似最優(yōu)解，得到滿足覆蓋度要求最少數(shù)量林火傳感器的布局方法.在遺傳算法進化過程中，根據(jù)實際地形修正傳感器的信號覆蓋范圍，將其作為適應(yīng)性函數(shù)的參數(shù)；對其遺傳選擇和變異過程加以優(yōu)化，防止算法早熟.實驗結(jié)果表明，在有限的計算時間內(nèi)，改進的遺傳算法能收斂于模型的近似最優(yōu)解，并在進化過程中不斷提高種群個體的整體適應(yīng)性.

1 林火傳感器布局規(guī)劃模型

設(shè)C為所有可用傳感器集合，其中有N個傳感器，從N個傳感器中取任意個傳感器的所有組合個數(shù)為M，C′為C的子集，A為C′中所有傳感器地表覆蓋區(qū)域并集的面積總和，a為每個傳感器的地表覆蓋面積，F(xiàn)t為C′中所有傳感器所覆蓋區(qū)域的面積與傳感器個數(shù)的比值，F(xiàn)t的值越大表示C′的布局越好.當(dāng)存在約束條件要求覆蓋面積A不小于A′或使用的傳感器個數(shù)card（C′）不超過K個時，能使目標(biāo)函數(shù)f得到最大值的C′即為最優(yōu)解.規(guī)劃模型如下：

2 基于遺傳算法的求解過程

遺傳算法（genetic algorithm，GA）的求解過程一般為生成初始種群、基因編碼、適應(yīng)性評價、選擇進化和判斷終止幾個步驟［12］.由初始種群開始，計算每代種群中個體的適應(yīng)性，選擇適應(yīng)性高的染色體直接遺傳到下一代，按適應(yīng)性高低選擇個體進行交叉配對或淘汰，再在選出的個體中按一定比例進行變異.在進化過程中，不斷保留優(yōu)秀基因，不斷淘汰劣質(zhì)基因，當(dāng)達到預(yù)設(shè)條件時停止算法，在最后一代符合預(yù)設(shè)條件的個體中選擇適應(yīng)性最好的個體作為最終結(jié)果.

2.1 生成初始種群 先根據(jù)監(jiān)測區(qū)域的外包矩形將其柵格化成一個m×n的柵格矩陣，傳感器可位于監(jiān)測區(qū)域內(nèi)的任一個柵格內(nèi)，坐標(biāo)為（x，y），其中1≤x≤m，1≤y≤n.然后隨機生成1～S組坐標(biāo)作為一個種群的個體（即染色體），其中S≤m×n.在生成T個個體后，得到初始種群p為

2.3 適應(yīng)性評價 林火發(fā)生后通常會由火點向周圍的連續(xù)區(qū)域蔓延，傳感器不需要基于感知距離對林區(qū)進行完整覆蓋，只需以一定間隔布設(shè)，即可在短時間內(nèi)偵測到林火并定位火點.該間隔由傳感器的感知距離、無線網(wǎng)絡(luò)的通訊距離、火點的最短偵測時間要求、傳感器的能耗和持續(xù)工作時長要求等因素決定，通常是由實際情況決定的經(jīng)驗值.本文假設(shè)此間隔為2D，則每個傳感器的覆蓋范圍是以其為圓心，D為半徑的球體.

無線信號的傳播有一定的穿透性，假設(shè)信號在穿透DS厚度的障礙物后，信號衰減L.能保證網(wǎng)絡(luò)通訊的最低信號強度為S′，當(dāng)信號強度S低于S′后通訊失效.無線信號的直線傳播距離也是有限的，為便于計算，假設(shè)其傳播過程中信號無衰減，但傳播距離超過D后信號強度小于S′.如圖1所示，a，b，c，d4個點中，a與信號源間的空間直線距離大于D，d與信號源間的障礙物過厚而不能被信號覆蓋，只有b，c兩點能被信號覆蓋.

假設(shè)某點p與傳感器節(jié)點間的障礙物厚度為DS′，空間直線距離為D，則此點可被信號覆蓋的條件為

圖1 無線信號的傳播Fig.1 Wireless signal propagation

2.4 選擇進化 當(dāng)初始種群、基因編碼和適應(yīng)性評價函數(shù)確定后，先計算初始種群中每個個體的適應(yīng)性，將適應(yīng)性最高的個體直接遺傳到下一代.然后用輪盤賭方法［12］選取其余個體，根據(jù)個體適應(yīng)性高低決定被選中的概率高低.在選中的個體中，設(shè)定一個交叉比例Rc，將輪盤賭算法選中的個體以比例Rc隨機地選為父代，進行兩兩交叉配對.配對時根據(jù)一個小于兩個個體中染色體較短的長度隨機數(shù)，交換位于該隨機數(shù)上的基因，生成新的個體進入下一代.在交叉配對過程中，如果新個體中出現(xiàn)兩個相同基因，則只保留一個基因并作為新個體進入子代.在子代產(chǎn)生完后，再將每個子代的個體乘以變異概率Rv，以Rv的幾率選擇子代的一部分個體進行變異.變異時從基因庫G中隨機選取一個基因，再用這個基因替換發(fā)生變異的染色體上隨機位置的基因，以變異的方式強制產(chǎn)生初始種群中沒有的基因.

2.5 判斷終止 在遺傳算法開始前，必須預(yù)設(shè)首要的和備用的終止條件.本文將規(guī)劃目標(biāo)作為終止條件，進化代數(shù)作為備用條件.假設(shè)規(guī)劃目標(biāo)為覆蓋面積至少為Ae及使用的傳感器數(shù)量不超過Ce個，如果在進化Ng代后仍然達不到則終止算法.終止過程如下：當(dāng)某代種群中出現(xiàn)符合條件A≤Ae且card（C′）≤Ce的個體時，終止算法，在末代種群中取f＝max（Ft）為最終結(jié)果；如果在進化Hg代后仍未出現(xiàn)符合條件A≤Ae且card（C′）≤Ce的個體，則取末代種群中f＝max（Ft）為最終結(jié)果.

3 仿真實驗

使用北京市延慶區(qū)一個12 816m×9 878m的區(qū)域進行實驗，該區(qū)域地形起伏多山，最高海拔1 286m，最低海拔500m.實驗機器的硬件配置為CPU 4核，主頻2.5GHz，內(nèi)存4Gb，操作系統(tǒng)為32位Win7.使用的地形數(shù)據(jù)為該區(qū)域的數(shù)字高程數(shù)據(jù).

假設(shè)傳感器通訊半徑為320m，每穿過一個障礙柵格點信號損失0.8，信號失效強度為0.3.進化過程的交叉比值為0.1，變異率設(shè)置為0.01.設(shè)定停止條件為使用不超過200個傳感器達到75%的覆蓋率，即

在實驗區(qū)內(nèi)隨機投放860個點作為初始種群，進化過程如圖2所示（圖中像素點為4格）.進化到50代時，種群中的個體減少至466個，到100代時個體減少至338個，最終結(jié)果為149個傳感器，覆蓋面積為70.12%.圖2中的圓圈表示為更好地演示整個群體的進化趨勢而使用相同的圓，并不是傳感器真正的覆蓋區(qū)域.

圖2 進化過程Fig.2 Evolutionary process

圖3 傳感器的實際覆蓋區(qū)域Fig.3 Actual area coverage of sensor

圖4 整體適應(yīng)性變化Fig.4 Change of average adaptability of population

綜上所述，本文建立了一個林火傳感器規(guī)劃模型，在考慮地形因素的情況下基于遺傳算法在一定約束下將求該模型的近似最優(yōu)解作為最終規(guī)劃方案.仿真實驗表明，種群的整體適應(yīng)性不斷趨于最優(yōu)解，在有限時間內(nèi)能快速得到符合或接近預(yù)設(shè)條件的解集，因此，遺傳算法適用于地形相關(guān)度較高的林火傳感器布局規(guī)劃.

［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.（陸志平，秦會斌，王春芳.無線傳感器網(wǎng)絡(luò)在森林火災(zāi)監(jiān)測中的應(yīng)用 ［J］.杭州電子科技大學(xué)學(xué)報，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無線傳感器網(wǎng)絡(luò)的森林火災(zāi)監(jiān)測系統(tǒng)的研究 ［J］.北京林業(yè)大學(xué)學(xué)報，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.（趙凌，劉全利，王越，等.基于無線傳感器網(wǎng)絡(luò)的森林火險監(jiān)測系統(tǒng)的設(shè)計［J］.重慶工學(xué)院學(xué)報：自然科學(xué)版，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.（張寧，韓海.用于森林火災(zāi)監(jiān)測和救災(zāi)的無線傳感器網(wǎng)絡(luò) ［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的無線傳感器網(wǎng)絡(luò)通信覆蓋研究 ［J］.傳感技術(shù)學(xué)報，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.（蔣鵬，陳峰.基于概率的三維無線傳感器網(wǎng)絡(luò)K－覆蓋控制方法 ［J］.傳感技術(shù)學(xué)報，2009，22（5）：706－711.）

［9］LI Hai－h(huán)ua，F(xiàn)AN Juan，CHEN Li.Application of Grid Method in Deployment of Wireless Sensor Networks［J］.Transducer and Microsystem Technologies，2012，31（3）：150－152.（李海華，范娟，陳利.網(wǎng)格法在無線傳感器網(wǎng)絡(luò)部署中的應(yīng)用 ［J］.傳感器與微系統(tǒng)，2012，31（3）：150－152.）

［10］JIANG Jie，F(xiàn)ANG 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.（蔣杰，方力，張鶴穎，等.無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法 ［J］.軟件學(xué)報，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.（郭秀明，趙春江，楊信廷，等.基于網(wǎng)格掃描的實現(xiàn)目標(biāo)點覆蓋的確定性傳感器節(jié)點部署方法［J］.傳感技術(shù)學(xué)報，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.（賈杰，陳劍，常桂然，等.無線傳感器網(wǎng)絡(luò)中最優(yōu)覆蓋節(jié)點集的求解算法 ［J］.東北大學(xué)學(xué)報：自然科學(xué)版，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.（劉元寧，王剛，朱曉冬，等.基于自適應(yīng)多種群遺傳算法的特征選擇 ［J］.吉林大學(xué)學(xué)報：工學(xué)版，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.（潘晏濤，劉作偉，張強.基于遺傳算法求解傳感器網(wǎng)絡(luò)生存時間優(yōu)化問題的設(shè)計及比較 ［J］.吉林大學(xué)學(xué)報：工學(xué)版，2007，37（4）：865－869.）