Mobile Path Selection Algorithm of Sink Node for Optimizing Network Lifetime*

WANG Zhangquan，CHEN Yourong，YU Lizhe，REN Tiaojuan

(College of Information Science and Technology，Zhejiang Shuren University，Hangzhou 310015，China)

Mobile Path Selection Algorithm of Sink Node for Optimizing Network Lifetime*

WANG Zhangquan，CHEN Yourong*，YU Lizhe，REN Tiaojuan

(College of Information Science and Technology，Zhejiang Shuren University，Hangzhou 310015，China)

To overcome the energy hole problem in wireless sensor networks，optimization method is used and mobile path selection algorithm of Sink node for optimizing network lifetime(MPSA)is researched.In MPSA algorithm，the monitoring area of single-hop transmission wireless sensor network is divided into multiple grids of same size.Sink node can move to any grid’s center and stay to gather data in the single-hop maximum communication range.Full node coverage condition of stay location and node energy consumption are analyzed.Then the optimization model which weighs network lifetime and mobile journey is established.The modified genetic algorithm is proposed to solve the model.The steps such as chromosome evaluation，selection，crossover，mutation，minimum coverage processing and isolated nodes processing are iteratively executed.Finally the mobile scheme of Sink node for optimizing network lifetime is obtained.Simulation results show that MPSA algorithm can improve the network lifetime and keep mobile journey at small range.In the aspect of improving network lifetime，it is better than RCC(range constrained clustering)algorithm.

wireless sensor networks;network lifetime;path selection;optimization algorithm

無(wú)線傳感網(wǎng)WSNs(Wireless Sensor Networks)主要由分布在監(jiān)測(cè)區(qū)域內(nèi)的大量傳感節(jié)點(diǎn)、Sink節(jié)點(diǎn)和監(jiān)控中心組成。傳感節(jié)點(diǎn)監(jiān)測(cè)各種環(huán)境參數(shù)，并通過逐跳通信的方式將感知的數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。當(dāng)Sink節(jié)點(diǎn)收集和處理其監(jiān)測(cè)范圍內(nèi)的傳感節(jié)點(diǎn)數(shù)據(jù)后，通過GPRS、3G等通信方式轉(zhuǎn)發(fā)給監(jiān)控中心。監(jiān)控中心收集、處理和顯示所有傳感節(jié)點(diǎn)的數(shù)據(jù)，并提供給用戶參考和使用［1］。WSNs通常應(yīng)用在室內(nèi)/室外的環(huán)境、衛(wèi)生和健康、電力、庫(kù)存位置、工廠和過程自動(dòng)化、地震和結(jié)構(gòu)等方面的監(jiān)測(cè)和動(dòng)物、人類、車輛等目標(biāo)的跟蹤中［2］，目前已成為熱門研究領(lǐng)域，受到政府、學(xué)術(shù)界和產(chǎn)業(yè)界的高度重視。

在無(wú)線傳感網(wǎng)中，傳感節(jié)點(diǎn)通常采用電池供電，例如，Crossbow公司的IRIS、MICA等節(jié)點(diǎn)都采用兩節(jié)AA電池供電［3］。一般情況下，傳感節(jié)點(diǎn)分布在無(wú)人看管的環(huán)境中，其電池很難更新或充電。經(jīng)過有限的時(shí)間后，傳感節(jié)點(diǎn)會(huì)消耗完自身的能量而失效。但是在無(wú)線傳感網(wǎng)的應(yīng)用中，通常要求無(wú)線傳感網(wǎng)能工作幾個(gè)月或一年，且不能充電。因此降低節(jié)點(diǎn)的能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間是無(wú)線傳感網(wǎng)的一個(gè)重要研究?jī)?nèi)容。

但是，在周期性收集數(shù)據(jù)的靜態(tài)無(wú)線傳感網(wǎng)(所有節(jié)點(diǎn)位置固定不變)中，分布在Sink節(jié)點(diǎn)周圍的傳感節(jié)點(diǎn)比其他地方的傳感節(jié)點(diǎn)消耗更多的能量，且失效較早。這是因?yàn)檫@些傳感節(jié)點(diǎn)除了發(fā)送自身感知的數(shù)據(jù)外，還較多承擔(dān)其他傳感節(jié)點(diǎn)的數(shù)據(jù)中繼任務(wù)，因此快速消耗了自身的能量。無(wú)論算法怎么調(diào)整，這種不均勻的能量消耗都會(huì)產(chǎn)生監(jiān)測(cè)區(qū)域的能量空穴問題，導(dǎo)致網(wǎng)絡(luò)的分裂，部分傳感節(jié)點(diǎn)數(shù)據(jù)不能達(dá)到Sink節(jié)點(diǎn)［4-5］。

解決靜態(tài)無(wú)線傳感網(wǎng)能量空穴、生存時(shí)間優(yōu)化等問題的一種方法是利用Sink節(jié)點(diǎn)的移動(dòng)，達(dá)到優(yōu)化網(wǎng)絡(luò)生存時(shí)間和平衡節(jié)點(diǎn)能量消耗的效果。文獻(xiàn)［6］提出范圍約束分簇方法RCC(Range Constrained Clustering)，將監(jiān)測(cè)區(qū)域內(nèi)所有節(jié)點(diǎn)分成若干個(gè)簇。每一個(gè)簇節(jié)點(diǎn)到簇中心的距離不超過最大通信距離。Sink節(jié)點(diǎn)可移動(dòng)到每一個(gè)簇中心收集數(shù)據(jù)。采用Concorde TSP(travelling Salesman Problem)求解器獲得Sink節(jié)點(diǎn)的最優(yōu)移動(dòng)路徑。文獻(xiàn)［7］將網(wǎng)絡(luò)分成若干個(gè)網(wǎng)格，提出一種基于網(wǎng)格的分簇方法GBC(Grid-Based Clustering)。在每一個(gè)網(wǎng)格內(nèi)選擇一個(gè)主簇頭，負(fù)責(zé)與其他網(wǎng)格主簇頭通信。選擇一個(gè)次簇頭，負(fù)責(zé)收集簇內(nèi)傳感節(jié)點(diǎn)的數(shù)據(jù)。Sink節(jié)點(diǎn)移動(dòng)到預(yù)先規(guī)定的多個(gè)網(wǎng)格中心收集數(shù)據(jù)，沒有考慮如何選擇Sink節(jié)點(diǎn)的移動(dòng)路徑。文獻(xiàn)［8］提出了一種基于移動(dòng)Sink節(jié)點(diǎn)的多跳數(shù)據(jù)采集方案。該算法將監(jiān)測(cè)區(qū)域分成若干個(gè)圓盤，在每一個(gè)圓盤內(nèi)根據(jù)節(jié)點(diǎn)的位置分布確定采集點(diǎn)，采用量子遺傳算法求解經(jīng)過所有采集點(diǎn)的最短路線。文獻(xiàn)［9］以滿足時(shí)延要求和最小化網(wǎng)絡(luò)整體能耗為優(yōu)化目標(biāo)，提出了一種基于虛擬點(diǎn)優(yōu)先級(jí)的移動(dòng)Sink路徑優(yōu)化選擇方法。在算法中先根據(jù)網(wǎng)格方法劃分成若干個(gè)虛擬點(diǎn)，優(yōu)先選擇優(yōu)先級(jí)高且移動(dòng)距離不小于閾值的虛擬點(diǎn)集合，采用TSP算法求解最短路徑問題。Sink節(jié)點(diǎn)沿著最短路徑移動(dòng)收集多跳通信范圍內(nèi)的傳感節(jié)點(diǎn)數(shù)據(jù)。文獻(xiàn)［10］將節(jié)點(diǎn)的通信范圍建模成大小各異且存在重疊的圓盤。在移動(dòng)過程中Sink節(jié)點(diǎn)必須進(jìn)入所有圓盤。根據(jù)不相交環(huán)路的特性構(gòu)造一條賽道，通過內(nèi)圈啟發(fā)式、彎道啟發(fā)式和捷徑搜索式尋找賽道內(nèi)近似最短路徑，但是沒有考慮Sink節(jié)點(diǎn)移動(dòng)時(shí)如何收集數(shù)據(jù)。

文獻(xiàn)［6-10］都沒有考慮網(wǎng)絡(luò)生存時(shí)間，只是提出Sink節(jié)點(diǎn)移動(dòng)的路徑選擇算法，其移動(dòng)路徑是否達(dá)到具有最優(yōu)網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案，缺乏理論分析和推導(dǎo)。針對(duì)上述存在的問題，在總結(jié)相關(guān)文獻(xiàn)的基礎(chǔ)上，采用從最優(yōu)化方法，考慮數(shù)據(jù)單跳傳輸?shù)臒o(wú)線傳感網(wǎng)，提出優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法MPSA(Mobile Path Selection Algorithm of Sink Node for Optimizing Network Lifetime)。在MPSA算法中，提出權(quán)衡網(wǎng)絡(luò)生存時(shí)間和Sink節(jié)點(diǎn)移動(dòng)路程的優(yōu)化模型。建立適應(yīng)度函數(shù)，采用改進(jìn)的遺傳算法用于求解優(yōu)化模型，獲得優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案。

1 優(yōu)化模型的建立

1.1 模型假設(shè)

在MPSA算法中，假設(shè)［11］:①僅考慮2維無(wú)線傳感網(wǎng)，即所有傳感節(jié)點(diǎn)隨機(jī)分布在2維監(jiān)測(cè)區(qū)域中。傳感節(jié)點(diǎn)位置固定不變，但是Sink節(jié)點(diǎn)可移動(dòng)到監(jiān)測(cè)區(qū)域內(nèi)任一網(wǎng)格的中心位置上收集數(shù)據(jù);②由于可采用分簇算法將停留位置分配給不同Sink節(jié)點(diǎn)，多Sink節(jié)點(diǎn)移動(dòng)的路程選擇問題可轉(zhuǎn)換成若干個(gè)單一Sink節(jié)點(diǎn)移動(dòng)的路程選擇問題。因此在MPSA算法中，僅考慮單一Sink節(jié)點(diǎn)的移動(dòng)。而且只考慮Sink節(jié)點(diǎn)在某個(gè)位置上停留一定時(shí)間的數(shù)據(jù)收集，不考慮Sink節(jié)點(diǎn)移動(dòng)過程中的數(shù)據(jù)收集;③當(dāng)傳感節(jié)點(diǎn)不能與Sink節(jié)點(diǎn)通信時(shí)，即不在其單跳最大通信范圍內(nèi)，所有傳感節(jié)點(diǎn)的感知數(shù)據(jù)保存在緩存中，并基本處于睡眠狀態(tài)。當(dāng)傳感節(jié)點(diǎn)能與Sink節(jié)點(diǎn)通信，即在其單跳最大通信范圍內(nèi)，傳感節(jié)點(diǎn)處于工作狀態(tài)，通過逐跳通信的方式將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn);④Sink節(jié)點(diǎn)能量不受限制，但是每個(gè)傳感節(jié)點(diǎn)的能量有限且不能補(bǔ)充;⑤所有節(jié)點(diǎn)可安裝GPS模塊或采用其他定位方法獲知自身的位置坐標(biāo);⑥所有傳感節(jié)點(diǎn)具有相同的性能(如感應(yīng)速率、最大通信半徑、初始能量、能耗參數(shù)等)，采用統(tǒng)一的能耗模型。

1.2 優(yōu)化模型

由于根據(jù)傳感節(jié)點(diǎn)的位置分布直接確定Sink節(jié)點(diǎn)的最優(yōu)移動(dòng)位置坐標(biāo)還存在非常大的困難。因此，將監(jiān)測(cè)區(qū)域分成n×n個(gè)大小一致的網(wǎng)格，對(duì)所有網(wǎng)格從左到右且從上到下的原則進(jìn)行統(tǒng)一的編碼(如圖1所示)。Sink節(jié)點(diǎn)可移動(dòng)到任一網(wǎng)絡(luò)中心上收集數(shù)據(jù)。令Vg表示所有網(wǎng)格中心集合，xn是Sink節(jié)點(diǎn)停留位置的狀態(tài)指示符號(hào)。xn=1表示Sink節(jié)點(diǎn)移動(dòng)到網(wǎng)格中心n上停留一段時(shí)間收集數(shù)據(jù)，即網(wǎng)格中心n在Sink節(jié)點(diǎn)的移動(dòng)路徑上。xn= 0表示Sink節(jié)點(diǎn)不停留在網(wǎng)格中心n上收集數(shù)據(jù)。Sink節(jié)點(diǎn)需要停留的位置數(shù)量是

其中，Nm表示網(wǎng)絡(luò)中Sink停留位置的數(shù)量。

圖1 網(wǎng)格分配和編號(hào)圖

如圖2所示，Sink節(jié)點(diǎn)的數(shù)據(jù)收集就是當(dāng)Sink節(jié)點(diǎn)停留在某一個(gè)位置(圖中五角星表示)上時(shí)，靜態(tài)收集其單跳最大通信范圍內(nèi)的傳感節(jié)點(diǎn)數(shù)據(jù)。定義Sink節(jié)點(diǎn)從初始位置開始，沿著某一路徑收集數(shù)據(jù)，最后返回初始位置所需要的時(shí)間為一個(gè)數(shù)據(jù)收集周期。則Sink節(jié)點(diǎn)的一個(gè)數(shù)據(jù)收集周期tc由Sink節(jié)點(diǎn)的停留時(shí)間和移動(dòng)時(shí)間兩部分組成，可表示為

式中，tv

coll表示Sink節(jié)點(diǎn)在停留位置v上的停留時(shí)間。Vm表示所有停留位置集合，dTSP表示Sink節(jié)點(diǎn)移動(dòng)遍歷所有停留位置需要移動(dòng)的最短路程(假設(shè)已知Sink節(jié)點(diǎn)的停留位置，則可以通過經(jīng)典TSP算法求解)，u表示Sink節(jié)點(diǎn)的移動(dòng)速度。

圖2Sink節(jié)點(diǎn)的數(shù)據(jù)收集

為保證Sink節(jié)點(diǎn)數(shù)據(jù)收集的全節(jié)點(diǎn)覆蓋，在Sink節(jié)點(diǎn)的數(shù)據(jù)收集中，要求每一個(gè)傳感節(jié)點(diǎn)至少在一個(gè)停留位置的單跳最大通信范圍內(nèi)，即需要滿足如下公式:

其中，di，v表示傳感節(jié)點(diǎn)i到停留位置v的距離，dmax表示節(jié)點(diǎn)單跳最大通信距離，Vs表示所有傳感節(jié)點(diǎn)的集合。

當(dāng)Sink節(jié)點(diǎn)停留在某一個(gè)位置，廣播通知周圍單跳最大通信范圍內(nèi)的所有傳感節(jié)點(diǎn)。這些傳感節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。在單跳傳輸網(wǎng)絡(luò)中，網(wǎng)絡(luò)通信協(xié)議簡(jiǎn)單。傳感節(jié)點(diǎn)只有在Sink節(jié)點(diǎn)的單跳最大通信范圍內(nèi)，才將數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)。因此傳感節(jié)點(diǎn)的能耗主要由節(jié)點(diǎn)數(shù)據(jù)發(fā)送能耗組成［11-12］。在一個(gè)數(shù)據(jù)收集周期間，節(jié)點(diǎn)i的數(shù)據(jù)發(fā)送能耗為

其中，Eelec表示發(fā)送1 bit數(shù)據(jù)時(shí)的電路電子能耗，εfs表示放大1 bit數(shù)據(jù)時(shí)的信號(hào)放大器電子能耗，fi，v表示當(dāng)Sink在停留位置v時(shí)，傳感節(jié)點(diǎn)i的數(shù)據(jù)發(fā)送速率。di，v表示傳感節(jié)點(diǎn)i到停留位置v的距離。Vi表示到傳感節(jié)點(diǎn)i的距離小于單跳最大通信范圍的所有停留位置集合。

定義網(wǎng)絡(luò)生存時(shí)間Tnet是網(wǎng)絡(luò)開始運(yùn)行到任意一個(gè)節(jié)點(diǎn)能量耗盡時(shí)所有傳感節(jié)點(diǎn)給Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)的累計(jì)工作時(shí)間的最小值(不包括睡眠時(shí)間)。假設(shè)Sink節(jié)點(diǎn)在每一個(gè)停留位置上停留時(shí)間相同，則該節(jié)點(diǎn)i的生存時(shí)間為

其中，Ei表示傳感節(jié)點(diǎn)i的初始能量，|Vi|表示集合Vi中元素的個(gè)數(shù)。

根據(jù)上述分析，網(wǎng)絡(luò)生存時(shí)間的優(yōu)化模型可表示為:

在優(yōu)化模型(6)的求解過程中，如果不對(duì)Sink節(jié)點(diǎn)的移動(dòng)路徑進(jìn)行限制，則求解的移動(dòng)路徑是Sink節(jié)點(diǎn)移動(dòng)到每一個(gè)傳感節(jié)點(diǎn)附近的網(wǎng)格中心收集數(shù)據(jù)。該方案雖然減低了節(jié)點(diǎn)的數(shù)據(jù)傳輸能耗，但是大大提高了數(shù)據(jù)收集周期內(nèi)Sink節(jié)點(diǎn)的移動(dòng)路程和移動(dòng)時(shí)間，提高了數(shù)據(jù)傳輸時(shí)延。傳感節(jié)點(diǎn)的緩存資源有限，如果數(shù)據(jù)傳輸時(shí)延較高，則部分傳感節(jié)點(diǎn)緩存空間溢出，一些采集數(shù)據(jù)不能達(dá)到Sink節(jié)點(diǎn)，被直接丟棄。因此引入Sink節(jié)點(diǎn)的移動(dòng)路程，將優(yōu)化模型(6)修改為:

2 模型的求解

如圖3所示，本算法采用保證節(jié)點(diǎn)全節(jié)點(diǎn)覆蓋的遺傳算法求解優(yōu)化模型(7)［13］，迭代執(zhí)行染色體評(píng)估、選擇、交叉、變異、最小覆蓋處理、孤立節(jié)點(diǎn)處理等步驟，最終獲得優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案。

圖3MPSA算法流程圖

令包括Sink節(jié)點(diǎn)停留位置的所有狀態(tài)指示符號(hào)的向量x=(x1，x2，…，xn2)表示染色體，M表示染色體數(shù)量，α1表示交叉概率，α2表示染色體發(fā)生變異概率，α3表示基因發(fā)生變異概率，g表示迭代次數(shù)。根據(jù)優(yōu)化模型(7)，遺傳算法的適應(yīng)度函數(shù)為

根據(jù)適應(yīng)度函數(shù)，采用以下步驟求解優(yōu)化模型(7)。

步驟1:初始化

初始化全節(jié)點(diǎn)覆蓋的M個(gè)染色體，迭代次數(shù)g=0，染色體操作數(shù)m=0，算法中α1，α2，α3等參數(shù)。

步驟2:染色體評(píng)估

計(jì)算所有染色體的適應(yīng)度，直接選擇適應(yīng)度最大的染色體繼承到下一代種群中。

步驟3:選擇和交叉

根據(jù)輪盤賭策略選擇需要交叉的2個(gè)染色體。令

其中，PPm表示累計(jì)概率，pm表示個(gè)體選擇概率。隨機(jī)選擇0到1之間的2個(gè)隨機(jī)數(shù)r1，r2。如果PPi-1≤r1＜PPi，PPj-1≤r2＜PPj，則選擇染色體i，j。

對(duì)染色體i，j進(jìn)行交叉，生成一個(gè)新的染色體k。令gk，l表示染色體k中的基因l，如式(11)所示，所有基因的選擇方法如下:產(chǎn)生一個(gè)0到1之間隨機(jī)數(shù)q，如果大于α1，則選擇染色體j中對(duì)應(yīng)基因，否則選擇染色體i中對(duì)應(yīng)基因。

經(jīng)過n2次基因交叉后，形成了一個(gè)新的染色體k。

步驟4:變異

產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，如果大于α2，則跳到步驟5，否則需要對(duì)新產(chǎn)生的染色體k執(zhí)行變異操作。如式(12)所示，產(chǎn)生一個(gè)0～1之間隨機(jī)數(shù)q，如果q大于α3，則gk，l不變化，否則改變gk，l值，即0變1，1變0。

其中，abs()表示取絕對(duì)值函數(shù)。

步驟5:最小覆蓋處理

根據(jù)染色體的所有基因值，獲得停留位置集合。計(jì)算每一個(gè)傳感節(jié)點(diǎn)到停留位置集合中每一個(gè)停留位置的距離。如果該傳感節(jié)點(diǎn)的最小距離小于dmax，則表示該傳感節(jié)點(diǎn)能與Sink節(jié)點(diǎn)通信。否則，該傳感節(jié)點(diǎn)為孤立節(jié)點(diǎn)。如果某一個(gè)停留位置的單跳最大通信范圍內(nèi)沒有傳感節(jié)點(diǎn)，則該停留位置是冗余的，將染色體中對(duì)應(yīng)基因值變成0。

步驟6:孤立節(jié)點(diǎn)處理

如果網(wǎng)絡(luò)中存在孤立節(jié)點(diǎn)，則需要添加停留位置消除孤立節(jié)點(diǎn)。為控制停留位置的增加數(shù)量，選擇單跳最大通信范圍內(nèi)孤立節(jié)點(diǎn)數(shù)量最多且距離平均值最小的網(wǎng)格中心為Sink節(jié)點(diǎn)的停留位置。經(jīng)過多次網(wǎng)格中心的選擇，直到該染色體達(dá)到全節(jié)點(diǎn)覆蓋的要求。

步驟7:返回或結(jié)束

m=m+1。如果m＜M-1，則跳到步驟3，否則g=g+1且m=0。如果迭代次數(shù)g小于gmax，則返回執(zhí)行步驟2，否則結(jié)束遺傳算法，獲得適應(yīng)度值最大的染色體，即優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案。

3 仿真實(shí)現(xiàn)和分析

3.1 仿真參數(shù)設(shè)置

在算法仿真中，僅僅考慮數(shù)據(jù)通信的能耗，不考慮其他的能耗。為方便比較算法性能，假設(shè)所有算法的數(shù)據(jù)收集周期為一個(gè)固定值。如表1所示，選擇表中參數(shù)，在MATLAB軟件上編程實(shí)現(xiàn)MPSA和RCC算法，分析相關(guān)參數(shù)對(duì)MPSA算法的影響，并比較RCC和MPSA算法。

表1 仿真參數(shù)表

3.2 算法關(guān)鍵參數(shù)分析

分析網(wǎng)格數(shù)量對(duì)MPSA算法的影響。分別選擇10×10、20×20、30×30和40×40個(gè)網(wǎng)格，選擇節(jié)點(diǎn)數(shù)量100、染色體數(shù)量30和表1中參數(shù)，隨機(jī)產(chǎn)生10個(gè)不同拓?fù)浣Y(jié)構(gòu)的無(wú)線傳感網(wǎng)，分別采用改進(jìn)的遺傳算法計(jì)算每一種拓?fù)浣Y(jié)構(gòu)的最優(yōu)染色體的適應(yīng)度，獲得每一個(gè)固定網(wǎng)格數(shù)量的最優(yōu)染色體適應(yīng)度的最大值、平均值和最小值。如圖4所示，當(dāng)網(wǎng)格數(shù)量為30×30時(shí)，其最優(yōu)染色體適應(yīng)度的最大值(矩形上面的T表示)、平均值(矩形中的紅線表示)和最小值(矩形下面的T表示)都比其他網(wǎng)格數(shù)量要高。這是因?yàn)?當(dāng)網(wǎng)格數(shù)量小于30×30時(shí)，隨著網(wǎng)格數(shù)量的增加，Sink節(jié)點(diǎn)的位置選擇范圍變大，在有限的迭代次數(shù)內(nèi)，算法可以找到較優(yōu)的移動(dòng)路徑，因此其最大值和平均值變大。但是當(dāng)網(wǎng)格數(shù)量為40×40時(shí)，即染色體具有1 600個(gè)元素，采用100次的迭代次數(shù)還無(wú)法找到較優(yōu)方案，因此其仿真結(jié)果值偏低。隨著網(wǎng)格數(shù)量的增加，染色體的元素?cái)?shù)量也增加，且需要更多的迭代次數(shù)，這都大大增加了算法的計(jì)算量，但是所獲得的最優(yōu)染色體適應(yīng)度值相差不大。因此為降低算法的計(jì)算量，在MPSA算法中，選擇網(wǎng)格數(shù)量10×10。

圖4 網(wǎng)格數(shù)量對(duì)最優(yōu)染色體適應(yīng)度的影響

分析染色體數(shù)量對(duì)MPSA算法的影響。分別選擇10、20、30和40個(gè)染色體，選擇網(wǎng)格數(shù)量10×10，節(jié)點(diǎn)數(shù)量100和表1中參數(shù)，獲得染色體數(shù)量對(duì)最優(yōu)染色體適應(yīng)度的影響圖5。如圖5所示，隨著染色體數(shù)量的增加，最優(yōu)染色體適應(yīng)度的平均值也隨之增加。當(dāng)染色體數(shù)量為30和40時(shí)，兩者的平均值相差不大。這是因?yàn)?當(dāng)染色體數(shù)量小于30時(shí)，由于參與計(jì)算的染色體較少，在有限的迭代次數(shù)中，MPSA算法還沒有尋找到較優(yōu)方案，需要更多的迭代次數(shù)。當(dāng)染色體數(shù)量為30和40時(shí)，有較多的染色體參與移動(dòng)路徑的迭代計(jì)算中，在有限的迭代次數(shù)中獲得的較優(yōu)方案，因此兩者平均值相差不大。但是由于染色體數(shù)量過大，會(huì)增加算法的計(jì)算量，因此在MPSA算法中，選擇染色體個(gè)數(shù)30。

圖5 染色體數(shù)量對(duì)最優(yōu)染色體適應(yīng)度的影響

3.3 算法仿真結(jié)果分析

為了驗(yàn)證算法的有效性，比較RCC和MPSA算法。根據(jù)3.2節(jié)的關(guān)鍵參數(shù)研究，選擇節(jié)點(diǎn)數(shù)量100，網(wǎng)格數(shù)量10×10，染色體數(shù)量30和表1中參數(shù)，獲得RCC和MPSA算法的數(shù)據(jù)收集圖。如圖6所示，RCC算法在每一次分簇時(shí)，選擇在單跳最大通信范圍內(nèi)能覆蓋最多傳感節(jié)點(diǎn)的區(qū)域中心作為簇中心，因此Sink節(jié)點(diǎn)的停留位置數(shù)量只有9個(gè)，但是節(jié)點(diǎn)的數(shù)據(jù)傳輸能耗較大。如圖7所示，MPSA算法雖然選擇了15個(gè)停留位置，但是每一個(gè)停留位置到其單跳最大通信范圍內(nèi)傳感節(jié)點(diǎn)的平均距離較短，降低了節(jié)點(diǎn)的數(shù)據(jù)傳輸能耗。由于MPSA算法停留位置間距較短而RCC算法的停留位置間距較長(zhǎng)，所以兩者的移動(dòng)路程相差不大。

圖6RCC算法的數(shù)據(jù)收集圖

圖7MPSA算法的數(shù)據(jù)收集圖

在仿真區(qū)域內(nèi)隨機(jī)均勻分布20、40、60、80、100、120、140、160、180和200個(gè)傳感節(jié)點(diǎn)。選擇網(wǎng)格數(shù)量10×10，染色體數(shù)量30和表1中仿真參數(shù)，針對(duì)每一種傳感節(jié)點(diǎn)數(shù)量，隨機(jī)產(chǎn)生10個(gè)不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，分別計(jì)算RCC和MPSA算法的網(wǎng)絡(luò)生存時(shí)間和移動(dòng)路程，最后取其平均值作為某一傳感節(jié)點(diǎn)數(shù)量的各算法仿真比較值。

圖8 網(wǎng)絡(luò)生存時(shí)間比較圖

如圖8所示，MPSA算法的網(wǎng)絡(luò)生存時(shí)間比RCC算法高，而且隨著傳感節(jié)點(diǎn)數(shù)量降低，MPSA算法提高網(wǎng)絡(luò)生存時(shí)間的效果越明顯。這是因?yàn)镸PSA算法全面考慮監(jiān)測(cè)區(qū)域內(nèi)各個(gè)位置，在路徑選擇時(shí)以網(wǎng)絡(luò)生存時(shí)間作為一個(gè)主要考慮指標(biāo)，建立優(yōu)化模型。在遺傳算法求解中優(yōu)先繼承較好網(wǎng)絡(luò)生存時(shí)間的移動(dòng)路徑，經(jīng)過多次迭代最終獲得較優(yōu)路徑。而RCC算法沒有考慮網(wǎng)絡(luò)生存時(shí)間，因此MPSA算法能提高網(wǎng)絡(luò)生存時(shí)間。

如圖9所示，當(dāng)節(jié)點(diǎn)數(shù)量小于100時(shí)，MPSA算法的移動(dòng)路程比RCC算法的移動(dòng)路程略大，反之RCC算法的移動(dòng)路程比MPSA算法的移動(dòng)路程略大，且兩者的移動(dòng)路程都較小。這是因?yàn)镸PSA算法在染色體的適應(yīng)度函數(shù)中加入了Sink節(jié)點(diǎn)的移動(dòng)路程。在提高網(wǎng)絡(luò)生存時(shí)間的同時(shí)盡可能降低Sink節(jié)點(diǎn)的移動(dòng)路程。在其所獲的Sink節(jié)點(diǎn)移動(dòng)路徑中，雖然停留位置數(shù)量增加了，但是停留位置間距較短，而RCC算法的停留位置間距較長(zhǎng)，因此MPSA和RCC算法的移動(dòng)路程上下波動(dòng)，相差不大。

圖9 移動(dòng)路程比較圖

綜上所述，與RCC算法相比，MPSA算法能明顯提高網(wǎng)絡(luò)生存時(shí)間，將移動(dòng)路程保持在較小范圍內(nèi)。

4 總結(jié)

本文研究?jī)?yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法(MPSA)。首先提出系統(tǒng)假設(shè)，其次從優(yōu)化模型建立和模型求解二個(gè)方面研究MPSA算法。建立權(quán)衡網(wǎng)絡(luò)生存時(shí)間和Sink節(jié)點(diǎn)移動(dòng)路程的優(yōu)化模型。采用改進(jìn)遺傳算法用于求解優(yōu)化模型，獲得優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案。最后仿真分析關(guān)鍵參數(shù)對(duì)MPSA算法性能的影響，仿真比較RCC和MPSA算法的網(wǎng)絡(luò)生存時(shí)間和Sink節(jié)點(diǎn)的移動(dòng)路程。

MPSA算法是集中式算法。隨著節(jié)點(diǎn)數(shù)量、網(wǎng)格數(shù)量等關(guān)鍵參數(shù)的增大，算法的計(jì)算量也增加，需要較多的迭代時(shí)間才能收斂。因此下一步將研究分布式優(yōu)化算法:每一個(gè)節(jié)點(diǎn)根據(jù)局部信息建立和求解節(jié)點(diǎn)優(yōu)化模型，Sink節(jié)點(diǎn)根據(jù)周圍節(jié)點(diǎn)優(yōu)化模型的解判斷下一次的移動(dòng)位置。

［1］Yang Y，F(xiàn)onoage M I，Cardei M.Improving Network Lifetime withMobile Wireless Sensor Networks［J］.Computer Communications，2010，33(4):409-419.

［2］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292-2330.

［3］Crossbow公司節(jié)點(diǎn).http://www.memsic.com/wireless-sensor -networks/.

［4］Rao J，Biswas S.Data Harvesting in Sensor Networks Using Mobile Sinks［J］.IEEE Wireless Communications，2008，15(6):63-70.

［5］霍梅梅，鄭增威，周曉偉.移動(dòng)傳感器網(wǎng)絡(luò)及其路由協(xié)議研究進(jìn)展［J］.計(jì)算機(jī)應(yīng)用研究，2009，26(11):4010-401.

［6］Kumar A K，Sivalingam K M，Kumar A.On Reducing Delay in Mobile Data Collection Based Wireless Sensor Networks［J］.Wireless Network.2013，19(3):285-299.

［7］Thanigaivelu K，Murugan K.Grid-Based Clustering with Predefined Path Mobility for Mobile Sink Data Collection to Extend Network Lifetime in Wireless Sensor Networks［J］.IEEE Technical Review，2012，29(2):133-147.

［8］郭劍，孫力娟，許文君，等.基于移動(dòng)Sink的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案［J］.通信學(xué)報(bào)，2012，33(9):176-184.

［9］郜帥，張宏科.時(shí)延受限傳感器網(wǎng)絡(luò)移動(dòng)Sink路徑選擇方法研究［J］.電子學(xué)報(bào)，2011，39(4):742-747.

［10］袁遠(yuǎn)，彭宇行，李?yuàn)檴櫍?高效的移動(dòng)Sink路由問題的啟發(fā)式算法［J］.通信學(xué)報(bào)，2011，32(10):107-117.

［11］陳友榮，王章權(quán)，程菊花，等.基于最短路徑樹的優(yōu)化生存時(shí)間路由算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25(3):406-412.

［12］汪林云，劉文軍.無(wú)線傳感器網(wǎng)絡(luò)中帶有移動(dòng)匯點(diǎn)的能量高效的數(shù)據(jù)收集協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2012，25(5):678-682.

［13］Luo X N.Hybrid Genetic Algorithm Using a Forward Encoding Scheme for Lifetime Maximization of Wireless Sensor Networks［J］.IEEE Transactions on Evolutionary Computation，2010，14 (5):766-781.

王章權(quán)(1969-)，男，碩士，浙江諸暨人，副教授，浙江樹人大學(xué)信息科技學(xué)院，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)、控制技術(shù);

陳友榮(1982-)，男，博士，浙江蒼南人，講師，浙江樹人大學(xué)信息科技學(xué)院，主要研究方向?yàn)闊o(wú)線傳感網(wǎng)、物聯(lián)網(wǎng)。

優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法*

王章權(quán)，陳友榮*，尉理哲，任條娟
(浙江樹人大學(xué)信息科技學(xué)院，杭州310015)

為克服無(wú)線傳感網(wǎng)的能量空穴問題，采用最優(yōu)化方法，研究一種優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)路徑選擇算法(MPSA)。在MPSA算法中，將單跳傳輸?shù)臒o(wú)線傳感網(wǎng)監(jiān)測(cè)區(qū)域分成多個(gè)大小一致的網(wǎng)格，Sink節(jié)點(diǎn)可移動(dòng)到任一網(wǎng)格中心，停留收集單跳最大通信范圍內(nèi)的傳感節(jié)點(diǎn)數(shù)據(jù)。分析停留位置的全節(jié)點(diǎn)覆蓋條件和所有傳感節(jié)點(diǎn)的能耗，建立權(quán)衡網(wǎng)絡(luò)生存時(shí)間和Sink節(jié)點(diǎn)移動(dòng)路程的優(yōu)化模型。提出一種改進(jìn)的遺傳算法，用于求解優(yōu)化模型，即迭代執(zhí)行染色體評(píng)估、選擇、交叉、變異、最小覆蓋處理、孤立節(jié)點(diǎn)處理等步驟，最終獲得優(yōu)化網(wǎng)絡(luò)生存時(shí)間的Sink節(jié)點(diǎn)移動(dòng)方案。仿真結(jié)果表明:MPSA算法能提高網(wǎng)絡(luò)生存時(shí)間，將移動(dòng)路程保持在較小范圍。在提高網(wǎng)絡(luò)生存時(shí)間方面，比RCC算法更優(yōu)。

無(wú)線傳感網(wǎng);網(wǎng)絡(luò)生存時(shí)間;路徑選擇;優(yōu)化算法

TP393

A

1004－1699(2014)03－0409－07

2013-12-13修改日期:2014-03-08

C:6150P

10.3969/j.issn.1004－1699.2014.03.025

項(xiàng)目來(lái)源:浙江省自然科學(xué)基金項(xiàng)目(Y13F010013，Q12F03014);浙江省教育廳項(xiàng)目(Y201330053)