基于魚群算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略

摘 要:無線傳感網(wǎng)絡(luò)是能量受限的網(wǎng)絡(luò)，有效覆蓋和能耗是衡量其性能的兩個重要指標(biāo)。將最大化網(wǎng)絡(luò)覆蓋率和最小化工作節(jié)點數(shù)作為網(wǎng)絡(luò)優(yōu)化目標(biāo)，建立了網(wǎng)絡(luò)覆蓋優(yōu)化的數(shù)學(xué)模型，并利用魚群算法并行尋優(yōu)、收斂快速的特性，提出了一種基于魚群算法的覆蓋優(yōu)化策略。仿真實驗表明，該算法能求解最優(yōu)覆蓋工作節(jié)點，并可以改進網(wǎng)絡(luò)節(jié)點調(diào)度的實時性。

關(guān)鍵詞:無線傳感網(wǎng)絡(luò); 魚群算法; 覆蓋優(yōu)化

中圖分類號:TP393文獻標(biāo)志碼:A

文章編號:1001-3695(2010)06-2276-04

doi:10.3969/j.issn.10013695.2010.06.080

Optimal coverage configuration based onartificial fish swarm algorithm in WSNs

ZHOU Limin， YANG Kehua， ZHOU Pan

(School of Computer Communication， Hunan University， Changsha 410082， China)

Abstract:Wireless sensor networks is energyconstrained networks，coverage rates and energy consumption are two important performace indicators.Maximize the network coverage and minimize the number of working nodes as a network optimization goal， established an optimal model for coverage in wireless sensor network. To utilize the characteristics of parallel and fast convergence，proposed a coverage optimization strategy based on fish swarm algorithm. Simulation results show that the algorithm can get an optimal selection of the set of nodes and improve the realtime capability of nodes scheduling.

Key words:wirelss sensor networks; aritificial fish swarm algorithm; optimal coverage

0 引言

覆蓋是無線傳感器網(wǎng)絡(luò)中的一個重要問題，它反映了網(wǎng)絡(luò)所能提供的感知服務(wù)質(zhì)量。優(yōu)化無線傳感器網(wǎng)絡(luò)覆蓋對于合理分配網(wǎng)絡(luò)資源，更好地完成環(huán)境感知、信息獲取等任務(wù)都具有重要的意義[1]。

目前，對無線傳感覆蓋問題的研究主要分為確定性覆蓋和隨機覆蓋。前者主要研究如何使用最少的節(jié)點對已知環(huán)境進行覆蓋;后者研究采用隨機布署的方式對環(huán)境未知的區(qū)域進行監(jiān)測。一般地，隨機部署的網(wǎng)絡(luò)節(jié)點能源無法再生或補給。因此，如何保證在足夠覆蓋監(jiān)測區(qū)域的同時延長網(wǎng)絡(luò)的壽命，是無線傳感器網(wǎng)絡(luò)中一個亟待解決的重要問題[2]。文獻[3]首先討論了如何利用節(jié)點的覆蓋冗余來延長網(wǎng)絡(luò)生存時間。采用輪換活躍和休眠節(jié)點的節(jié)能覆蓋方案，可以有效地提高網(wǎng)絡(luò)生存時間[4]。文獻[5]提出了基于遺傳算法和基于約束遺傳算法的優(yōu)化覆蓋機制，計算出傳感器網(wǎng)絡(luò)充分覆蓋區(qū)域所需的近似最優(yōu)工作節(jié)點集，但遺傳算法在最優(yōu)解附近收斂緩慢，節(jié)點調(diào)度的實時性能有待提高。文獻[6]結(jié)合了網(wǎng)絡(luò)中節(jié)點的能量消耗，提出一種結(jié)合了Hopfield網(wǎng)絡(luò)與遺傳算法(HNGA)的覆蓋優(yōu)化策略。文獻[7]通過在網(wǎng)絡(luò)中加入移動節(jié)點，設(shè)計了一種基于微粒群算法的覆蓋能效優(yōu)化方法。文獻[8]結(jié)合了魚群算法設(shè)計網(wǎng)絡(luò)部署優(yōu)化方案計算移動節(jié)點的最終位置來提高網(wǎng)絡(luò)覆蓋率，但該方案不能作用于靜態(tài)約束的節(jié)點，無法適用于靜態(tài)網(wǎng)絡(luò)的覆蓋優(yōu)化。由于移動節(jié)點比較昂貴，靜態(tài)網(wǎng)絡(luò)有更大的普遍性和代表性，本文研究如何利用無線傳感器靜態(tài)網(wǎng)絡(luò)的冗余性，利用魚群算法并行尋優(yōu)、收斂快速的特性，提出了一種基于魚群算法的覆蓋優(yōu)化策略。

1 覆蓋數(shù)學(xué)模型

1.1 問題描述

假定監(jiān)測區(qū)域為二維平面，在該區(qū)域隨機投放了N個網(wǎng)絡(luò)節(jié)點。網(wǎng)絡(luò)中節(jié)點密度足夠大，有冗余。為簡化起見，假設(shè):

a)傳感器網(wǎng)絡(luò)為高密度靜態(tài)網(wǎng)絡(luò)，即節(jié)點部署后不再移動。

b)各節(jié)點感知采用布爾感知模型，物理結(jié)構(gòu)都是同構(gòu)的。

c)每個節(jié)點具有工作和休眠兩種狀態(tài)。網(wǎng)絡(luò)僅含一個中心處理節(jié)點，具有較強的計算能力，可用于切換無線傳感器網(wǎng)絡(luò)節(jié)點狀態(tài)。

d)所有無線傳感器節(jié)點位置已知。

節(jié)點調(diào)度的任務(wù)就是從大量的傳感器節(jié)點中選出一組最優(yōu)的節(jié)點，保持網(wǎng)絡(luò)連通，并獲得盡可能大的覆蓋率，文獻[9]證明了當(dāng)保持節(jié)點間通信半徑兩倍于感知半徑時，在充分覆蓋的前提下，總能保證網(wǎng)絡(luò)連通性。因此，本文探索的問題可以闡述如下:存在傳感器節(jié)點集合S={si，i=1，2，…，N}，求一個子集工作節(jié)點集C，在最大化網(wǎng)絡(luò)覆蓋要求的同時盡量最小化工作節(jié)點的個數(shù)。

1.2 覆蓋性能指標(biāo)

設(shè)無線傳感網(wǎng)絡(luò)中所有的傳感器節(jié)點集合為S={si，i=1，2，…，N}，每個傳感器節(jié)點的覆蓋模型可表示為以節(jié)點坐標(biāo)為圓心，Rs為半徑的圓，即每個節(jié)點均可表示為si=(xi，yi，Rs)。設(shè)監(jiān)測區(qū)域被數(shù)字離散化分成m×n個像素，每個像素的面積為一個單位，設(shè)其中任意一個像素點p(x，y)，則目標(biāo)像素點與傳感器節(jié)點si的距離為

d(si，p)=(x-xi)2+(y-yi)2(1)

定義像素點(x，y)被傳感器節(jié)點si覆蓋的事件為ri，i=1，2，…，N，該事件發(fā)生的概率為P(ri)。節(jié)點采用布爾傳感覆蓋模型，則該概率是二值函數(shù)，即

P(ri)=P(x，y，si)=1 d(si，p)≤Rs0 otherwise(2)

對于像素點(x，y)，節(jié)點集C中只要有一個節(jié)點覆蓋了該像素點，就認(rèn)為該像素點被覆蓋。記像素點(x，y)被選取的工作節(jié)點集C覆蓋的概率為P(x，y，C)，則

P(x，y，C)=P(∪ni=1ri)=1-∏ni=1(1-P(x，y，si))(3)

傳感器工作節(jié)點集C所覆蓋的像素面積之和就是該工作集所有工作節(jié)點覆蓋像素點的并集，記為area(C)，則

area(C)=∫m0∫n0P(x，y，C)dxdy(4)

定義一個布爾控制向量X=(a1，a2，…，aN)，該控制向量描述了傳感網(wǎng)絡(luò)節(jié)點的狀態(tài)。其中:ai=1表示第i個傳感節(jié)點處于工作狀態(tài)，ai=0表示第i個傳感節(jié)點處于休眠狀態(tài)。記傳感網(wǎng)絡(luò)覆蓋率f1(X)，節(jié)點利用率f2(X)。得到傳感網(wǎng)絡(luò)覆蓋率和節(jié)點利用率為

f1(X)=area(C)/(m×n)(5)

f2(X)=∑Ni=1ai/n(6)

對于無線傳感網(wǎng)絡(luò)的覆蓋優(yōu)化問題， 一方面是要使網(wǎng)絡(luò)覆蓋率極大化，另一方面是要使節(jié)點利用率極小化。因此，無線傳感網(wǎng)絡(luò)的覆蓋控制是一個多目標(biāo)組合優(yōu)化問題，可以通過加權(quán)形成目標(biāo)的線性組合，將原始的多個子目標(biāo)優(yōu)化函數(shù)轉(zhuǎn)換成單目標(biāo)優(yōu)化函數(shù)。總目標(biāo)優(yōu)化函數(shù)定義為

F(X)=w1f1(X)+w2(1-f2(X))(7)

其中:0

2 魚群算法的優(yōu)化原理

人工魚群算法是由李曉磊等人[10]在2002年提出的一種新型的群智能尋優(yōu)算法，該算法通過模擬魚群游弋覓食，通過集體協(xié)作達到尋優(yōu)目的。它不需要問題的嚴(yán)格機理模型，能很好地解決離散事件的最優(yōu)排序、分組或篩選等組合優(yōu)化問題，具有較快的收斂速度，適用于解決有實時性要求的問題[11]。目前，人工魚研究已涉及到通信多用戶檢測、組播路由、網(wǎng)格計算等領(lǐng)域[12~15]，顯示出解決大規(guī)模復(fù)雜非線性優(yōu)化問題的能力。

2.1 基于魚群算法的網(wǎng)絡(luò)覆蓋優(yōu)化策略

無線傳感器網(wǎng)絡(luò)的工作集節(jié)點備選解可用一條人工魚來表示。定義人工魚向量為工作節(jié)點集Xi=(ai1，ai2，…，aiN)。其中:aik表示人工魚Xi第k維的分量，只能為0或1。F(Xi)為人工魚Xi的食物濃度。將傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化問題抽象成若干條人工魚并行探索最大食物濃度的過程。設(shè)定人工魚步長為step，在其視野visual內(nèi)游動，1≤step≤visual。用δ(0<δ<1)表示擁擠度因子，因子值越大，表示越擁擠。NF表示人工魚群總數(shù)。

2.1.1 人工魚的相關(guān)定義

利用人工魚群算法解決覆蓋優(yōu)化問題，關(guān)鍵在于人工魚個體模型的構(gòu)造。在本文中，每條人工魚表示一個工作節(jié)點集，人工魚的距離、鄰居魚群和中心位置這幾個概念比較重要。下面就對其相關(guān)的概念進一步定義。

定義1 人工魚距離。人工魚向量Xi和Xj之間的距離為海明距離，用來表示屬于Xi但不屬于Xj的元素的個數(shù)。

D(Xi，Xj)=∑Nk=1(|aik-ajk|)

定義2 鄰居魚群。設(shè)人工魚群為G，對于人工魚XNeighbor(X，visual)={X′|D(X，X′)

定義3 魚群中心。設(shè)人工魚Xi的鄰居為Xi_1，Xi_2，…，Xi_n，即Xi的鄰居魚群矩陣為

(Xi，Xi_1，…，Xi_n)T=ai1ai2…aiN

a(i_1)1a(i-1)2…a(i_1)N



a(i_n)1a(i_n)2 … a(i_n)N

人工魚Xi的魚群中心為

center(Xi)=mostj=i，i_1，…i_n(aj1，aj2，…，ajN)

其中:most操作符表示求取魚群矩陣在每列出現(xiàn)次數(shù)較多的分量值。

定義4 近似魚群中心。在排除Xi的鄰居魚群中具有最小食物濃度魚的魚群矩陣上，再進行most操作得到的魚群中心稱為Xi的近似魚群中心。

2.1.2 人工魚行為描述

人工魚的行為一共包含下列幾種:

a)覓食行為。它是魚在隨機游動過程中循著食物濃度高的方向游動的一種行為，隨機游動行為是魚類為了更大范圍地尋覓鄰居和食物而進行的一種全向嘗試行為，隨機行為有助于算法跳出局部極值。人工魚在狀態(tài)Xi下， 在其視野距離內(nèi)隨機探索一個位置Xj(將Xi向量隨機visual位分量取反)。如果Xi的食物濃度比Xj大，則人工魚Xi向Xj前進一步，即Xi=Xj;否則，人工魚繼續(xù)在其視野距離內(nèi)重新尋找可以前進的位置，如此反復(fù)嘗試幾次后，如果仍沒有找到更優(yōu)的位置，則隨機移動一步。

b)聚群行為。它是每條人工魚在游動過程中盡量向鄰居魚群的中心移動并避免過分擁擠。人工魚先搜索其視野內(nèi)的鄰居，計算其數(shù)目nf，求其鄰居中心Xi_c(如果對其鄰居中心most操作得到某些維次的分量為0或1的次數(shù)相同，求其近似鄰居中心)，若鄰居中心位置Xi_c食物濃度較大且不太擁擠，即滿足F(Xi_c)>F(Xi)和nfNF<δ，則朝鄰居中心方向前進一步。

c)追尾行為。它是魚追捉其視野內(nèi)具有最大食物濃度的人工魚Xi_max的行為， 如果其周圍不太擁擠，向該人工魚的方向前進一步。

2.1.3 應(yīng)用于無線傳感網(wǎng)絡(luò)覆蓋的AFSA算法流程

人工魚群算法求解無線傳感網(wǎng)絡(luò)節(jié)點工作集的基本流程如圖1所示。

根據(jù)上述流程圖，覆蓋優(yōu)化策略詳細(xì)設(shè)計如下:

a)產(chǎn)生初始化群體。設(shè)置初始迭代次數(shù)G=0，在控制變量可行域內(nèi)隨機生成NF條人工魚個體，形成初始魚群。

b)公告板賦初值。計算初始魚群各人工魚個體當(dāng)前狀態(tài)的食物濃度，比較大小，取最大食物濃度進入公告板，將此人工魚也登記公告板。

c)行為選擇。人工魚個體的行為由該人工魚的食物濃度決定。計算每條人工魚的自身食物濃度及魚群平均食物濃度，若人工魚低于平均水平時，則該人工魚采取追尾策略，以獲取食物;若高于平均水平 ，則該人工魚采取聚群策略。因為此時魚不餓，以聚群方式躲避敵害為主;若執(zhí)行聚群和追尾行為不成功，才執(zhí)行覓食行為。

d)公告板。各人工魚每行動一次后，檢驗自身的食物濃度與公告板的食物濃度，如果優(yōu)于公告板，則以自身取代之。

e)終止條件判斷。判斷G是否已達到預(yù)置的最大迭代次數(shù)Gmax或判斷最優(yōu)解是否達到了滿意的誤差界內(nèi)，若不滿足，則G=G+1，轉(zhuǎn)到c)執(zhí)行，進行下一步魚群優(yōu)化過程;否則，轉(zhuǎn)到f)執(zhí)行。

f)算法終止，輸出最優(yōu)解(即公告板中人工魚向量和函數(shù)值)。

3 實驗仿真

仿真實驗環(huán)境設(shè)置如下:

假設(shè)無線傳感器網(wǎng)絡(luò)監(jiān)測區(qū)域為100 m×100 m，每個無線傳感器節(jié)點的感知半徑是Rs= 9 m，采用主頻為2.4 GHz的計算機在MATLAB環(huán)境下仿真無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化。

根據(jù)待監(jiān)測區(qū)域的面積和傳感器參數(shù)，首先確定性地安放54個傳感器節(jié)點最優(yōu)化分布于監(jiān)測區(qū)域，如圖2(a)所示;然后在此基礎(chǔ)上再隨機播散26個傳感器節(jié)點，如圖2(b)所示。采用魚群算法對該監(jiān)測區(qū)域進行無線傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化，設(shè)定人工魚個數(shù)為100，魚群算法最大迭代次數(shù)設(shè)為300。人工魚視野為5，重試次數(shù)為3，擁擠度因子為0.6。進行20次實驗，對監(jiān)測區(qū)進行優(yōu)化覆蓋平均使用55個節(jié)點，節(jié)點利用率為68.75%，平均覆蓋率為96.2% ，達到了優(yōu)化覆蓋的目的。圖2(c)為算法運行200代后節(jié)點的分布情況;圖2(d)為算法運行300代后節(jié)點的分布情況。

為了驗證算法的有效性，本文進行了兩種模式下的仿真，即采用文獻[5]的基于遺傳算法的優(yōu)化覆蓋機制與本文算法進行對比，如表1所示。由于這兩種算法均存在一定的隨機性，在對照中分別進行了40 組實驗，最后將結(jié)果求平均。在實驗中，為了增強迭代時間的可比性，遺傳算法的基因編碼為人工魚向量，設(shè)置種群數(shù)為100，進化代數(shù)為300，交叉率為0.9，變異率為0.05。

表1 魚群算法與遺傳算法策略對比表

迭代數(shù)本文覆蓋率/%文獻[5]覆蓋率/%本文節(jié)點數(shù)文獻[5]節(jié)點數(shù)

10079.3274.256365

15084.2480.686062

20089.4786.235859

25093.1792.915656

30096.2896.325555

如圖3所示。隨著迭代次數(shù)的增加，魚群算法覆蓋率增大，工作節(jié)點數(shù)向減速小的方向收斂。在進化到第300代時，魚群算法已經(jīng)取得非常接近遺傳算法的近似最優(yōu)覆蓋效果，而在算法的前期，人工魚群算法具有更快的收斂速度和更好的覆蓋優(yōu)化效果。特別地，對于某些可以極小地降低覆蓋率要求的無線傳感網(wǎng)絡(luò)，基于魚群算法的覆蓋優(yōu)化策略在更短的時間內(nèi)就可以使用更少的工作節(jié)點來達到網(wǎng)絡(luò)的覆蓋要求。因此，基于魚群算法的覆蓋策略可以在短時間內(nèi)求得較滿意的覆蓋優(yōu)化方案，具有更好的實時性，能夠減少網(wǎng)絡(luò)的振蕩。

4 結(jié)束語

人工魚群算法是一種新的隨機搜索優(yōu)化算法，它具有并行性、全局性、簡單性、快速性、跟蹤性等特點，為解決一些非凸、非線性及離散的優(yōu)化問題提供了一條新的思路。

本文針對無線傳感器網(wǎng)絡(luò)中的覆蓋問題，提出了一種基于魚群算法的覆蓋優(yōu)化策略。仿真結(jié)果表明了魚群算法能以較小的代價快速高效地求解近似最優(yōu)覆蓋節(jié)點集，從而減小網(wǎng)絡(luò)冗余，提高網(wǎng)絡(luò)的能效性和節(jié)點調(diào)度的實時性。

參考文獻:

[1]HUANG C F. The coverage problem in wireless sensor network[C]//Proc of ACM International Workshop on Wireless Sensor Networks and Applications.New York:ACM Press， 2005:519-528.

[2]CARDEI M， WU J. Energyefficient coverage problems in wireless Ad hoc sensor networks[J]. Computer Communications， 2006， 29(4):413-420.

[3]SLIJEPCEVIC S， POTKONJAK M. Power efficient organization of wireless sensor networks[C]//Proc of International Conference on Communications. Helsinki: IEEE Communication Society， 2001:472-476.

[4]CARDEI M， DUD Z. Improving wireless sensor network life time through power aware organization[J]. Wireless Networks，2005，11(3):333-340.

[5]賈杰，陳劍，常桂然.無線傳感器網(wǎng)絡(luò)中基于遺傳算法的優(yōu)化覆蓋機制[J].控制與決策，2007， 22(17) :1289-1301.

[6]王晟，王雪，畢道偉.無線傳感器網(wǎng)絡(luò)動態(tài)節(jié)點選擇優(yōu)化策略[J].計算機研究與發(fā)展，2008，45(1):188-195.

[7]WANG Xue，WANG Sheng，MA Junlie. Parallel particle swarm optimization based mobile sensor node deployment in wireless sensor networks[J].Chinese Journal of Computers， 2007，30(4):563-568.

[8]王蕊，劉國枝.基于魚群優(yōu)化算法的無線傳感網(wǎng)絡(luò)部署[J].振動與沖擊，2009，28(2):8-11.

[9]ZHANG Honghai， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad hoc and Sensor Wireless Networs，2005，1(1):89-124.

[10]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實踐，2002，22(11):32-38.

[11]李曉磊，路飛，田國會.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報，2004，34(5):64-67.

[12]JIANG Y， WANG Y， PFLETSCHINGER S， et al. Optimal multiuser detection with artificial fish swarm algorithm[C]//Proc of International Conference on Intelligent Computing. Berlin， Heidelberg:SpringerVerlag， 2007:1084-1093.

[13]SHAN X J， JIANG M Y.The routing optimization based on improved artificial fish swarm algorithm[C]//Proc of the 6th IEEE World Congress on Intelligent Control and Automation.Dalian:[s.n.]， 2006:3658-3662.

[14]FARZI S. Efficient job scheduling in grid computing with modified artificial fish swarm algorithm[J]. International Journal of Computer Theory and Engineering，2009，1(1):13-18.

[15]JIANG M Y， YUAN D F. Artificial fish swarm algorithm and its applications[C]//Proc of International Conference on Sensing Computing and Automation. 2006:1782-1787.