無線傳感器網絡中移動sink節點的路徑規劃

柏 琪，朱曉娟

(安徽理工大學 計算機科學與工程學院，安徽 淮南 232001)

0 引言

無線傳感器網絡中通過多跳路由匯聚到sink節點是傳統的數據收集方法。離sink節點很近的傳感器節點或簇頭，被視為sink節點的中介，需要轉發遠處傳感器節點的數據包，這會導致能量有限的傳感器節點快速消耗掉自身的能量，從而死亡，這被稱為熱點或能量空洞問題[1-4]。為了避免這種情況，使用移動sink節點來解決這一問題，將sink節點安裝在一些車輛上，圍繞網絡區域移動進行數據收集。使用移動sink進行數據收集有以下優點：

① 傳感器節點將數據轉發到移動sink節點的跳數相對較小，這會減少擁塞和數據包丟失的概率[5]；

② 移動sink節點的存儲和計算資源較充分；

③ 使用移動sink節點，在很大程度上減少某些傳感器節點數據轉發負載，可以更好地利用傳感器的能量，從而延長了整個網絡的壽命。

目前，sink節點移動的軌跡選擇主要有3種類型：隨機移動、固定移動和可控移動[6]。

在基于隨機移動的方法中，sink節點的移動軌跡不是預先設定的。例如，節點放在動物身上，動物的移動軌跡是隨機的，雖然這個方案很容易實現，它的優點是保證移動sink節點到每個節點進行收集數據的概率是相等的，但其性能是不確定的，因為它可能會產生很長的路徑，造成鏈路斷開，產生額外的能量損耗。

在固定移動中，移動sink節點將移動sink訪問一些預先指定的位置，并從傳感器節點組中收集數據，它需要只訪問有限數量的節點，但不會根據無線傳感器網絡節點的能量情況進行路線改變，缺乏靈活性。

在可控移動中，可以根據路徑反饋的信息進行路徑規劃。因此，它能夠在指定延遲限制內進行數據收集，可以很好地平衡網絡壽命與延遲的問題。

1 相關工作

近年來，為了解決能量空洞問題，提高無線傳感器網絡的生命周期，許多算法已被提議用于移動sink節點的路徑規劃。周暉等人[7]提出移動多sink 生物啟發式路徑規劃算法，采用蟻群優化作為上層算子，根據網絡運行過程中的變化，即節點數量和能量變化，實時優選下層算子集，選中的下層算子集規劃各移動sink節點的路徑。黃冰倩等人[8]首先利用圖論知識，把無線傳感器網絡看成一個連通的無向圖，將傳感器節點轉化成圖的頂點，并選取虛擬信標節點，利用蟻群算法對選取的節點進行遍歷，從而獲得移動路徑。俸皓等人[9]提出了一種新的基于螢火蟲群的路徑規劃方法。首先依據問題的特性對可行解空間進行了壓縮；然后為提高算法在高維解空間的搜索效率，對離群螢火蟲粒子設計了變異操作并設計了個體逐維移動的方式，提高了算法的求解精度并加快了算法的收斂速度。文獻[7-9]運用生物智能的路徑規劃算法，這類算法沒有考慮現實中的適用性，數據的處理和成本太高。陳友榮等人[10]提出了一種高效的距離感知路由算法,通過無線傳感器網絡的移動匯聚，匯聚節點以一定的速度沿網絡邊界采集監控數據。但是該算法中提到的障礙物和移動sink節點的移動感知問題沒有得到解決，且過于復雜導致數據傳輸速率受到影響。

與以上算法相比，結合實際情況，本文考慮合理規劃移動sink節點的路徑，最大限度延長網絡壽命。首先將移動sink節點通信范圍內的傳感器節點的剩余能量信息傳達給移動sink節點,然后通過能量密度與移動路徑選擇算法選擇出移動sink的最佳轉向點，得到sink節點移動的最優路徑。對于能量密度和具體的移動路徑選擇算法會在后面進行詳細介紹。

2 網絡模型

2.1 問題描述

無線傳感器網絡是使用同構的傳感器節點隨機部署在H×W的長方形區域內，其中每個傳感器節點都有有限電源和相同的通信半徑，并且移動sink節點能量不受限制。本文為了避免移動sink節點進行不必要的移動，規定檢測區域內的節點都為簇首，該網絡為骨干網絡[11]。

在監測區域內，假設傳感器節點呈現正態分布，四周的節點分布較稀疏，中間部分比較集中。移動sink節點從矩形區域的左邊中點出發，根據規劃的路徑進行勻速移動，在通信范圍內進行數據的收集，直到區域右邊中點，看做完成一輪采集。本文將矩形區域劃分成若干個子區域，以便更準確進行轉向點選擇。以下是一些假設。

① 每個傳感器節點在部署后保持靜止并具有唯一識別號碼；

② 假定在每個轉向點位置，移動sink節點的逗留時間可以忽略不計；

③ 所有通信都通過共享無線電建立；

④ 網絡生命周期定義為直到第一個節點死亡為止；

⑤ 假設從傳感器節點到移動sink節點沒有重傳數據，移動sink節點負責將收集到的數據傳到信息處理中心，且移動sink節點運動速度恒定不變。

2.2 能耗模型

本文提出相應的能量模型，其中單個傳感器節點在發送或接收k比特數據所需的能量為：

E1=Eeleck。

(1)

在信號放大器件上消耗的能量為：

E2=Eampd2k，

(2)

式中，Eamp為單位功率放大器的能量消耗，d為兩個節點之間的距離。所以接收消息時只存在第一步的能量消耗；發送數據所消耗的能量為兩步的和，即：

ET=E1+E2。

(3)

2.3 能量密度

本文提出的能量密度是指單位區域內傳感器節點的能量。它在一定程度上反映了傳感器網絡負載是否平衡，對于移動sink節點的轉向點也有很大影響。使用二分法劃分區域，在能量密度較高的區域會盡可能多地劃分子區域，增加轉向點的數量，避免因某個節點承載過多的轉發任務而造成能量耗盡、節點死亡的后果，達到傳感器網絡的能量平衡。能量密度的計算公式如下：

ED=RE/N，

(4)

式中，ED為能量密度，RE代表子區域內傳感器節點的剩余能量總和，N為子區域內無線傳感器節點的數量。

對于一個區域內能量密度大小，以整個網絡的能量密度T為標準，如果ED>T，則說明該子區域能量密度大，需要考慮增加轉向點；相反，如果ED

3 轉向點選擇與子區域劃分

首先對移動sink節點路徑規劃的必要性進行研究，如圖1所示。移動sink節點從A移動到B，經過整個傳感器網絡區域，這個路徑是一條固定的直線，靠近該路徑的節點可以把數據直接傳送給移動sink節點，但是由于傳感器節點的能量有限，遠離該路徑的節點想要發送數據必須經過多跳轉發才能成功。由此可以看出，這樣的路徑影響整個網絡的生命周期。

為了解決該問題，本文提出了轉向點的概念，如圖2所示。移動sink節點同樣是從A移動到B，但在移動過程中，它不是一條固定的直線路徑，而是經過多次轉折，轉折的目的是為了盡可能保證分布在路徑兩邊的傳感器節點傳送數據到移動sink節點需要轉發的次數比較少，也就是跳數減少，這樣大大均衡了網絡的能量負載，提高生命周期。

圖1 直線移動Fig.1 straight line movement

圖2 規劃路徑移動Fig.2 Planning path movement

圖3 k為4時轉折點結果Fig.3 K is the result of turning point at 4

圖4 k為2時轉折點結果Fig.4 K is the result of turning point at 2

4 簇首到移動sink的最短路徑

本文在設計移動sink的移動路徑有一個重要前提，在數據傳輸階段，如果傳輸數據距離移動sink較遠，不在其通信范圍內，此時通過另外簇首節點進行數據轉發，要保證傳輸數據路徑是最短路徑，以跳數來判斷傳輸路徑是否為最短路徑。具體步驟用Dijkstra算法[14-16]來求解。

① 給定兩個集合：已求出最短路徑節點集合S(初始時，在S中添加一個源節點V1)和未求出最短路徑的所有節點的集合U。

② 從U中選取一個距離V1最小的頂點K加入到S中(選定的距離就是V1到K的最短路徑)。且只有當該距離小于傳感器節點的一跳范圍時，才能加入S，如果兩個節點不能通過一跳到達，距離就為∞，排除該節點。

③ 以K為新考慮的中間點，修改U中各節點的距離。若從源節點V經過頂點到節點U的路徑距離比原來不經過節點K的路徑距離短，則修改V1到U的距離。

④ 重復步驟②、③直到sink節點加入到S中，就能知道源點V1到sink節點進行數據傳輸的最短路徑。

5 路徑規劃算法

通過以上子區域的劃分、轉向點的選擇和傳輸數據的最短路徑可以得出最終的路徑規劃算法。算法思想為：將傳感器網絡劃分為合適數量的子區域，找出移動sink節點的轉向點，在轉向點中選擇最優的，依次連接所有最優轉向點，最后得到移動sink節點的最佳路徑。具體算法如下。

步驟1：以中軸線將傳感器網絡區域一分為二，分為左右兩個子區域，并進一步劃分多個子區域，選擇候選轉向點。

輸入：整個區域簇首的剩余能量：R1.R2...Rm...Rn

左子區域內各個簇首的剩余能量：R1.R2...Rm

右子區域內各個簇首的剩余能量：Rm...Rn

整個區域內簇首節點數量：n

左區域內簇首的數量：m

右區域內簇首的數量：n-m

過程：

1：forR1 toRm

EDL=(R1+…+Rm)/m∥計算左子區域的能量密度

2：forRmtoRn

EDR=(Rm+…+Rn)/(n-m) ∥計算右子區域的能量密度

3：forR1 toRn

T=(R1+…+Rn)/n∥計算整個區域的能量密度

4：ifEDL

利用第3提到的子區域劃分方法進行區域劃分

5：else

該區域不再進行子區域劃分

6：end

輸出：劃分區域線上的點為候選轉向點

步驟2：選擇最優轉向點。

輸入：候選點A(X1,Y1),B(X2,Y2)…(Xn,Yn)，其中X1=X2= …=Xn,Y1=k1Δy,Y2=k2Δy…Yn=knΔy(k為常數,Δy為固定網格格數)

各個簇首到sink節點的跳數h1,h2…hn

過程：

1：forh1 tohn∥選擇A作為轉向點，遍歷所有簇首節點到sink節點的跳數

RA=(h1+h2+…hn)/n∥ 選擇A作為轉向點傳輸數據所需要的平均跳數

2：forh1 tohn∥選擇B作為轉向點，更新步驟1中簇首節點到sink節點的跳數

RB=(h1+h2+…hn)/n∥ 選擇B作為轉向點傳輸數據所需要的平均跳數

3：ifRA

takeA intoS[i][j] ∥S為最優轉向點的集合

4：else

take B intoS[i][j]

5：循環操作到所有轉向點比較完成

6：end

輸出：最優轉向點的集合S

步驟3：sink節點以勻速依次經過最優轉向點，該路徑就是sink節點的移動路徑。

圖5～圖8分別為移動sink節點在不同迭代操作次數下，移動路徑的改變。

圖5 初始狀態Fig.5 Initial state

圖6 第1次迭代Fig.6 First iteration

圖7 第2次迭代Fig.7 Second iteration

圖8 第3次迭代Fig.8 Third iteration

從圖中可以看出，初始狀態有些簇首需要將數據包轉發4～6次，隨著不同時期下路徑的改變，傳感器節點需要轉發的數據包越來越少，迭代3次后傳感器節點最多只要轉發2次，能量消耗也趨于平衡，生命周期也會大幅度延長。

6 仿真實驗

采用Matlab進行仿真，在實驗中，假設在監測區域為300 m*400 m的范圍，300個傳感器節點隨機分布，傳感器節點的傳輸半徑為40 m，普通節點的起始能量為1 J，節點發送單位字節數據的能耗為100 nJ，接收單位字節數據的能耗為20 nJ，sink節點沿著規劃路徑勻速運動，每個周期產生的平均數據為1000 B，規定從區域左邊邊界移動到右邊邊界為一個周期，完成一個周期的數據收集為一輪。仿真實驗的約束條件為：① 傳感器節點靜止不動，移動sink節點沒有能量約束；② 在一個周期內，無數據傳輸的節點不參與路徑規劃。

為了驗證本文提出路徑規劃算法的有效性，將其與文獻[5]中提出的sink節點固定轉向移動算法進行對比。固定轉向移動算法在轉向點的選擇上不考慮網絡的剩余能量，在sink節點移動之前已經確定了轉向點，固定在監測區域的水平邊界上，sink節點在轉向點之間直接進行移動。仿真實驗將從每輪存活節點百分比、節點的平均剩余能量、網絡平均跳數三個方面進行判斷，比較兩種算法的網絡生命周期。

圖9是在收集數據的不同輪數下，傳感器節點存活的百分比。從圖中可以看出，與文獻[5]中的sink節點固定轉向算法相比，sink節點固定轉向算法在2 500輪時就出現了節點死亡，本文算法在3 500輪后才出現節點死亡，到6 000輪時，存活節點還剩60%，而sink節點固定轉向算法只存活了一半，這說明了本文提出的算法能有效延長網絡的生命周期。

圖9 每輪存活節點百分比Fig.9 Percentage of surviving nodes in each round

圖10為傳感器網絡中兩種算法節點平均剩余能量的曲線對比圖。由圖10可知，本文設計的移動sink節點路徑規劃算法與sink節點固定轉向算法在工作的前25 s，能量消耗的差距并不大，但是隨著時間的進行，sink節點固定轉向算法的能耗問題就顯現出來，能量消耗明顯加快，由此可以判斷，本文提出的算法很大程度上解決了能耗問題，延長了網絡生命周期。

圖10 節點平均剩余能量Fig.10 Average residual energy of nodes

圖11為網絡平均跳數對比圖。對于sink節點固定轉向算法，在前50 s沒有傳感器節點死亡，網絡平均跳數保持平衡，本文算法平均跳數略有下降，隨著網絡運行時間的增加，兩種算法下傳感器網絡的平均跳數都出現明顯下降。但是，本文算法對應的網絡平均跳數始終低于sink節點固定轉向算法，有效降低了數據丟包的概率與傳感器節點能耗，從而達到延長網絡生命周期的目的。

圖11 網絡平均跳數Fig.11 Network average hops

7 結束語

針對無線傳感器網絡中的能量空洞問題，提出了移動sink節點路徑規劃的算法，該算法使用二分法劃分區域，基于傳感器節點的能量密度選擇轉向點的位置。仿真結果表明，本文所提出的方案可以減少能量空洞問題，從而延長網絡壽命。與現有算法比較后，顯示出它在延長網絡生命周期方面的優越性。下一步工作的重點是分析不同數量移動sink節點的路徑規劃以及它們之間如何協調收集數據問題。