異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中多目標(biāo)優(yōu)化節(jié)點(diǎn)部署策略*

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

（重慶大學(xué)自動(dòng)化學(xué)院，重慶 400030）

0 引言

節(jié)點(diǎn)部署是無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）的基本問(wèn)題，決定了傳感器監(jiān)測(cè)物理空間的效果。覆蓋反映網(wǎng)絡(luò)所能提供的“感知”服務(wù)質(zhì)量［1］，實(shí)現(xiàn)優(yōu)化分配無(wú)線傳感器網(wǎng)絡(luò)的空間資源，進(jìn)而更好地完成環(huán)境感知、信息獲取和有效傳輸任務(wù)。因此，覆蓋質(zhì)量和能耗是無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署必須考慮的問(wèn)題。

文獻(xiàn)［2］提出一種基于遺傳算法在保證充分覆蓋的前提下，使得參與覆蓋的節(jié)點(diǎn)數(shù)最小的最優(yōu)覆蓋方法。文獻(xiàn)［3］以網(wǎng)絡(luò)覆蓋最大和傳感器節(jié)點(diǎn)利用率最小為目標(biāo)，提出基于二進(jìn)制隨機(jī)多目標(biāo)粒子群優(yōu)化算法。文獻(xiàn)［4］以網(wǎng)絡(luò)覆蓋率為目標(biāo)，提出基于改進(jìn)蟻群算法的節(jié)點(diǎn)優(yōu)化部署方法。文獻(xiàn)［5］提出了基于概率測(cè)量模型的以網(wǎng)絡(luò)覆蓋率為目標(biāo)的粒子群優(yōu)化策略。上述研究均針對(duì)同構(gòu)網(wǎng)絡(luò)即參與覆蓋的節(jié)點(diǎn)參數(shù)相同，并且大多采用二元感知模型，不能反映節(jié)點(diǎn)實(shí)際探測(cè)時(shí)的不確定性。同時(shí)研究沒(méi)有考慮到事件發(fā)生呈現(xiàn)的“熱點(diǎn)”區(qū)域。針對(duì)這些問(wèn)題，本文提出一種基于二進(jìn)制粒子群的以區(qū)域覆蓋率最大和單位面積網(wǎng)絡(luò)能耗最小為目標(biāo)的多目標(biāo)異構(gòu)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略。

1 問(wèn)題描述

假設(shè)監(jiān)測(cè)區(qū)域A為二維平面，A被離散化為N個(gè)柵格，單位柵格面積為1。有K種不同類(lèi)型的傳感器節(jié)點(diǎn)M個(gè)，其感知半徑rk和通信半徑rkc，且滿足rkc≥2rk，保證異構(gòu)節(jié)點(diǎn)部署后構(gòu)成一個(gè)連通的網(wǎng)絡(luò)。xik表示柵格i處的節(jié)點(diǎn)放置情況

1.1 異構(gòu)網(wǎng)絡(luò)覆蓋模型與覆蓋率

類(lèi)型為k的傳感器節(jié)點(diǎn)sik的位置為（xik，yik），對(duì)于任意格點(diǎn)q（xj，yj），傳感器節(jié)點(diǎn)與柵格點(diǎn)間的歐氏距離為

點(diǎn)q被i所覆蓋的事件定義為rijk，該事件發(fā)生的概率為p（rijk）。現(xiàn)有研究多數(shù)采用簡(jiǎn)單的二元感知模型，即

然而，在實(shí)際應(yīng)用中，由于監(jiān)測(cè)環(huán)境和噪聲干擾和信號(hào)強(qiáng)度隨傳輸距離的衰減，傳感器節(jié)點(diǎn)的感知能力具有不確定性，因此，本文采用概率感知模型［6］

其中，α=d（cik，q）－rik1，λ為與監(jiān)測(cè)概率有關(guān)的參數(shù)，rik1，rik2分別為k型傳感器節(jié)點(diǎn)的內(nèi)外感知半徑。假設(shè)監(jiān)測(cè)區(qū)域內(nèi)rijk的發(fā)生具獨(dú)立性，定義任意格點(diǎn)q被區(qū)域內(nèi)放置的傳感器節(jié)點(diǎn)感知的事件為rj，該事件發(fā)生的概率p（rj）為

根據(jù)覆蓋要求，用pthj表示格點(diǎn)p的覆蓋概率門(mén)限值，用c（pj）表示格點(diǎn)p是否滿足覆蓋要求

網(wǎng)絡(luò)中區(qū)域覆蓋率P定義為

1.2 異構(gòu)網(wǎng)絡(luò)能耗模型

根據(jù)能量消耗模型［7］，單個(gè)k型節(jié)點(diǎn)在網(wǎng)絡(luò)覆蓋中的能量消耗為

其中，rk為k型傳感器節(jié)點(diǎn)的感知半徑。節(jié)點(diǎn)部署后，監(jiān)測(cè)區(qū)域單位面積的能耗為

1.3 覆蓋優(yōu)化目標(biāo)

異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署優(yōu)化目標(biāo)是:網(wǎng)絡(luò)區(qū)域覆蓋率最大和網(wǎng)絡(luò)能耗最小。即要同時(shí)考察2個(gè)目標(biāo):網(wǎng)絡(luò)區(qū)域覆蓋率函數(shù)和監(jiān)測(cè)區(qū)域單位面積能耗函數(shù)。這是一個(gè)多目標(biāo)優(yōu)化，問(wèn)題可表達(dá)為

與單目標(biāo)優(yōu)化問(wèn)題不同，求解多目標(biāo)優(yōu)化問(wèn)題時(shí)，不是只有一個(gè)最優(yōu)解而是要尋求一個(gè)非劣最優(yōu)解集合。

2 節(jié)點(diǎn)部署策略設(shè)計(jì)

2.1 多目標(biāo)優(yōu)化的二進(jìn)制粒子群算法原理

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

多目標(biāo)優(yōu)化的二進(jìn)制粒子群算法（multi-objective binary particle swarm optimization，MOBPSO）中支配關(guān)系定義:1）任意2個(gè)粒子x1，x2，對(duì)于?fi都有f1（x1）≤fi（x2），?fi存在目標(biāo)函數(shù)fj使得fi（xi）＜fi（x2），則稱粒子x1支配x2。2）對(duì)于不滿足上述關(guān)系的任意x1，x2，對(duì)于?fi，都有|fi（x1）＜fi（x2）|≤εm，?fi使得|fi（x1）＜fi（x2）|εm，則隨機(jī)選取x1或x2，如果選中x1，則稱粒子x1支配x2。引入強(qiáng)支配系數(shù)C［9］

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

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

適應(yīng)度函數(shù):采用自適應(yīng)加權(quán)適應(yīng)度分配［10］，求解目標(biāo)空間中各粒子的各目標(biāo)函數(shù)值，通過(guò)比較得到各目標(biāo)函數(shù)的權(quán)重值為

則粒子的適應(yīng)度值為

通過(guò)適應(yīng)度值可區(qū)分Pareto解集。

pbesti（t）和gbesti（t）的取值:在EXS中的Pareto解集中隨機(jī)選取2個(gè)解比較其適應(yīng)度值，進(jìn)而選取較優(yōu)的解作為pbesti（t）或gbesti（t）。

算法約束條件:各類(lèi)型傳感器節(jié)點(diǎn)不超過(guò)給定的數(shù)量。若當(dāng)前粒子不滿足約束條件，則該粒子刪除，重新隨機(jī)產(chǎn)生一個(gè)新粒子，增加粒子群的多樣性。

2.2 算法實(shí)現(xiàn)步驟

1）編碼機(jī)制:粒子群中任意粒子X(jué)i的維數(shù)為Q，Q=［log2K］+1，［X］為取整運(yùn)算，K為傳感器類(lèi)型數(shù)，編碼機(jī)制如圖1所示。

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

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

3）計(jì)算各粒子的目標(biāo)函數(shù)值:通過(guò)粒子間的支配關(guān)系排序，將非支配關(guān)系的粒子位置存入EXS。

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

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

6）判斷算法是否達(dá)到最大迭代次數(shù)，是則退出，否則，轉(zhuǎn)向步驟（3）。

3 仿真與結(jié)果分析

假設(shè)在40 m×40 m的監(jiān)測(cè)區(qū)域中，不同區(qū)域覆蓋要求不同，即會(huì)出現(xiàn)監(jiān)測(cè)目標(biāo)數(shù)量多、密度大的“熱點(diǎn)區(qū)域”，該區(qū)域?qū)W(wǎng)絡(luò)的覆蓋要求相應(yīng)較大。如圖2所示為區(qū)域監(jiān)測(cè)覆蓋率要求示意圖，不同的區(qū)域覆蓋率對(duì)應(yīng)不同顏色。其中包括對(duì)覆蓋要求較高的深色“熱點(diǎn)區(qū)域”和對(duì)覆蓋要求相對(duì)較低的淺色區(qū)域。

仿真系統(tǒng)中傳感器類(lèi)型和相關(guān)參數(shù)如表1所示。

圖2 監(jiān)測(cè)區(qū)域覆蓋要求示意圖Fig 2 Schematic diagram of monitoring regional coverage requirements

表1 傳感器類(lèi)型參數(shù)表Tab 1 List of sensor type parameter

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

圖3 節(jié)點(diǎn)部署圖Fig 3 Diagram of node deployment

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

從圖4、圖5可以看出:隨著迭代次數(shù)的增加，MOBPSO算法的非劣解集對(duì)應(yīng)的各目標(biāo)函數(shù)（－F1，F(xiàn)2）的均值相對(duì)于NSGA—Ⅱ算法更快速、穩(wěn)定地收斂于較優(yōu)解。

圖4 不同迭代次數(shù)非劣解對(duì)應(yīng)－F1均值變化圖Fig 4 Diagram of－F1value of solution in different iterations

圖5 不同迭代次數(shù)非劣解對(duì)應(yīng)F2均值變化圖Fig 5 Diagram of F2value of solution in different iterations

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

本文提出了存在“熱點(diǎn)區(qū)域”的異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中一種基于二進(jìn)制粒子群算法的多目標(biāo)優(yōu)化的節(jié)點(diǎn)部署策略，采用概率感知模型，引入強(qiáng)支配系數(shù)使得解分布均勻，結(jié)合Pareto最優(yōu)解選擇排序和基于自適應(yīng)權(quán)重的適應(yīng)度分配，進(jìn)而獲得異構(gòu)節(jié)點(diǎn)部署解。與NSGA—Ⅱ算法相比，運(yùn)用MOBPSO算法對(duì)節(jié)點(diǎn)部署后提高了網(wǎng)絡(luò)覆蓋率，同時(shí)降低了能耗。本文研究的是二維空間的確定性靜止異構(gòu)節(jié)點(diǎn)部署方法，傳感器節(jié)點(diǎn)位置是通過(guò)計(jì)算后部署。而監(jiān)測(cè)區(qū)域的三維覆蓋、節(jié)點(diǎn)隨機(jī)布撒后通過(guò)節(jié)點(diǎn)移動(dòng)的部署優(yōu)化等問(wèn)題有待于進(jìn)一步的研究和探索。

［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］賈 杰，陳 劍，常桂然.無(wú)線傳感器網(wǎng)絡(luò)中最優(yōu)覆蓋節(jié)點(diǎn)集的求解算法［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，2007，28（11）:1560－1563.

［3］郭怡婷，王俊年.無(wú)線傳感器網(wǎng)絡(luò)中基于微粒群算法的優(yōu)化覆蓋機(jī)制［J］.計(jì)算機(jī)與現(xiàn)代化，2009，6:1560 －1563.

［4］黃 亮.基于改進(jìn)蟻群算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署［J］.計(jì)算機(jī)測(cè)量與控制，2010，18（9）:2210 －2212.

［5］林祝亮，馮遠(yuǎn)進(jìn).基于粒子群算法的無(wú)線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略［J］.計(jì)算機(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，F(xiàn)ukuoka，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的網(wǎng)絡(luò)最短路徑多目標(biāo)優(yōu)化算法研究［J］.控制與決策，2009，27（7）:1104 －1107.