基于和聲搜索方法的無線傳感器網(wǎng)絡(luò)壽命優(yōu)化算法*

賴 欣， 李偉勤， 胡 澤

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

基于和聲搜索方法的無線傳感器網(wǎng)絡(luò)壽命優(yōu)化算法*

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

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

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

無線傳感器網(wǎng)絡(luò)； 壽命； 優(yōu)化算法； 和聲搜索方法

0 引 言

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

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

移動(dòng)基站的重新定位問題是圖論問題，可以通過不同的數(shù)學(xué)規(guī)劃方法進(jìn)行解決。研究表明，最優(yōu)的基站重新定位問題是NP完全問題[4]，因此，在大規(guī)模無線傳感器網(wǎng)絡(luò)下，不可能在短時(shí)間內(nèi)找到最優(yōu)解。文獻(xiàn)[5，6]分別對采用線性規(guī)劃和混合整數(shù)規(guī)劃來優(yōu)化基站的重新定位問題進(jìn)行了綜述。此外，移動(dòng)基站的重新定位問題可以通過不同的啟發(fā)式方法來解決，如，粒子群優(yōu)化[7]和遺傳算法[8]。

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

1 系統(tǒng)模型與問題定義

本節(jié)首先定義了無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型和無線能量模型，接著給出了研究問題的定義。

1.1 網(wǎng)絡(luò)模型

本文定義的無線傳感器網(wǎng)絡(luò)的模型如下：

1)基站的初始位置位于感知區(qū)域的中央，在每一輪的起始時(shí)刻，基站可以移到預(yù)先定義的節(jié)點(diǎn)；

2)網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)是同類的，并且有能源約束；

3)節(jié)點(diǎn)間的傳播通道是對稱的；

4)每個(gè)節(jié)點(diǎn)都有各自的能量和位置信息；

5)節(jié)點(diǎn)的位置是固定的。

1.2 無線能量模型

在本文的無線能量模型中，發(fā)射節(jié)點(diǎn)消耗能量用于運(yùn)行無線電和功率放大器，接收節(jié)點(diǎn)消耗能量用于運(yùn)行無線電。節(jié)點(diǎn)將bbits數(shù)據(jù)傳輸?shù)骄嚯x為d的節(jié)點(diǎn)所使用的能量為

(1)

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

ERx=Eelec×b.

(2)

其中,Eelec為收發(fā)器電路所使用的能量，Efs和Emp是為了將誤碼率控制在可接受范圍內(nèi)傳輸1bit數(shù)據(jù)所消耗的能量。當(dāng)傳輸?shù)木嚯xd小于閾值d0時(shí)，采用自由空間模型Efs；當(dāng)傳輸?shù)木嚯xd不小于閾值d0時(shí)，采用多路徑模型Emp。此處的閾值為

(3)

1.3 問題定義

圖1給出了移動(dòng)基站重新定位協(xié)議的整體結(jié)構(gòu)。該協(xié)議以輪(即循環(huán))的形式進(jìn)行，每一輪分為初始化階段和穩(wěn)態(tài)階段。在初始階段，節(jié)點(diǎn)間形成分組，并確定新的基站位置。在隨后的穩(wěn)態(tài)過程中，節(jié)點(diǎn)之間進(jìn)行數(shù)據(jù)的傳輸。在分組的形成中，本文提出了一種模糊C-means聚類算法用戶優(yōu)化無線傳感器網(wǎng)絡(luò)的基本結(jié)構(gòu)。此后，根據(jù)選擇的每個(gè)分組的頭節(jié)點(diǎn)的位置，在感知區(qū)域中確定基站的新位置。每個(gè)分組的頭節(jié)點(diǎn)負(fù)責(zé)收集本組內(nèi)節(jié)點(diǎn)的數(shù)據(jù)，并與基站交互。本文的目的是最小化每個(gè)分組的頭節(jié)點(diǎn)與基站之間的距離。為了實(shí)現(xiàn)上述目標(biāo)，本文應(yīng)用和聲搜索算法用于確定新的基站的位置。

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

節(jié)點(diǎn)之間的數(shù)據(jù)傳輸發(fā)生在穩(wěn)態(tài)過程。在初始化階段完成后，分組內(nèi)的每一個(gè)節(jié)點(diǎn)收到一條關(guān)于本組頭節(jié)點(diǎn)的信息。傳感器節(jié)點(diǎn)以很短的時(shí)間打開無線組件收集信息，并將數(shù)據(jù)發(fā)送到分組的頭節(jié)點(diǎn)。頭節(jié)點(diǎn)收集本組節(jié)點(diǎn)發(fā)來的數(shù)據(jù)，壓縮后發(fā)往基站。由于傳輸?shù)臄?shù)據(jù)總量減少了，因而，導(dǎo)致整個(gè)網(wǎng)絡(luò)的能量消耗減少。

2 協(xié)議描述

在無線傳感器網(wǎng)絡(luò)中，基站的最佳位置由每個(gè)組的頭節(jié)點(diǎn)決定。理想情況下，基站應(yīng)當(dāng)位于所有頭節(jié)點(diǎn)的中心。但實(shí)際上，尋找該中心位置是一個(gè)NP完全問題。當(dāng)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)規(guī)模很大時(shí)，準(zhǔn)確算法的執(zhí)行時(shí)間長，節(jié)點(diǎn)消耗的能量多，必須采用近似算法。本文提出一種基于和聲搜索算法的基站位置選擇協(xié)議。和聲搜索算法的搜索空間限制在頭節(jié)點(diǎn)位置的邊界，可以大大減小算法的復(fù)雜性?；诤吐曀阉魉惴ǖ幕局匦露ㄎ粎f(xié)議如下：

1)和聲搜索初始化

在和聲算法中，優(yōu)化問題是一個(gè)最小化或者最大化問題，即最小化或者最大化目標(biāo)函數(shù)f(a)，使得ai∈Ai,i=1,2,…N，其中,a為決策變量的集合{ai}，A為決策變量的取值范圍Ai={ai(1),ai(2),…，ai(M)}，M為相應(yīng)決策變量的值域的大小，N為決策變量的個(gè)數(shù)。在傳感器網(wǎng)絡(luò)中，中心節(jié)點(diǎn)距離所有分組的距離的最大值為

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

(4)

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

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

(5)

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

2)和聲記憶庫初始化

和聲記憶庫是一個(gè)由問題的解構(gòu)成的矩陣，如公式(6)所示。在該步驟中，隨機(jī)產(chǎn)生若干解，并按照目標(biāo)函數(shù)對這些解進(jìn)行反序排列

(6)

其中,HMS為和聲庫的大小，矩陣中的每一個(gè)元素為實(shí)數(shù)，表示新基站的位置坐標(biāo)。每一個(gè)和聲庫向量ai的構(gòu)建公式為

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

(7)

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

(8)

其中,rand(1,k)為產(chǎn)生一個(gè)1～k的整數(shù)的隨機(jī)函數(shù)，maxChsLocx和maxChsLocy分別是所有頭節(jié)點(diǎn)位置的x軸和y軸坐標(biāo)的上屆，minChsLocx和minChsLocy分別是所有頭節(jié)點(diǎn)位置的x軸和y軸坐標(biāo)的下屆，k為節(jié)點(diǎn)的分組個(gè)數(shù)。式(8)產(chǎn)生的位置坐標(biāo)可以保證基站位于所有頭節(jié)點(diǎn)的中間，因而是有效的。

3)和聲優(yōu)化

(9)

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

4)和聲庫更新

5)算法停止

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

3 模擬實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)設(shè)置

為了對提出的協(xié)議進(jìn)行驗(yàn)證，本文應(yīng)用Matlab模擬了100個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)，并進(jìn)行了2組實(shí)驗(yàn)。在第一組實(shí)驗(yàn)中，傳感器節(jié)點(diǎn)隨機(jī)部署在100 m×100 m 的區(qū)域內(nèi)，并且保證沒有相同的節(jié)點(diǎn)在同一位置。在第二組實(shí)驗(yàn)中，傳感器節(jié)點(diǎn)隨機(jī)部署在500 m×500 m的區(qū)域內(nèi)，同時(shí)也保證每個(gè)位置最多含有一個(gè)節(jié)點(diǎn)。

在初始情況下，基站設(shè)置在感知區(qū)域的中間。當(dāng)基站到達(dá)目的位置后，先進(jìn)行數(shù)據(jù)的收集，然后再重新確定新的基站位置。在每一輪基站選擇結(jié)束后，將新的分組頭節(jié)點(diǎn)位置發(fā)送到基站，基站根據(jù)協(xié)議計(jì)算新的基站的位置，并移動(dòng)到新的位置坐標(biāo)。本文將節(jié)點(diǎn)分為5個(gè)組，即k=5，每個(gè)節(jié)點(diǎn)的初始能量為2 J。

模擬實(shí)驗(yàn)中的參數(shù)設(shè)置為Eelec=50 pJ/bit，Efs=50 pJ/bit/m2，Emp=0.001 3 pJ/bit/m4。局部節(jié)點(diǎn)向分組的頭節(jié)點(diǎn)發(fā)送的消息和頭節(jié)點(diǎn)向基站發(fā)送的消息的大小為b=4 000 bits?？刂菩盘柕拇笮?00 bits。和聲搜索算法的參數(shù)分別為HMCR=0.95，PAR=0.3，HMS=30，迭代次數(shù)NI=3 000。

3.2 實(shí)驗(yàn)結(jié)果

為了評價(jià)提出的方法的性能，實(shí)驗(yàn)將本文提出的協(xié)議與文獻(xiàn)[10]提出的模糊聚類協(xié)議進(jìn)行對比。模糊聚類方法與本文提出的方法相似，都將傳感器節(jié)點(diǎn)進(jìn)行分組，然后選出頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的傳輸。區(qū)別在于，本文在對節(jié)點(diǎn)進(jìn)行分組后，根據(jù)分組的頭節(jié)點(diǎn)動(dòng)態(tài)的調(diào)整基站的位置。

本文提出的協(xié)議由于利用頭節(jié)點(diǎn)對局部數(shù)據(jù)進(jìn)行壓縮傳輸?shù)交?，其傳輸?shù)臄?shù)據(jù)總量減少了，能耗更低。圖2給出了基站在2種方法下接收到的數(shù)據(jù)總量對比。從該圖可以看出：本文提出的協(xié)議在2組實(shí)驗(yàn)中傳輸?shù)臄?shù)據(jù)都低于模糊聚類方法。此外，在500 m×500 m的實(shí)驗(yàn)中，數(shù)據(jù)的傳輸總量減少的更為明顯。這表明本文提出的方法在傳感器節(jié)點(diǎn)部署稀疏的大區(qū)域內(nèi)可以更好減少數(shù)據(jù)的傳輸量，從而能更好地節(jié)約傳感器節(jié)點(diǎn)的能量。

圖2 數(shù)據(jù)傳輸總量對比圖Fig 2 Comparison of data transmission amount

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

圖3 活躍節(jié)點(diǎn)隨迭代次數(shù)的變化(感知區(qū)域100 m×100 m)Fig 3 Change of active nodes vs iteration numbers(sensing area 100 m×100 m)

圖4 活躍節(jié)點(diǎn)隨迭代次數(shù)的變化(感知區(qū)域500 m×500 m)Fig 4 Change of active nodes vs iteration numbers (sensing area 500 m×500 m)

實(shí)驗(yàn)同時(shí)對比了2種算法在不同傳感器環(huán)境下，初始失效節(jié)點(diǎn)和最終失效節(jié)點(diǎn)的時(shí)間對比，對比結(jié)果如表1所示。初始失效節(jié)點(diǎn)為網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間，最終失效節(jié)點(diǎn)為網(wǎng)絡(luò)中最后一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間。當(dāng)網(wǎng)絡(luò)中最后一個(gè)傳感器節(jié)點(diǎn)的能量耗盡時(shí)，傳感器網(wǎng)絡(luò)消失。從表1可以看出，由于本文提出的協(xié)議根據(jù)和聲搜索算法動(dòng)態(tài)的調(diào)整基站的位置，使得節(jié)點(diǎn)的能量消耗相對均衡，因而初始失效節(jié)點(diǎn)的時(shí)間滯后。此外，由于本文在動(dòng)態(tài)調(diào)整基站的同時(shí)，使得基站與數(shù)據(jù)傳輸節(jié)點(diǎn)的距離近了，導(dǎo)致數(shù)據(jù)傳輸消耗的能量少，因而網(wǎng)絡(luò)的壽命更長。

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

4 結(jié)束語

為了快速確定基站位置的更新，減小基站與數(shù)據(jù)傳輸節(jié)點(diǎn)的距離，降低數(shù)據(jù)傳輸量，本文將傳感器節(jié)點(diǎn)進(jìn)行分組并選擇投節(jié)點(diǎn)，并通過頭節(jié)點(diǎn)對數(shù)據(jù)壓縮后傳輸?shù)交尽Ｔ诨疚恢玫膭?dòng)態(tài)更新中，本文提出了一種基于和聲搜索方法的基站位置更新協(xié)議。模擬實(shí)驗(yàn)表明:提出的協(xié)議與模糊聚類協(xié)議相比，傳輸數(shù)據(jù)總量更小，傳感器節(jié)點(diǎn)的能量使用率更低，能更好地提高無線傳感器網(wǎng)絡(luò)的整體使用壽命。

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

[2] 沈 波,張世永,鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),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”計(jì)劃資助項(xiàng)目(2007AA090801—03)；國家重大專項(xiàng)資助項(xiàng)目(2008ZX05026—001—09)；國家自然科學(xué)基金資助項(xiàng)目(51304165)；四川省教育廳資助項(xiàng)目(14ZB0052)

TP 319

A

1000—9787(2014)08—0134—04

賴 欣(1981-)，女，四川蓬安人，碩士，講師，主要研究方向?yàn)閭鞲衅骷夹g(shù)、自動(dòng)化技術(shù)。