基于遺傳算法的農業無線傳感器節點部署算法設計

張伯琰，鄒騰躍

(福建農林大學機電工程學院，福建 福州 350002)

0 引言

利用農業無線傳感器網絡(Agricultural Wireless Sensor Network，AWSN)精確獲取農作物生長環境信息是現代農業發展的重要技術手段，農業無線傳感器網絡通常由多個無線傳感器節點(Wireless Sensor Network Nodes，WSNN)組成，組成傳感器網絡的傳感器檢測半徑大多相同，傳感器的布局會直接影響到農業無線傳感器網絡的成本、效率和使用壽命。在無線傳感器網絡部署階段，傳感器的檢測范圍為圓形，多個傳感器進行部署，不可避免地產生重疊區域。若傳感器數量過多，檢測范圍重疊程度較大，會導致傳感器檢測數據的冗余，數據處理煩瑣，無線傳感器網絡系統整體電量耗能增加，縮短無線傳感器網絡壽命[1]。農業無線傳感網絡設置環境復雜，維護困難，大大增加了農業無線傳感器網絡的安裝維護成本。

孫宇晶[2]提出了一種基于感知模型的傳感器部署算法，感知模型與遺傳算法相結合，實現了傳感器節點部署的遺傳求解過程。程龍等[3]就無線傳感器的等邊部署方法進行了討論，將不同條件下的等邊多邊形部署方法做了仿真，并得出不同條件下使用不同等邊多邊形部署的結論。許佳慧等[4]進行了基于網絡掃描算法估算傳感器位置的仿真試驗。吳傳程等[5]提出了一種基于區域面積覆蓋強度的虛擬力覆蓋優化算法，有效解決了不同傳感器數量情況下的節點部署問題，但存在大面積重疊現象。針對農業無線傳感器網絡節點部署，本文提出一種基于離散計算的遺傳算法部署策略。

1 問題描述與模型建立

1.1 問題描述

隨著智能技術的發展，智慧農業成為熱點問題。基于大數據的智慧農業發展迅速，物聯網技術在智慧農業中發揮了極大的作用[6]。物聯網技術可以監控農業的生長情況和環境條件，并構建信息交流網絡平臺，實現信息的互通與交流[7]。合理的無線傳感器部署算法可以延遲黑洞效應的產生時間，有效提升無線傳感器網絡生命周期[8]。傳統的農業無線傳感器部署通常采用正多邊形的部署辦法，可以實現檢測區域的高覆蓋率，但是這會使傳感器數量大大增加，同時因為傳感器數量的增加，使得重疊面積增加，冗余數據也會隨之增加，進而促進了節點的衰亡。

1.2 模型建立

為了改進上述問題，在確保高覆蓋率的同時，減少傳感器數量，設計了一種基于改進遺傳算法的農業無線傳感器網絡節點部署算法。本算法以舍差取優點策略作為算子選擇方案。用整個分布圖的節點坐標作為遺傳個體，每個個體的染色體包含一個多點坐標。本設計沒有使用二進制編碼，而是直接對染色體進行保留或舍棄操作，利用圖形計算，更加精確地計算相關參數。假設傳感器檢測范圍都為半徑相同的圓形區域，對檢測半徑為7 m的傳感器檢測范圍圓S進行細分為1 m/pixel離散的示意如圖1所示。

圖1 傳感器檢測范圍圓離散化Fig.1 Discretized circle of sensor detection range

(1)

式中P(x，y)——離散化后的圓(x，y)坐標的值

r——待離散化圓的半徑

當P(x，y)與圓心O的距離小于等于半徑時，P(x，y)=1，否則P(x，y)=0。為了方便計算，并沒有直接賦予顏色值，而是用1代表覆蓋范圍，0代表未被覆蓋。

代數計算無線傳感器檢測圓面積公式為

S=π·r2

(2)

式中S——傳感器檢測范圍面積

經過離散化后，計算無線傳感器檢測范圍圓面積公式為

(3)

式中S′——離散化后圓的面積

針對此模型給出以下定義。

定義1：單層有效覆蓋面積，在一個無線傳感器的覆蓋范圍里，除去其他傳感器造成的重疊區域部分的面積。

定義2：覆蓋值，樣本區域被分割為多個長寬各1 m的區域，當該區域被n個傳感器覆蓋時，其覆蓋值為n。該值用于表達每塊區域被傳感器覆蓋的程度。

定義3：覆蓋率，表示樣本被傳感器覆蓋的程度。

如圖2所示，當兩個節點的覆蓋面積發生重疊，執行離散圓的加和操作，基因表達模型公式為

圖2 兩個節點檢測范圍發生重疊示意Fig.2 Schematic diagram of overlapping monitoring range of two nodes

p(xr+x，yr+y)n+1=p(xr+x，yr+y)n+P(r+x，r+y)x，y∈[-r，r]

(4)

式中p(x，y)——樣本中點(x，y)坐標的值

按照本算法擬對基因為{(1，2)，(6，9)，(11，1)，r=7}的個體進行基因表達，表達模型過程如圖3、圖4和圖5所示。

圖3 基因表達模型過程步驟一Fig.3 Gene expression model process′s step one

圖4 基因表達模型過程步驟二Fig.4 Gene expression model process′s step two

圖5 基因表達模型過程步驟三Fig.5 Gene expression model process′s step three

如圖3所示，首先將離散化的傳感器檢測范圍圓按照染色體記錄的坐標映射到畫布上，對應位置覆蓋值相加，傳感器檢測范圍圓內覆蓋值為0+1=1。超出邊界部分不予記錄。

表達完染色體1后表達染色體2，同樣也是對應位置相加，兩圓重疊部分的值為2

最后表達染色體3，對應位置相加，3個圓重疊部分值為3；至此本算法完成了該基因的表達工作。

2 算法設計

2.1 算法設計思想

在一定的試驗條件下，無線傳感器網絡節點的部署是個非確定多項式問題，該問題不確定能否在多項式時間內找到答案，傳統估計計算覆蓋率的方法為樣本區域中劃分出n個采樣點，然后通過統計計算這幾個采樣點的覆蓋情況大致得出覆蓋率情況[9]。這種辦法原理可行，但誤差較大，容易出現極端情況。本算法用離散化的方法，取代原先的代數計算，且比粗略估計覆蓋率的方法更為準確，不易出現極端誤差，算法易懂，通過遺傳算法優勝劣汰的特點，可以得出比較好的部署方案。本算法類似遺傳算法，將覆蓋率作為適應度函數可以較為直觀地觀測其收斂過程，不同于以往遺傳算法的是，本算法在產生新的父代時并不是先產生固定數量的子代后擇優產生下一代的父代，而是在產生子代地過程中，若子代的適應度高于父代時，直接代替上代父代作為新的父代。由于產生新的父代適應度總是高于上一代父代，且逐步趨于一個極限值，所以本算法是收斂的。由于在產生子代的配對樣本的坐標是隨機產生的，相當于一部分子代全部變異，所以本文未設置另外的變異概率。同時遍歷樣本中每個區域的覆蓋值，可直接獲得該區域的傳感器覆蓋情況。

2.2 算法設計步驟

步驟一：建立一個樣本個體，設定該樣本個體中染色體數量即無線傳感器數量N，并隨機生成含傳感器坐標的N個染色體。

步驟二：產生首次遺傳的父代之一。隨機產生K個樣本進行兩兩相融。每次先產生染色體數目為2N的樣本，通過圖像處理的辦法將基因表達出來，保留覆蓋率最大的二倍體樣本。

步驟三：計算每個傳感器節點染色體的單層有效覆蓋面積，將單層覆蓋面積最小的染色體移除，重復此移除過程，直到該樣本中保留最后的N個染色體。

步驟四：算法隨機產生一個新的樣本，新樣本與上一步驟產生的父代做雜交，先產生染色體數目為2N的樣本，通過圖像處理的辦法將基因表達出來，接著重復步驟三，產生的新個體與父代做比較，若適應度高于父代則代替原父代成為新的父代，否則舍棄該子代重復步驟四，直到適應度在很長一段時間里不再發生變化，到達了要求的適應度或者達到了循環次數即表示完成了算法過程。

主程序算法流程如圖6所示。

圖6 主程序算法流程Fig.6 Flow chart of main program algorithm

K的值取5，使得初始父代有較高的覆蓋率，減少算法循環次數，雜交算法流程如圖7所示。

圖7 雜交算法流程Fig.7 Flow chart of hybrid algorithm

本算法設計雜交時先形成二倍體，然后表達該二倍體，再剔除差的基因，重復此循環，直到新形成的個體，染色體數目正常，至此視為產生了符合要求的子代。

3 仿真試驗與數據分析

將試驗樣本條件設置為長和寬均為100 m，細分0.1 m/pixel；設置所有傳感器檢測圓半徑r=12 m，即傳感器檢測圓半徑為120像素；設置染色體(無線傳感器節點)個數N分別為25、28、30和32個，單代雜交最大次數為19時，對此算法進行仿真。

無線傳感器節點數目為25、28、31和32個時，通過本算法得到的無線傳感器網絡部署如圖8所示，對應的適應度曲線如圖9所示。孫宇晶[2]的研究中，長和寬各90 m的環境下，傳感器半徑12 m、覆蓋率達到92%時，傳感器最少需要35個；而通過本算法，在長和寬均為100 m的情況下僅僅需要25個即可達到93.64%的覆蓋率。從適應度曲線不難看出，隨著適應度越來越高，出現更優的新一代所需的雜交次數也越來越多，傳感器個數越多，其覆蓋率也越高，但覆蓋率與傳感器個數并不成線性關系。此算法是一種隨機排布的加速算法，使隨機得到的部署圖能快速符合需求，并且隨運行時間推移，子代的適應度將收斂于一個極限值，并隨著傳感器個數的增加，適應度也在增加。

圖8 N為不同值時的傳感器節點部署Fig.8 Sensor nodes deployment when N is different value

圖9 N為不同值時適應度曲線Fig.9 Fitness curve when N is different value

4 結束語

本算法利用離散的圖形計算方法，實現了農業無線傳感器網絡節點的部署算法。利用本算法，可以方便地求得特定條件下覆蓋率較高的無線傳感器網絡部署方案。本算法的時間復雜度與無線傳感器節點數量和離散細分有關，若試驗精確度要求不高則可將細分設置為1 m/pixel，可大幅度提高運算速度。遺傳迭代次數越多，本算法得到的試驗結果越好。當細分值越小時，相同條件下結果的精確度越好。該算法的計算過程可以進一步改進，先在高細分下求得較好的部署方案，再通過低細分繼承其結果進一步求取結果；其次優化雜交算法可以提升計算速度。