基于和聲搜索方法的無線傳感器網絡壽命優化算法*

賴 欣， 李偉勤， 胡 澤

(1.西南石油大學 電氣信息學院，四川 成都 610500;2.電子科技大學 通信與信息工程學院，四川 成都 610054)

基于和聲搜索方法的無線傳感器網絡壽命優化算法*

賴 欣1， 李偉勤2， 胡 澤1

(1.西南石油大學 電氣信息學院，四川 成都 610500;2.電子科技大學 通信與信息工程學院，四川 成都 610054)

在無線傳感器網絡中，基站位置的動態調整可以提高網絡的壽命，然而基站位置的最優化問題是NP完全問題。為了快速地更新基站的位置并減少數據的交互總量，提出了一種基于和聲搜索方法的無線傳感器網絡壽命優化算法。首先，通過聚類方法將傳感器節點分成若干組。其次，在每一個組中選出頭節點，應用頭節點對組中節點的數據進行壓縮并與基站進行數據交互。最后，提出一種基于和聲搜索方法的基站位置動態更新協議。實驗表明：提出的協議與模糊聚類協議相比，傳輸數據總量更小，傳感器節點的能量使用率更低，能更好地提高傳感器網絡的整體使用壽命。

無線傳感器網絡； 壽命； 優化算法； 和聲搜索方法

0 引 言

無線傳感器網絡(WSNs)在民用和軍用領域都有著廣泛的應用，例如:環境監測，緊急救援，醫療服務，交通控制和目標跟蹤等[1]。在傳感器節點中，很大一部分能量都用于節點自身與基站之間的數據交互，因此，高效的路由協議在減少數據交互的同時可以延長傳感器節點的使用壽命。由于傳感器節點的能源都是輕量級的電池提供，高效的路由協議在減少傳感器節點能源損耗的同時，可相應地增加了傳感器網絡的整體使用壽命[2]。

無線傳感器網絡基礎設施中基站節點的選擇對于傳感器節點的能源消耗有著舉足輕重的作用。當傳感器節點與基站之間的距離增大時，傳感器節點的能源損耗也相應地增大；相反，傳感器節點與基站之間的距離變小，那么傳感器節點的能源損耗也減少。因此，選擇最佳的基站位置可以減少傳感器節點的能源損耗，從而增大整個傳感器網絡的使用壽命。為了解決上述問題，可以采用移動基站來替代固定基站，從而平衡整個傳感器網絡的能源，以提高網絡的使用壽命[3]。

移動基站的重新定位問題是圖論問題，可以通過不同的數學規劃方法進行解決。研究表明，最優的基站重新定位問題是NP完全問題[4]，因此，在大規模無線傳感器網絡下，不可能在短時間內找到最優解。文獻[5，6]分別對采用線性規劃和混合整數規劃來優化基站的重新定位問題進行了綜述。此外，移動基站的重新定位問題可以通過不同的啟發式方法來解決，如，粒子群優化[7]和遺傳算法[8]。

和聲搜索算法[9]是一種元啟發式優化算法，該算法在解決優化問題時模擬音樂家進行演奏，并將演奏表現調整到協調且美妙。為了研究基站重新定位問題，本文提出了一種基于和聲搜索算法的優化框架，將無線傳感器網絡中的節點聚類成不同的組。在每個組中選出一個頭節點，頭節點收集同組中其它節點發來的數據，在將數據進行過濾后發往基站。在這種結構中，和聲搜索算法用來尋找基站的最佳位置，即基站應當接近每個組的頭節點，而不是網絡中所有節點。

1 系統模型與問題定義

本節首先定義了無線傳感器網絡的網絡模型和無線能量模型，接著給出了研究問題的定義。

1.1 網絡模型

本文定義的無線傳感器網絡的模型如下：

1)基站的初始位置位于感知區域的中央，在每一輪的起始時刻，基站可以移到預先定義的節點；

2)網絡中所有傳感器節點是同類的，并且有能源約束；

3)節點間的傳播通道是對稱的；

4)每個節點都有各自的能量和位置信息；

5)節點的位置是固定的。

1.2 無線能量模型

在本文的無線能量模型中，發射節點消耗能量用于運行無線電和功率放大器，接收節點消耗能量用于運行無線電。節點將bbits數據傳輸到距離為d的節點所使用的能量為

(1)

接收該消息所使用的能量為

ERx=Eelec×b.

(2)

其中,Eelec為收發器電路所使用的能量，Efs和Emp是為了將誤碼率控制在可接受范圍內傳輸1bit數據所消耗的能量。當傳輸的距離d小于閾值d0時，采用自由空間模型Efs；當傳輸的距離d不小于閾值d0時，采用多路徑模型Emp。此處的閾值為

(3)

1.3 問題定義

圖1給出了移動基站重新定位協議的整體結構。該協議以輪(即循環)的形式進行，每一輪分為初始化階段和穩態階段。在初始階段，節點間形成分組，并確定新的基站位置。在隨后的穩態過程中，節點之間進行數據的傳輸。在分組的形成中，本文提出了一種模糊C-means聚類算法用戶優化無線傳感器網絡的基本結構。此后，根據選擇的每個分組的頭節點的位置，在感知區域中確定基站的新位置。每個分組的頭節點負責收集本組內節點的數據，并與基站交互。本文的目的是最小化每個分組的頭節點與基站之間的距離。為了實現上述目標，本文應用和聲搜索算法用于確定新的基站的位置。

圖1 基站位置更新流程Fig 1 Base station location update process

節點之間的數據傳輸發生在穩態過程。在初始化階段完成后，分組內的每一個節點收到一條關于本組頭節點的信息。傳感器節點以很短的時間打開無線組件收集信息，并將數據發送到分組的頭節點。頭節點收集本組節點發來的數據，壓縮后發往基站。由于傳輸的數據總量減少了，因而，導致整個網絡的能量消耗減少。

2 協議描述

在無線傳感器網絡中，基站的最佳位置由每個組的頭節點決定。理想情況下，基站應當位于所有頭節點的中心。但實際上，尋找該中心位置是一個NP完全問題。當傳感器網絡中節點規模很大時，準確算法的執行時間長，節點消耗的能量多，必須采用近似算法。本文提出一種基于和聲搜索算法的基站位置選擇協議。和聲搜索算法的搜索空間限制在頭節點位置的邊界，可以大大減小算法的復雜性。基于和聲搜索算法的基站重新定位協議如下：

1)和聲搜索初始化

在和聲算法中，優化問題是一個最小化或者最大化問題，即最小化或者最大化目標函數f(a)，使得ai∈Ai,i=1,2,…N，其中,a為決策變量的集合{ai}，A為決策變量的取值范圍Ai={ai(1),ai(2),…，ai(M)}，M為相應決策變量的值域的大小，N為決策變量的個數。在傳感器網絡中，中心節點距離所有分組的距離的最大值為

fobj=max?k∈K{d(ai,Ck)}.

(4)

本文的目標是找出找到一個中心位置，使其距離所有分組的最大距離最小化，即

minfobj=min max?k∈K{d(ai,Ck)}.

(5)

采用和聲搜索算法，通過最小化公式(5)的目標函數得到相應的位置坐標，并將該位置坐標作為新的基站位置。

2)和聲記憶庫初始化

和聲記憶庫是一個由問題的解構成的矩陣，如公式(6)所示。在該步驟中，隨機產生若干解，并按照目標函數對這些解進行反序排列

(6)

其中,HMS為和聲庫的大小，矩陣中的每一個元素為實數，表示新基站的位置坐標。每一個和聲庫向量ai的構建公式為

ai=[bsi,x,bsi,y].

(7)

其中,第i個向量的x軸坐標和t軸坐標分別為bsi,x和bsi,y。為了保證初始化的和聲庫中包含若干有效的和聲向量，需要滿足以下公式

(8)

其中,rand(1,k)為產生一個1～k的整數的隨機函數，maxChsLocx和maxChsLocy分別是所有頭節點位置的x軸和y軸坐標的上屆，minChsLocx和minChsLocy分別是所有頭節點位置的x軸和y軸坐標的下屆，k為節點的分組個數。式(8)產生的位置坐標可以保證基站位于所有頭節點的中間，因而是有效的。

3)和聲優化

(9)

其中,變量bw為一個任意的距離帶寬，該變量用來提升和聲搜索算法的性能。概率PAR通過調整頻率來模擬音樂，可以對新產生的和聲向量進行微調，從而在搜索空間中發現更多的解。

4)和聲庫更新

5)算法停止

重復第3和第4步，直到算法完成了最大迭代次數。最后，在和聲矩陣向量中選出最優值作為和聲算法的解，即基站的新的位置。

3 模擬實驗與結果

3.1 實驗設置

為了對提出的協議進行驗證，本文應用Matlab模擬了100個節點的傳感器網絡，并進行了2組實驗。在第一組實驗中，傳感器節點隨機部署在100 m×100 m 的區域內，并且保證沒有相同的節點在同一位置。在第二組實驗中，傳感器節點隨機部署在500 m×500 m的區域內，同時也保證每個位置最多含有一個節點。

在初始情況下，基站設置在感知區域的中間。當基站到達目的位置后，先進行數據的收集，然后再重新確定新的基站位置。在每一輪基站選擇結束后，將新的分組頭節點位置發送到基站，基站根據協議計算新的基站的位置，并移動到新的位置坐標。本文將節點分為5個組，即k=5，每個節點的初始能量為2 J。

模擬實驗中的參數設置為Eelec=50 pJ/bit，Efs=50 pJ/bit/m2，Emp=0.001 3 pJ/bit/m4。局部節點向分組的頭節點發送的消息和頭節點向基站發送的消息的大小為b=4 000 bits。控制信號的大小為200 bits。和聲搜索算法的參數分別為HMCR=0.95，PAR=0.3，HMS=30，迭代次數NI=3 000。

3.2 實驗結果

為了評價提出的方法的性能，實驗將本文提出的協議與文獻[10]提出的模糊聚類協議進行對比。模糊聚類方法與本文提出的方法相似，都將傳感器節點進行分組，然后選出頭節點進行數據的傳輸。區別在于，本文在對節點進行分組后，根據分組的頭節點動態的調整基站的位置。

本文提出的協議由于利用頭節點對局部數據進行壓縮傳輸到基站，其傳輸的數據總量減少了，能耗更低。圖2給出了基站在2種方法下接收到的數據總量對比。從該圖可以看出：本文提出的協議在2組實驗中傳輸的數據都低于模糊聚類方法。此外，在500 m×500 m的實驗中，數據的傳輸總量減少的更為明顯。這表明本文提出的方法在傳感器節點部署稀疏的大區域內可以更好減少數據的傳輸量，從而能更好地節約傳感器節點的能量。

圖2 數據傳輸總量對比圖Fig 2 Comparison of data transmission amount

實驗測試了2種算法的能量消耗隨著迭代次數的變化。圖3和圖4分別為2種網絡拓撲下，傳感器網絡的能源消耗隨著時間的變化圖。從圖中可以看出：本文提出的基于和聲搜索的基站位置更新算法與模糊聚類方法隨著時間的變化，逐漸耗盡傳感器網絡的能量。在500m×500m的傳感器網絡中，由于傳感器節點數是相同的，所有傳感器之間的距離較遠，因而能量損耗的速度快于100m×100m的傳感器網絡。在2種算法的對比中，本文提出的方法在同一時間的活躍節點數高于模糊聚類方法，并且網絡節點耗盡的時間要滯后與模糊聚類方法。

圖3 活躍節點隨迭代次數的變化(感知區域100 m×100 m)Fig 3 Change of active nodes vs iteration numbers(sensing area 100 m×100 m)

圖4 活躍節點隨迭代次數的變化(感知區域500 m×500 m)Fig 4 Change of active nodes vs iteration numbers (sensing area 500 m×500 m)

實驗同時對比了2種算法在不同傳感器環境下，初始失效節點和最終失效節點的時間對比，對比結果如表1所示。初始失效節點為網絡中第一個節點能量耗盡的時間，最終失效節點為網絡中最后一個節點能量耗盡的時間。當網絡中最后一個傳感器節點的能量耗盡時，傳感器網絡消失。從表1可以看出，由于本文提出的協議根據和聲搜索算法動態的調整基站的位置，使得節點的能量消耗相對均衡，因而初始失效節點的時間滯后。此外，由于本文在動態調整基站的同時，使得基站與數據傳輸節點的距離近了，導致數據傳輸消耗的能量少，因而網絡的壽命更長。

表1 初始和最終失效節點的時間對比(單位：s)Tab 1 Comparison of time between initial and final failure nodes(unit:s)

4 結束語

為了快速確定基站位置的更新，減小基站與數據傳輸節點的距離，降低數據傳輸量，本文將傳感器節點進行分組并選擇投節點，并通過頭節點對數據壓縮后傳輸到基站。在基站位置的動態更新中，本文提出了一種基于和聲搜索方法的基站位置更新協議。模擬實驗表明:提出的協議與模糊聚類協議相比，傳輸數據總量更小，傳感器節點的能量使用率更低，能更好地提高無線傳感器網絡的整體使用壽命。

[1] Lewis F L.Wireless sensor networks[J].Smart environments:Technologies,protocols,and applications,2004,8(5):11-46.

[2] 沈 波,張世永,鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報,2006,17(7):1588-1600.

[3] Vlajic N,Stevanovic D.Sink mobility in wireless sensor networks:When theory meets reality[C]∥Sarnoff Symposium,2009,SARNOFF’09,IEEE,2009:1-8.

[4] Akkaya K,Younis M,Youssef W.Positioning of base stations in wireless sensor networks[J].Communications Magazine,IEEE,2007,45(4):96-102.

[5] Cheng Z,Perillo M,Heinzelman W B.General network lifetime and cost models for evaluating sensor network deployment strategies[J].IEEE Transactions on Mobile Computing,2008,7(4):484-497.

[6] Zhao M,Yang Y.Bounded relay hop mobile data gathering in wireless sensor networks[J].IEEE Transactions on Computers,2012,61(2):265-277.

[7] Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.

[8] Ferentinos K P,Tsiligiridis T A.Adaptive design optimization of wireless sensor networks using genetic algorithms [J].Computer Networks,2007,51(4):1031-1051.

[9] Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:Harmony search[J].Simulation,2001,76(2):60-68.

[10] Alia O M.A decentralized fuzzy clustering-based energy-efficient routing protocol for wireless sensor networks[C]∥Proceedings of the 13th Annual Wireless Telecommunications Symposium,Washington,DC,USA,2014:145-147.

Lifetime optimization algorithm for WSNs based on harmony searching method*

LAI Xin1, LI Wei-qin2, HU Ze1

(1.School of Electrical and Information,Southwest Petroleum University,Chengdu 610500,China;2.School of Communication and Information Engineering,University of Electronic Science and Technology,Chengdu 610054,China)

In wireless sensor networks(WSNs),dynamic regulation of position of base station can improve lifetime of the whole networks,however,the optimization problem of base station location is NP-complete problem.In order to relocate the base station quickly and reduce the total amount of exchange data,propose a lifetime optimization algorithm based on harmony searching for WSNs.Firstly,through clustering method,divide sensor nodes into groups.Secondly,select head node in each group,compress datas in each group and apply the head node to exchange data with the base station.Finally,propose a base station relocation protocol based on harmony searching.The experiments show that compared with the fuzzy cluster protocol,the proposed protocol has less data transmission amount and low energy usage rate,and then can better improve the whole lifetime of WSNs.

wireless sensor networks(WSNs); lifetime; optimization algorithm; harmony searching method

10.13873/J.1000—9787(2014)08—0134—04

2014—05—19

國家“863”計劃資助項目(2007AA090801—03)；國家重大專項資助項目(2008ZX05026—001—09)；國家自然科學基金資助項目(51304165)；四川省教育廳資助項目(14ZB0052)

TP 319

A

1000—9787(2014)08—0134—04

賴 欣(1981-)，女，四川蓬安人，碩士，講師，主要研究方向為傳感器技術、自動化技術。