水文無線傳感網覆蓋的多目標優化算法研究

涂振宇,陳 杰，曾 瑄

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

為了獲得監測目標區域的水位、蒸發、溫濕度等水文數據，人們通常采用人工部署傳感節點采集數據的方式進行。這種技術路線具有簡單易行，便于操作的特點。但如果監測區域面積大(通?？赡苡袔装賯€平方米)、目標環境復雜、不便于人工部署數據采集節點。此時可采用飛機拋灑大量廉價的水文無線傳感器的方式進行水文監測[4]。每個無線傳感器都被看作一個擁有無線通信能力，同時還具有一定的數據采集與信號處理的智能節點。各節點能夠自組織，自管理。這些特性使得監測網絡具有較高的健壯性和容錯性，任何節點的故障不會影響整個網絡的數據探測與傳輸能力。

傳感器的硬件構成如圖1所示。傳感節點由傳感模塊、微處理器模塊、能量單元和無線通信模塊構成。傳感模塊可以監測目標區域的水雨情數據、蒸發、溫濕度、水質污染等多方面的數據乃至多媒體信息。

圖1 傳感器硬件構成

無線傳感技術同樣也適應農林業生產中的農作物病蟲害、土壤酸堿度和其他信息監測。

傳感信息經過采集和A/D轉換，經過處理器的處理并在存儲器里暫存。通信模塊負責數據發送并接受交換控制信息。能量單元為節點提供運行所需能量，一般采用電池供電。

1 系統模型

本文將監測水域劃分成二維網格來對監測的區域離散化，大量傳感器節點分散在某些網格中，用統一的初始化電量。我們要研究以下幾個問題:

1.1 覆蓋問題

每個傳感器節點的感知范圍是一個半徑為Rs的圓，節點之間的通信半徑為Rc，當Rc≥2Rs時，可以認為節點網絡全連通[2]。如果一個監測點位于K個節點感知范圍內，稱為K覆蓋[7]。節點的感知模型可以分為布爾感知模型和隨機感知模型二類。

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

監測點p位于節點s的感知圓形區域內，其感知概率為：

(1)

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

(2)

(2)概率模型：監測節點d被感知的概率與它與節點s的距離有下面關系

(3)

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

(4)

在水信息監測工程實踐中，我們通常監測的對象是二維水面的某個區域的水文信息，因此可以把目標區域離散成二維網格，網格的大小按合適的測量精度及傳感器的感知半徑來劃分。在監測水文數據時，我們要求的是無線傳感網能盡可能地覆蓋更大的面積并保存更長時間的監測周期，而不是要求監測特定的網格。在這種數據優先的前提下，我們在計算覆蓋面積時可以做一定的簡化。

監測區域的總網格數有m×n個，按上面公式計算每個網格的覆蓋度，如果該網格的覆蓋度大于設定的門檻值，則認為該網格被覆蓋。被傳感器覆蓋的網格數有Ni個，傳感器網絡按照時間段打開一定數目的傳感器，能有效地延長網絡生存期。

定義第i個時間段的覆蓋度為

傳感網的各個工作時間段都有一個覆蓋度值，取其最小值作為整個網絡的覆蓋度。

COV=MINCOVii屬于是[1T]區間的時間段

1.2 問題建模

一個節點集Ci對監測區域的覆蓋率可以定義為能被傳感器感知覆蓋的總面積與監測區域總面積之比。下面我們可以給出無線傳感網生存期優化模型：

MAX CS

滿足對于每個周期的工作節點，其節點集合滿足覆蓋條件并且

(8)

公式(8)表示，在所有工作周期內，任一節點的工作能耗總和不能超過其初始電量。

適應度函數設定：

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

(9)

其中α+β=1

在工程實際中，我們可以根據工程需要分別指定“網絡覆蓋度”，“網絡生存期”兩個目標的權重大小。通過公式(9)可以把多目標優化問題轉成單目標優化問題，有助于簡化編程，并且可以通過調整權重系數將算法向期待的方向引導。

2 多目標遺傳算法

2.1 算法步驟

用遺傳算法求解多目標優化問題的思想是：將問題進行編碼，構建初始種群，開始迭代運算，在每次迭代中，根據個體的適應度函數的值來選擇優良的個體并進行個體編碼的雜交、變異操作，最后達到終止條件后可以得到多個解的種群，通過解碼得到解空間[7]。

本文討論的優化問題是在傳感器的最大工作時間周期內，每個周期內獲得最大的覆蓋率。激活更多的傳感器節點可以獲得較大的覆蓋率，但同時消耗更多的電量，減少傳感器監測網絡總的生存期。因此編碼中要將傳感器節點的工作狀態與工作周期帶入問題中來，為此，先做如下規定：

傳感器節點集合記為S，每個傳感器的一個工作周期為t,網絡總的工作時間可以表示為T={t1,t2,,tn}。

在t時間內，如果傳感器節點處于工作狀態，其值為1，如果處于休眠狀態，設定為0。因此可以用T×N的矩陣來表示一個解的個體。

對于一個5個傳感器的WSN，如果設定有4個工作時間段，可以用圖2表示一種傳感器狀態。傳感器節點1，4，5工作，2、3休眠。

10011

圖2傳感器工作狀態

用如圖3所示矩陣表示監測區域內傳感器集合的工作方案。

圖3 傳感器編碼矩陣

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

(1)選擇算子

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

(10)

(2)雜交算子

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

列交換：產生二個[1M]區間的隨機整數N1，N2。父代個體1中選擇第N1列與父代個體2中的第N2列做交換，得到兩個子代個體。子代個體每列都符合覆蓋電量約束，但可能導致一個染色體的覆蓋約束不能得到滿足。故也要通過算法淘汰劣質解。

(3)變異算子

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

2.2 算法的改進

在上面的算子操作過程中，如果沒有合理的運算指導，只靠隨機概率來引導算法，很容易陷入局部最優或讓算法發散。本文對上面傳統的算法加以改進，引入鄰域搜索的概念來改進算法，收到良好的效果。在上面如果在計算適應度函數值的時候指定了固定的加權值α,β。算法只能得到一個非劣解。如果在選擇算子開始前，隨機設置新的權值組合可以使得算法在鄰域開始新的進化方向，從而彌補遺傳算法的局部搜索的局限[1,3]，改進的算法可以表述如下：

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

(2)根據適應度函數加權值的初始設定，計算當前種群每個解的適應度值,按支配關系,更新臨時非支配解集。

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

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

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

3 仿真算例

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

表1 算法實驗結果

圖4給出了一個較為理想的Pareto解集，與理論值較為吻合。圖4表明，在迭代次數為50的情況下，網絡覆蓋度的門檻值設定為0.5，如果要求100%的覆蓋，則網絡生存期為5個單位時間，如果維持最低的覆蓋度，則可以保持最大的生存期15個單位時間。調整不同的權重組合會得到不同的變化曲線。在實際工程中，可以根據需要進行設定。

圖4 Pareto解集

4 結語

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