基于魚群算法的無線傳感網絡覆蓋優化策略

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

關鍵詞:無線傳感網絡; 魚群算法; 覆蓋優化

中圖分類號:TP393文獻標志碼: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 引言

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

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

1 覆蓋數學模型

1.1 問題描述

假定監測區域為二維平面，在該區域隨機投放了N個網絡節點。網絡中節點密度足夠大，有冗余。為簡化起見，假設:

a)傳感器網絡為高密度靜態網絡，即節點部署后不再移動。

b)各節點感知采用布爾感知模型，物理結構都是同構的。

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

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

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

1.2 覆蓋性能指標

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

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

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

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

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

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

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

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

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

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

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

對于無線傳感網絡的覆蓋優化問題， 一方面是要使網絡覆蓋率極大化，另一方面是要使節點利用率極小化。因此，無線傳感網絡的覆蓋控制是一個多目標組合優化問題，可以通過加權形成目標的線性組合，將原始的多個子目標優化函數轉換成單目標優化函數。總目標優化函數定義為

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

其中:0

2 魚群算法的優化原理

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

2.1 基于魚群算法的網絡覆蓋優化策略

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

2.1.1 人工魚的相關定義

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

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

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

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

定義3 魚群中心。設人工魚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操作符表示求取魚群矩陣在每列出現次數較多的分量值。

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

2.1.2 人工魚行為描述

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

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

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

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

2.1.3 應用于無線傳感網絡覆蓋的AFSA算法流程

人工魚群算法求解無線傳感網絡節點工作集的基本流程如圖1所示。

根據上述流程圖，覆蓋優化策略詳細設計如下:

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

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

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

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

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

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

3 實驗仿真

仿真實驗環境設置如下:

假設無線傳感器網絡監測區域為100 m×100 m，每個無線傳感器節點的感知半徑是Rs= 9 m，采用主頻為2.4 GHz的計算機在MATLAB環境下仿真無線傳感網絡覆蓋優化。

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

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

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

迭代數本文覆蓋率/%文獻[5]覆蓋率/%本文節點數文獻[5]節點數

10079.3274.256365

15084.2480.686062

20089.4786.235859

25093.1792.915656

30096.2896.325555

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

4 結束語

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

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

參考文獻:

[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]賈杰，陳劍，常桂然.無線傳感器網絡中基于遺傳算法的優化覆蓋機制[J].控制與決策，2007， 22(17) :1289-1301.

[6]王晟，王雪，畢道偉.無線傳感器網絡動態節點選擇優化策略[J].計算機研究與發展，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]王蕊，劉國枝.基于魚群優化算法的無線傳感網絡部署[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]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式:魚群算法[J].系統工程理論與實踐，2002，22(11):32-38.

[11]李曉磊，路飛，田國會.組合優化問題的人工魚群算法應用[J].山東大學學報，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.