李惺穎，黃水生，謝陽(yáng)生，唐小明，王淑艷

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

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

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

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

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

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

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

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

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

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

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

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

圖1 無線信號(hào)的傳播Fig.1 Wireless signal propagation

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

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

3 仿真實(shí)驗(yàn)

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

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

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

圖2 進(jìn)化過程Fig.2 Evolutionary process

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

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

綜上所述，本文建立了一個(gè)林火傳感器規(guī)劃模型，在考慮地形因素的情況下基于遺傳算法在一定約束下將求該模型的近似最優(yōu)解作為最終規(guī)劃方案.仿真實(shí)驗(yàn)表明，種群的整體適應(yīng)性不斷趨于最優(yōu)解，在有限時(shí)間內(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.（陸志平，秦會(huì)斌，王春芳.無線傳感器網(wǎng)絡(luò)在森林火災(zāi)監(jiān)測(cè)中的應(yīng)用 ［J］.杭州電子科技大學(xué)學(xué)報(bào)，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.（張軍國(guó)，李文彬，韓寧，等.基于ZigBee無線傳感器網(wǎng)絡(luò)的森林火災(zāi)監(jiān)測(cè)系統(tǒng)的研究 ［J］.北京林業(yè)大學(xué)學(xué)報(bào)，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ò)的森林火險(xiǎn)監(jiān)測(cè)系統(tǒng)的設(shè)計(jì)［J］.重慶工學(xué)院學(xué)報(bào)：自然科學(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)測(cè)和救災(zāi)的無線傳感器網(wǎng)絡(luò) ［J］.微計(jì)算機(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.（聶云峰，舒堅(jiān)，龔佳杰，等.基于RSSI的無線傳感器網(wǎng)絡(luò)通信覆蓋研究 ［J］.傳感技術(shù)學(xué)報(bào)，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é)報(bào)，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é)報(bào)，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)格掃描的實(shí)現(xiàn)目標(biāo)點(diǎn)覆蓋的確定性傳感器節(jié)點(diǎn)部署方法［J］.傳感技術(shù)學(xué)報(bào)，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é)點(diǎn)集的求解算法 ［J］.東北大學(xué)學(xué)報(bào)：自然科學(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é)報(bào)：工學(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.（潘晏濤，劉作偉，張強(qiáng).基于遺傳算法求解傳感器網(wǎng)絡(luò)生存時(shí)間優(yōu)化問題的設(shè)計(jì)及比較 ［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2007，37（4）：865－869.）