涂振宇,陳 杰，曾 瑄

(1.南昌工程學(xué)院;2.江西省防汛信息中心)

為了獲得監(jiān)測(cè)目標(biāo)區(qū)域的水位、蒸發(fā)、溫濕度等水文數(shù)據(jù)，人們通常采用人工部署傳感節(jié)點(diǎn)采集數(shù)據(jù)的方式進(jìn)行。這種技術(shù)路線具有簡(jiǎn)單易行，便于操作的特點(diǎn)。但如果監(jiān)測(cè)區(qū)域面積大(通常可能有幾百個(gè)平方米)、目標(biāo)環(huán)境復(fù)雜、不便于人工部署數(shù)據(jù)采集節(jié)點(diǎn)。此時(shí)可采用飛機(jī)拋灑大量廉價(jià)的水文無(wú)線傳感器的方式進(jìn)行水文監(jiān)測(cè)[4]。每個(gè)無(wú)線傳感器都被看作一個(gè)擁有無(wú)線通信能力，同時(shí)還具有一定的數(shù)據(jù)采集與信號(hào)處理的智能節(jié)點(diǎn)。各節(jié)點(diǎn)能夠自組織，自管理。這些特性使得監(jiān)測(cè)網(wǎng)絡(luò)具有較高的健壯性和容錯(cuò)性，任何節(jié)點(diǎn)的故障不會(huì)影響整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)探測(cè)與傳輸能力。

傳感器的硬件構(gòu)成如圖1所示。傳感節(jié)點(diǎn)由傳感模塊、微處理器模塊、能量單元和無(wú)線通信模塊構(gòu)成。傳感模塊可以監(jiān)測(cè)目標(biāo)區(qū)域的水雨情數(shù)據(jù)、蒸發(fā)、溫濕度、水質(zhì)污染等多方面的數(shù)據(jù)乃至多媒體信息。

圖1 傳感器硬件構(gòu)成

無(wú)線傳感技術(shù)同樣也適應(yīng)農(nóng)林業(yè)生產(chǎn)中的農(nóng)作物病蟲(chóng)害、土壤酸堿度和其他信息監(jiān)測(cè)。

傳感信息經(jīng)過(guò)采集和A/D轉(zhuǎn)換，經(jīng)過(guò)處理器的處理并在存儲(chǔ)器里暫存。通信模塊負(fù)責(zé)數(shù)據(jù)發(fā)送并接受交換控制信息。能量單元為節(jié)點(diǎn)提供運(yùn)行所需能量，一般采用電池供電。

1 系統(tǒng)模型

本文將監(jiān)測(cè)水域劃分成二維網(wǎng)格來(lái)對(duì)監(jiān)測(cè)的區(qū)域離散化，大量傳感器節(jié)點(diǎn)分散在某些網(wǎng)格中，用統(tǒng)一的初始化電量。我們要研究以下幾個(gè)問(wèn)題:

1.1 覆蓋問(wèn)題

每個(gè)傳感器節(jié)點(diǎn)的感知范圍是一個(gè)半徑為Rs的圓，節(jié)點(diǎn)之間的通信半徑為Rc，當(dāng)Rc≥2Rs時(shí)，可以認(rèn)為節(jié)點(diǎn)網(wǎng)絡(luò)全連通[2]。如果一個(gè)監(jiān)測(cè)點(diǎn)位于K個(gè)節(jié)點(diǎn)感知范圍內(nèi)，稱(chēng)為K覆蓋[7]。節(jié)點(diǎn)的感知模型可以分為布爾感知模型和隨機(jī)感知模型二類(lèi)。

(1)布爾模型(0- 1 Boolean)

監(jiān)測(cè)點(diǎn)p位于節(jié)點(diǎn)s的感知圓形區(qū)域內(nèi)，其感知概率為：

(1)

其中，L(s,p)為點(diǎn)p(xp,yp)到點(diǎn)s(xs,ys)的歐氏距離

(2)

(2)概率模型：監(jiān)測(cè)節(jié)點(diǎn)d被感知的概率與它與節(jié)點(diǎn)s的距離有下面關(guān)系

(3)

其中，re容錯(cuò)半徑(表示節(jié)點(diǎn)的不確定性物理特性)，l=d(s,d)-(rs-re)如果監(jiān)測(cè)點(diǎn)d的監(jiān)測(cè)概率大于(或等于)一個(gè)門(mén)檻值pth，則表示P點(diǎn)可以被監(jiān)測(cè)到。如果監(jiān)測(cè)點(diǎn)P被K個(gè)傳感器節(jié)點(diǎn)感知，則其被K重覆蓋，其監(jiān)測(cè)概率為：

(4)

在水信息監(jiān)測(cè)工程實(shí)踐中，我們通常監(jiān)測(cè)的對(duì)象是二維水面的某個(gè)區(qū)域的水文信息，因此可以把目標(biāo)區(qū)域離散成二維網(wǎng)格，網(wǎng)格的大小按合適的測(cè)量精度及傳感器的感知半徑來(lái)劃分。在監(jiān)測(cè)水文數(shù)據(jù)時(shí)，我們要求的是無(wú)線傳感網(wǎng)能盡可能地覆蓋更大的面積并保存更長(zhǎng)時(shí)間的監(jiān)測(cè)周期，而不是要求監(jiān)測(cè)特定的網(wǎng)格。在這種數(shù)據(jù)優(yōu)先的前提下，我們?cè)谟?jì)算覆蓋面積時(shí)可以做一定的簡(jiǎn)化。

監(jiān)測(cè)區(qū)域的總網(wǎng)格數(shù)有m×n個(gè)，按上面公式計(jì)算每個(gè)網(wǎng)格的覆蓋度，如果該網(wǎng)格的覆蓋度大于設(shè)定的門(mén)檻值，則認(rèn)為該網(wǎng)格被覆蓋。被傳感器覆蓋的網(wǎng)格數(shù)有Ni個(gè)，傳感器網(wǎng)絡(luò)按照時(shí)間段打開(kāi)一定數(shù)目的傳感器，能有效地延長(zhǎng)網(wǎng)絡(luò)生存期。

定義第i個(gè)時(shí)間段的覆蓋度為

傳感網(wǎng)的各個(gè)工作時(shí)間段都有一個(gè)覆蓋度值，取其最小值作為整個(gè)網(wǎng)絡(luò)的覆蓋度。

COV=MINCOVii屬于是[1T]區(qū)間的時(shí)間段

1.2 問(wèn)題建模

一個(gè)節(jié)點(diǎn)集Ci對(duì)監(jiān)測(cè)區(qū)域的覆蓋率可以定義為能被傳感器感知覆蓋的總面積與監(jiān)測(cè)區(qū)域總面積之比。下面我們可以給出無(wú)線傳感網(wǎng)生存期優(yōu)化模型：

MAX CS

滿足對(duì)于每個(gè)周期的工作節(jié)點(diǎn)，其節(jié)點(diǎn)集合滿足覆蓋條件并且

(8)

公式(8)表示，在所有工作周期內(nèi)，任一節(jié)點(diǎn)的工作能耗總和不能超過(guò)其初始電量。

適應(yīng)度函數(shù)設(shè)定：

Fit(s)=α×Cs+β×T(s)

(9)

其中α+β=1

在工程實(shí)際中，我們可以根據(jù)工程需要分別指定“網(wǎng)絡(luò)覆蓋度”，“網(wǎng)絡(luò)生存期”兩個(gè)目標(biāo)的權(quán)重大小。通過(guò)公式(9)可以把多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)成單目標(biāo)優(yōu)化問(wèn)題，有助于簡(jiǎn)化編程，并且可以通過(guò)調(diào)整權(quán)重系數(shù)將算法向期待的方向引導(dǎo)。

2 多目標(biāo)遺傳算法

2.1 算法步驟

用遺傳算法求解多目標(biāo)優(yōu)化問(wèn)題的思想是：將問(wèn)題進(jìn)行編碼，構(gòu)建初始種群，開(kāi)始迭代運(yùn)算，在每次迭代中，根據(jù)個(gè)體的適應(yīng)度函數(shù)的值來(lái)選擇優(yōu)良的個(gè)體并進(jìn)行個(gè)體編碼的雜交、變異操作，最后達(dá)到終止條件后可以得到多個(gè)解的種群，通過(guò)解碼得到解空間[7]。

本文討論的優(yōu)化問(wèn)題是在傳感器的最大工作時(shí)間周期內(nèi)，每個(gè)周期內(nèi)獲得最大的覆蓋率。激活更多的傳感器節(jié)點(diǎn)可以獲得較大的覆蓋率，但同時(shí)消耗更多的電量，減少傳感器監(jiān)測(cè)網(wǎng)絡(luò)總的生存期。因此編碼中要將傳感器節(jié)點(diǎn)的工作狀態(tài)與工作周期帶入問(wèn)題中來(lái)，為此，先做如下規(guī)定：

傳感器節(jié)點(diǎn)集合記為S，每個(gè)傳感器的一個(gè)工作周期為t,網(wǎng)絡(luò)總的工作時(shí)間可以表示為T(mén)={t1,t2,,tn}。

在t時(shí)間內(nèi)，如果傳感器節(jié)點(diǎn)處于工作狀態(tài)，其值為1，如果處于休眠狀態(tài)，設(shè)定為0。因此可以用T×N的矩陣來(lái)表示一個(gè)解的個(gè)體。

對(duì)于一個(gè)5個(gè)傳感器的WSN，如果設(shè)定有4個(gè)工作時(shí)間段，可以用圖2表示一種傳感器狀態(tài)。傳感器節(jié)點(diǎn)1，4，5工作，2、3休眠。

10011

圖2傳感器工作狀態(tài)

用如圖3所示矩陣表示監(jiān)測(cè)區(qū)域內(nèi)傳感器集合的工作方案。

圖3 傳感器編碼矩陣

這種編碼方案可以映射到問(wèn)題的全部解空間，但每個(gè)矩陣個(gè)體不一定是合理的解。每個(gè)矩陣的列的和可能超過(guò)該節(jié)點(diǎn)的起始電量。因此在選擇操作中要淘汰某些不合理的解。

(1)選擇算子

在初始種群中，一個(gè)矩陣對(duì)于一個(gè)個(gè)體，在選擇作為父代個(gè)體前，可以對(duì)矩陣進(jìn)行解的合理性檢查，如果某列的元素之和超過(guò)該傳感器電量，則淘汰該個(gè)體，根據(jù)“輪盤(pán)賭選擇”算法選擇個(gè)體進(jìn)入下一次迭代。設(shè)種群規(guī)模為N，個(gè)體r的適應(yīng)度為fitness(r)，它被選中作為遺傳算法父體的概率為：

(10)

(2)雜交算子

行交換：產(chǎn)生二個(gè)[1T]區(qū)間的隨機(jī)整數(shù)N1，N2。父代個(gè)體1中選擇第N1行與父代個(gè)體2中的第N2行做交換，得到兩個(gè)子代個(gè)體。子代個(gè)體每行都是符合覆蓋要求的染色體。但可能產(chǎn)生某列的元素電量總和超過(guò)該傳感器的初始電量，產(chǎn)生不合理解個(gè)體。

列交換：產(chǎn)生二個(gè)[1M]區(qū)間的隨機(jī)整數(shù)N1，N2。父代個(gè)體1中選擇第N1列與父代個(gè)體2中的第N2列做交換，得到兩個(gè)子代個(gè)體。子代個(gè)體每列都符合覆蓋電量約束，但可能導(dǎo)致一個(gè)染色體的覆蓋約束不能得到滿足。故也要通過(guò)算法淘汰劣質(zhì)解。

(3)變異算子

變異算子可以拓寬解空間的大小，能使得解空間跳出局部最優(yōu)，在本例中屬于一個(gè)輔助算子，可以選擇父代的個(gè)體的某一行，按初始化方法生成某行元素，并檢查各列的電量約束條件。新的個(gè)體重新進(jìn)入迭代運(yùn)算。

2.2 算法的改進(jìn)

在上面的算子操作過(guò)程中，如果沒(méi)有合理的運(yùn)算指導(dǎo)，只靠隨機(jī)概率來(lái)引導(dǎo)算法，很容易陷入局部最優(yōu)或讓算法發(fā)散。本文對(duì)上面?zhèn)鹘y(tǒng)的算法加以改進(jìn)，引入鄰域搜索的概念來(lái)改進(jìn)算法，收到良好的效果。在上面如果在計(jì)算適應(yīng)度函數(shù)值的時(shí)候指定了固定的加權(quán)值α,β。算法只能得到一個(gè)非劣解。如果在選擇算子開(kāi)始前，隨機(jī)設(shè)置新的權(quán)值組合可以使得算法在鄰域開(kāi)始新的進(jìn)化方向，從而彌補(bǔ)遺傳算法的局部搜索的局限[1,3]，改進(jìn)的算法可以表述如下：

(1)隨機(jī)生成規(guī)模為初始種群，種群規(guī)模為N。

(2)根據(jù)適應(yīng)度函數(shù)加權(quán)值的初始設(shè)定，計(jì)算當(dāng)前種群每個(gè)解的適應(yīng)度值,按支配關(guān)系,更新臨時(shí)非支配解集。

(3)隨機(jī)設(shè)定新的加權(quán)值α，β，按輪盤(pán)賭方式從非支配解集之外選出父代個(gè)體，產(chǎn)生進(jìn)行遺傳操作交叉、變異。

(4)上述操作產(chǎn)生的子代和(2)中的非支配解集中的個(gè)體合并在一起，形成新的種群。

(5)如果滿足終止條件，則結(jié)束算法，否則重新轉(zhuǎn)(3)。

3 仿真算例

設(shè)置監(jiān)測(cè)區(qū)域大小為50m×50m，在其中隨機(jī)放在100個(gè)節(jié)點(diǎn)，設(shè)置節(jié)點(diǎn)感知半徑RS=5m,節(jié)點(diǎn)的通信半徑為RC=10m,初始電量為個(gè)單位。網(wǎng)絡(luò)覆蓋率門(mén)檻值為0.5，雜交概率為0.8，變異概率取0.1，初始種群個(gè)體50個(gè)，最大迭代次數(shù)為150。算法目標(biāo)，找到滿足覆蓋概率約束的，總工作周期T最大的個(gè)體解集。算法迭代次數(shù)分別設(shè)為50,75,100,125時(shí)，在每次迭代完成挑選出具有代表性地非劣解，見(jiàn)表1。如表1可知，在算法進(jìn)行100次迭代過(guò)程中，所得到的非劣解分布均勻，解的質(zhì)量良好，更多的迭代次數(shù)并沒(méi)有更多的改善，只能增加算法的時(shí)間。

表1 算法實(shí)驗(yàn)結(jié)果

圖4給出了一個(gè)較為理想的Pareto解集，與理論值較為吻合。圖4表明，在迭代次數(shù)為50的情況下，網(wǎng)絡(luò)覆蓋度的門(mén)檻值設(shè)定為0.5，如果要求100%的覆蓋，則網(wǎng)絡(luò)生存期為5個(gè)單位時(shí)間，如果維持最低的覆蓋度，則可以保持最大的生存期15個(gè)單位時(shí)間。調(diào)整不同的權(quán)重組合會(huì)得到不同的變化曲線。在實(shí)際工程中，可以根據(jù)需要進(jìn)行設(shè)定。

圖4 Pareto解集

4 結(jié)語(yǔ)

無(wú)線傳感網(wǎng)覆蓋優(yōu)化是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，傳統(tǒng)方法難以得到最優(yōu)解，一般也只能得到一系列的非支配解。在采用遺傳方法進(jìn)行迭代尋優(yōu)的過(guò)程中，個(gè)體的編碼很大程度上直接影響算法的效率和解空間的質(zhì)量。本文采用迭代過(guò)程中的鄰域搜索算法，可以有效地避免算法的早熟收斂，提高算法的質(zhì)量。與標(biāo)準(zhǔn)遺傳算法相比，新算法在網(wǎng)絡(luò)的有效覆蓋度和網(wǎng)絡(luò)生存期兩個(gè)方面都有明顯的提高，收斂速度也得到了加快。