異構無線傳感器網絡中多目標優化節點部署策略*

冀文娟，石為人，李 明，李 曼

（重慶大學自動化學院，重慶 400030）

0 引言

節點部署是無線傳感器網絡（wireless sensor networks，WSNs）的基本問題，決定了傳感器監測物理空間的效果。覆蓋反映網絡所能提供的“感知”服務質量［1］，實現優化分配無線傳感器網絡的空間資源，進而更好地完成環境感知、信息獲取和有效傳輸任務。因此，覆蓋質量和能耗是無線傳感器網絡節點部署必須考慮的問題。

文獻［2］提出一種基于遺傳算法在保證充分覆蓋的前提下，使得參與覆蓋的節點數最小的最優覆蓋方法。文獻［3］以網絡覆蓋最大和傳感器節點利用率最小為目標，提出基于二進制隨機多目標粒子群優化算法。文獻［4］以網絡覆蓋率為目標，提出基于改進蟻群算法的節點優化部署方法。文獻［5］提出了基于概率測量模型的以網絡覆蓋率為目標的粒子群優化策略。上述研究均針對同構網絡即參與覆蓋的節點參數相同，并且大多采用二元感知模型，不能反映節點實際探測時的不確定性。同時研究沒有考慮到事件發生呈現的“熱點”區域。針對這些問題，本文提出一種基于二進制粒子群的以區域覆蓋率最大和單位面積網絡能耗最小為目標的多目標異構傳感器網絡節點部署策略。

1 問題描述

假設監測區域A為二維平面，A被離散化為N個柵格，單位柵格面積為1。有K種不同類型的傳感器節點M個，其感知半徑rk和通信半徑rkc，且滿足rkc≥2rk，保證異構節點部署后構成一個連通的網絡。xik表示柵格i處的節點放置情況

1.1 異構網絡覆蓋模型與覆蓋率

類型為k的傳感器節點sik的位置為（xik，yik），對于任意格點q（xj，yj），傳感器節點與柵格點間的歐氏距離為

點q被i所覆蓋的事件定義為rijk，該事件發生的概率為p（rijk）。現有研究多數采用簡單的二元感知模型，即

然而，在實際應用中，由于監測環境和噪聲干擾和信號強度隨傳輸距離的衰減，傳感器節點的感知能力具有不確定性，因此，本文采用概率感知模型［6］

其中，α=d（cik，q）－rik1，λ為與監測概率有關的參數，rik1，rik2分別為k型傳感器節點的內外感知半徑。假設監測區域內rijk的發生具獨立性，定義任意格點q被區域內放置的傳感器節點感知的事件為rj，該事件發生的概率p（rj）為

根據覆蓋要求，用pthj表示格點p的覆蓋概率門限值，用c（pj）表示格點p是否滿足覆蓋要求

網絡中區域覆蓋率P定義為

1.2 異構網絡能耗模型

根據能量消耗模型［7］，單個k型節點在網絡覆蓋中的能量消耗為

其中，rk為k型傳感器節點的感知半徑。節點部署后，監測區域單位面積的能耗為

1.3 覆蓋優化目標

異構無線傳感器網絡節點部署優化目標是:網絡區域覆蓋率最大和網絡能耗最小。即要同時考察2個目標:網絡區域覆蓋率函數和監測區域單位面積能耗函數。這是一個多目標優化，問題可表達為

與單目標優化問題不同，求解多目標優化問題時，不是只有一個最優解而是要尋求一個非劣最優解集合。

2 節點部署策略設計

2.1 多目標優化的二進制粒子群算法原理

粒子群（particle swarm optimization，PSO）算法是一種通過模擬鳥群捕食行為的群智能算法，具有速度快、解質量高、魯棒性好等特點［8］。為解決工程實際中的組合優化問題，Kennedy和Eberhart于1997年首次提出二進制PSO，它將每個位置分量xij限制在集合{1，0}中，而速度vij不做這種限制。在更新粒子位置時，vij越大，粒子位置xij取1的概率越大。粒子速度和位置更新公式為

多目標優化的二進制粒子群算法（multi-objective binary particle swarm optimization，MOBPSO）中支配關系定義:1）任意2個粒子x1，x2，對于?fi都有f1（x1）≤fi（x2），?fi存在目標函數fj使得fi（xi）＜fi（x2），則稱粒子x1支配x2。2）對于不滿足上述關系的任意x1，x2，對于?fi，都有|fi（x1）＜fi（x2）|≤εm，?fi使得|fi（x1）＜fi（x2）|εm，則隨機選取x1或x2，如果選中x1，則稱粒子x1支配x2。引入強支配系數C［9］

使粒子間保持一定的距離，使非劣解均勻分布，防止粒子群早熟。

基于Pareto支配關系的最優解選擇排序方法:在粒子群中選取一個粒子xi與剩余粒子依次比較，通過粒子群中剩余粒子與xi的關系，將種群分為兩部分，A部分為支配xi和與xi不相關的粒子，B部分為被xi支配的粒子。若xi不被任何粒子支配，則將xi存入存放Pareto解集的EXS中。然后對A部分的粒子重復上述過程，直到將A部分粒子清空。

適應度函數:采用自適應加權適應度分配［10］，求解目標空間中各粒子的各目標函數值，通過比較得到各目標函數的權重值為

則粒子的適應度值為

通過適應度值可區分Pareto解集。

pbesti（t）和gbesti（t）的取值:在EXS中的Pareto解集中隨機選取2個解比較其適應度值，進而選取較優的解作為pbesti（t）或gbesti（t）。

算法約束條件:各類型傳感器節點不超過給定的數量。若當前粒子不滿足約束條件，則該粒子刪除，重新隨機產生一個新粒子，增加粒子群的多樣性。

2.2 算法實現步驟

1）編碼機制:粒子群中任意粒子Xi的維數為Q，Q=［log2K］+1，［X］為取整運算，K為傳感器類型數，編碼機制如圖1所示。

圖1 粒子編碼機制示意圖Fig 1 Schematic diagram of particle encoding mechanism

2）初始化粒子群規模PS，外部存儲空間EXS，粒子初始位置Xi（0）、初始速度υi（0）、迭代代數t=0。初始化算法參數:w，c1，c2。判斷初始化后的粒子群是否滿足約束條件，若否則重新生成粒子群。

3）計算各粒子的目標函數值:通過粒子間的支配關系排序，將非支配關系的粒子位置存入EXS。

4）更新粒子速度和位置信息:更新后的粒子若不滿足約束條件，則將該粒子刪除，重新隨機產生一個。

5）更新Pareto解集:如果Pareto解集中某個粒子與新存入的粒子存在支配，則從EXS中將被支配的粒子刪除。

6）判斷算法是否達到最大迭代次數，是則退出，否則，轉向步驟（3）。

3 仿真與結果分析

假設在40 m×40 m的監測區域中，不同區域覆蓋要求不同，即會出現監測目標數量多、密度大的“熱點區域”，該區域對網絡的覆蓋要求相應較大。如圖2所示為區域監測覆蓋率要求示意圖，不同的區域覆蓋率對應不同顏色。其中包括對覆蓋要求較高的深色“熱點區域”和對覆蓋要求相對較低的淺色區域。

仿真系統中傳感器類型和相關參數如表1所示。

圖2 監測區域覆蓋要求示意圖Fig 2 Schematic diagram of monitoring regional coverage requirements

表1 傳感器類型參數表Tab 1 List of sensor type parameter

能量參數μ=1，監測區域中各柵格覆蓋率閾值根據監測要求生成。圖3為本文算法運行結束后的到的Pareto解集中適應度值最大的解，其中用星號、圓圈、五角星分別表示0，1，2型傳感器節點。由于存在邊界效應，導致除“熱點區域”外，監測區域邊緣傳感器節點分布較多。

圖3 節點部署圖Fig 3 Diagram of node deployment

與NSGA-Ⅱ算法對比，MOBPSO算法中粒子群規模PS=20，迭代次數tmax=200，強支配系數C=80。NSGA—Ⅱ算法染色體編碼同本文算法編碼，交叉率為0.8，變異率為1/Q。

從圖4、圖5可以看出:隨著迭代次數的增加，MOBPSO算法的非劣解集對應的各目標函數（－F1，F2）的均值相對于NSGA—Ⅱ算法更快速、穩定地收斂于較優解。

圖4 不同迭代次數非劣解對應－F1均值變化圖Fig 4 Diagram of－F1value of solution in different iterations

圖5 不同迭代次數非劣解對應F2均值變化圖Fig 5 Diagram of F2value of solution in different iterations

4 結束語

本文提出了存在“熱點區域”的異構無線傳感器網絡中一種基于二進制粒子群算法的多目標優化的節點部署策略，采用概率感知模型，引入強支配系數使得解分布均勻，結合Pareto最優解選擇排序和基于自適應權重的適應度分配，進而獲得異構節點部署解。與NSGA—Ⅱ算法相比，運用MOBPSO算法對節點部署后提高了網絡覆蓋率，同時降低了能耗。本文研究的是二維空間的確定性靜止異構節點部署方法，傳感器節點位置是通過計算后部署。而監測區域的三維覆蓋、節點隨機布撒后通過節點移動的部署優化等問題有待于進一步的研究和探索。

［1］Huang Chifu.The coverage problem in wireless sensor networks［C］//ACM International Workshop on Wireless Sensor Networks and Applications，New York，USA，ACM，2005:519 －528.

［2］賈 杰，陳 劍，常桂然.無線傳感器網絡中最優覆蓋節點集的求解算法［J］.東北大學學報:自然科學版，2007，28（11）:1560－1563.

［3］郭怡婷，王俊年.無線傳感器網絡中基于微粒群算法的優化覆蓋機制［J］.計算機與現代化，2009，6:1560 －1563.

［4］黃 亮.基于改進蟻群算法的無線傳感器網絡節點部署［J］.計算機測量與控制，2010，18（9）:2210 －2212.

［5］林祝亮，馮遠進.基于粒子群算法的無線傳感器網絡覆蓋優化策略［J］.計算機仿真，2009，26（4）:190 －193.

［6］Zou Y，Chakrabarty K.Sensor deployment and target of localization based on virtual forces［C］//2003 Proceedings of the IEEE IN FOCOM San Francisco，California:IEEE，2003:1293 －1303.

［7］Shang Y，Shi H.Coverage and energy trade off in density control on sensor networks［C］//Proceedings of 11th International Conference on Parallel and Distributed Systems，Fukuoka，Japan，2005:564－570.

［8］Ciuprina G，Ioan D，Mumteanu I.Use of intelligent-particle swarm optimization in electromagnetic［J］.IEEE Trans on Magnetics，2002，38（2）:1037 －1040.

［9］Laumanns M，Thiele L，Deb K，et al.Combining convergence and diversity in evolutionary multi-objective optimization［J］.Evolutionary Computation，2002，10（3）:263 －282.

［10］閻嘯天，武 清.基于GA的網絡最短路徑多目標優化算法研究［J］.控制與決策，2009，27（7）:1104 －1107.