張伯琰，鄒騰躍

(福建農(nóng)林大學(xué)機(jī)電工程學(xué)院，福建 福州 350002)

0 引言

利用農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)(Agricultural Wireless Sensor Network，AWSN)精確獲取農(nóng)作物生長(zhǎng)環(huán)境信息是現(xiàn)代農(nóng)業(yè)發(fā)展的重要技術(shù)手段，農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)通常由多個(gè)無(wú)線傳感器節(jié)點(diǎn)(Wireless Sensor Network Nodes，WSNN)組成，組成傳感器網(wǎng)絡(luò)的傳感器檢測(cè)半徑大多相同，傳感器的布局會(huì)直接影響到農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)的成本、效率和使用壽命。在無(wú)線傳感器網(wǎng)絡(luò)部署階段，傳感器的檢測(cè)范圍為圓形，多個(gè)傳感器進(jìn)行部署，不可避免地產(chǎn)生重疊區(qū)域。若傳感器數(shù)量過(guò)多，檢測(cè)范圍重疊程度較大，會(huì)導(dǎo)致傳感器檢測(cè)數(shù)據(jù)的冗余，數(shù)據(jù)處理煩瑣，無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)整體電量耗能增加，縮短無(wú)線傳感器網(wǎng)絡(luò)壽命[1]。農(nóng)業(yè)無(wú)線傳感網(wǎng)絡(luò)設(shè)置環(huán)境復(fù)雜，維護(hù)困難，大大增加了農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)的安裝維護(hù)成本。

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

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

隨著智能技術(shù)的發(fā)展，智慧農(nóng)業(yè)成為熱點(diǎn)問(wèn)題。基于大數(shù)據(jù)的智慧農(nóng)業(yè)發(fā)展迅速，物聯(lián)網(wǎng)技術(shù)在智慧農(nóng)業(yè)中發(fā)揮了極大的作用[6]。物聯(lián)網(wǎng)技術(shù)可以監(jiān)控農(nóng)業(yè)的生長(zhǎng)情況和環(huán)境條件，并構(gòu)建信息交流網(wǎng)絡(luò)平臺(tái)，實(shí)現(xiàn)信息的互通與交流[7]。合理的無(wú)線傳感器部署算法可以延遲黑洞效應(yīng)的產(chǎn)生時(shí)間，有效提升無(wú)線傳感器網(wǎng)絡(luò)生命周期[8]。傳統(tǒng)的農(nóng)業(yè)無(wú)線傳感器部署通常采用正多邊形的部署辦法，可以實(shí)現(xiàn)檢測(cè)區(qū)域的高覆蓋率，但是這會(huì)使傳感器數(shù)量大大增加，同時(shí)因?yàn)閭鞲衅鲾?shù)量的增加，使得重疊面積增加，冗余數(shù)據(jù)也會(huì)隨之增加，進(jìn)而促進(jìn)了節(jié)點(diǎn)的衰亡。

1.2 模型建立

為了改進(jìn)上述問(wèn)題，在確保高覆蓋率的同時(shí)，減少傳感器數(shù)量，設(shè)計(jì)了一種基于改進(jìn)遺傳算法的農(nóng)業(yè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署算法。本算法以舍差取優(yōu)點(diǎn)策略作為算子選擇方案。用整個(gè)分布圖的節(jié)點(diǎn)坐標(biāo)作為遺傳個(gè)體，每個(gè)個(gè)體的染色體包含一個(gè)多點(diǎn)坐標(biāo)。本設(shè)計(jì)沒(méi)有使用二進(jìn)制編碼，而是直接對(duì)染色體進(jìn)行保留或舍棄操作，利用圖形計(jì)算，更加精確地計(jì)算相關(guān)參數(shù)。假設(shè)傳感器檢測(cè)范圍都為半徑相同的圓形區(qū)域，對(duì)檢測(cè)半徑為7 m的傳感器檢測(cè)范圍圓S進(jìn)行細(xì)分為1 m/pixel離散的示意如圖1所示。

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

(1)

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

r——待離散化圓的半徑

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

代數(shù)計(jì)算無(wú)線傳感器檢測(cè)圓面積公式為

S=π·r2

(2)

式中S——傳感器檢測(cè)范圍面積

經(jīng)過(guò)離散化后，計(jì)算無(wú)線傳感器檢測(cè)范圍圓面積公式為

(3)

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

針對(duì)此模型給出以下定義。

定義1：?jiǎn)螌佑行Ц采w面積，在一個(gè)無(wú)線傳感器的覆蓋范圍里，除去其他傳感器造成的重疊區(qū)域部分的面積。

定義2：覆蓋值，樣本區(qū)域被分割為多個(gè)長(zhǎng)寬各1 m的區(qū)域，當(dāng)該區(qū)域被n個(gè)傳感器覆蓋時(shí)，其覆蓋值為n。該值用于表達(dá)每塊區(qū)域被傳感器覆蓋的程度。

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

如圖2所示，當(dāng)兩個(gè)節(jié)點(diǎn)的覆蓋面積發(fā)生重疊，執(zhí)行離散圓的加和操作，基因表達(dá)模型公式為

圖2 兩個(gè)節(jié)點(diǎn)檢測(cè)范圍發(fā)生重疊示意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)——樣本中點(diǎn)(x，y)坐標(biāo)的值

按照本算法擬對(duì)基因?yàn)閧(1，2)，(6，9)，(11，1)，r=7}的個(gè)體進(jìn)行基因表達(dá)，表達(dá)模型過(guò)程如圖3、圖4和圖5所示。

圖3 基因表達(dá)模型過(guò)程步驟一Fig.3 Gene expression model process′s step one

圖4 基因表達(dá)模型過(guò)程步驟二Fig.4 Gene expression model process′s step two

圖5 基因表達(dá)模型過(guò)程步驟三Fig.5 Gene expression model process′s step three

如圖3所示，首先將離散化的傳感器檢測(cè)范圍圓按照染色體記錄的坐標(biāo)映射到畫(huà)布上，對(duì)應(yīng)位置覆蓋值相加，傳感器檢測(cè)范圍圓內(nèi)覆蓋值為0+1=1。超出邊界部分不予記錄。

表達(dá)完染色體1后表達(dá)染色體2，同樣也是對(duì)應(yīng)位置相加，兩圓重疊部分的值為2

最后表達(dá)染色體3，對(duì)應(yīng)位置相加，3個(gè)圓重疊部分值為3；至此本算法完成了該基因的表達(dá)工作。

2 算法設(shè)計(jì)

2.1 算法設(shè)計(jì)思想

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

2.2 算法設(shè)計(jì)步驟

步驟一：建立一個(gè)樣本個(gè)體，設(shè)定該樣本個(gè)體中染色體數(shù)量即無(wú)線傳感器數(shù)量N，并隨機(jī)生成含傳感器坐標(biāo)的N個(gè)染色體。

步驟二：產(chǎn)生首次遺傳的父代之一。隨機(jī)產(chǎn)生K個(gè)樣本進(jìn)行兩兩相融。每次先產(chǎn)生染色體數(shù)目為2N的樣本，通過(guò)圖像處理的辦法將基因表達(dá)出來(lái)，保留覆蓋率最大的二倍體樣本。

步驟三：計(jì)算每個(gè)傳感器節(jié)點(diǎn)染色體的單層有效覆蓋面積，將單層覆蓋面積最小的染色體移除，重復(fù)此移除過(guò)程，直到該樣本中保留最后的N個(gè)染色體。

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

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

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

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

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

本算法設(shè)計(jì)雜交時(shí)先形成二倍體，然后表達(dá)該二倍體，再剔除差的基因，重復(fù)此循環(huán)，直到新形成的個(gè)體，染色體數(shù)目正常，至此視為產(chǎn)生了符合要求的子代。

3 仿真試驗(yàn)與數(shù)據(jù)分析

將試驗(yàn)樣本條件設(shè)置為長(zhǎng)和寬均為100 m，細(xì)分0.1 m/pixel；設(shè)置所有傳感器檢測(cè)圓半徑r=12 m，即傳感器檢測(cè)圓半徑為120像素；設(shè)置染色體(無(wú)線傳感器節(jié)點(diǎn))個(gè)數(shù)N分別為25、28、30和32個(gè)，單代雜交最大次數(shù)為19時(shí)，對(duì)此算法進(jìn)行仿真。

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

圖8 N為不同值時(shí)的傳感器節(jié)點(diǎn)部署Fig.8 Sensor nodes deployment when N is different value

圖9 N為不同值時(shí)適應(yīng)度曲線Fig.9 Fitness curve when N is different value

4 結(jié)束語(yǔ)

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