基于移動Sink的無線傳感器網(wǎng)絡(luò)能量高效的駐留點(diǎn)路由算法

鮑毅，王占剛

（1安徽工程大學(xué) 電氣工程學(xué)院，蕪湖 241000；2湖北科技職業(yè)學(xué)院 軟件工程學(xué)院，武漢 430000）

無線傳感器網(wǎng)絡(luò)能夠部署在人類無法到達(dá)的地方，如野生森林、軍事環(huán)境、戰(zhàn)場等惡劣環(huán)境中進(jìn)行監(jiān)測，并廣泛應(yīng)用于智慧城市和社區(qū)、醫(yī)療系統(tǒng)和醫(yī)療保健、智能農(nóng)業(yè)等場景.無線傳感器網(wǎng)絡(luò)具有自組織部署、自組織、能量約束、動態(tài)網(wǎng)絡(luò)拓?fù)?、無人值守操作等特性，使得傳感數(shù)據(jù)的處理、通信和管理成為一項(xiàng)具有挑戰(zhàn)性的任務(wù)［1］.由于傳感網(wǎng)中部署的節(jié)點(diǎn)能量受限，傳感器節(jié)點(diǎn)的電池電量更續(xù)成為一項(xiàng)艱巨的任務(wù).另外，在多跳機(jī)制下，部分節(jié)點(diǎn)由于承載數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，導(dǎo)致距離Sink較近的節(jié)點(diǎn)需要更多的能量的開銷，導(dǎo)致能量空洞或熱點(diǎn)問題.這勢必影響整個網(wǎng)絡(luò)的正常工作，造成網(wǎng)絡(luò)壽命和服務(wù)質(zhì)量的下降［2］.

移動Sink或移動數(shù)據(jù)采集器（MDC）的概念被提出，以緩解能量空洞問題并延長網(wǎng)絡(luò)壽命.在基于移動Sink的WSN中，最基本的任務(wù)是確定移動Sink如何從網(wǎng)絡(luò)中獲取數(shù)據(jù).其中，一種策略是訪問每個傳感器節(jié)點(diǎn)，通過單跳通信直接獲取數(shù)據(jù).從根本上講，這是一個旅行商問題（TSP），其目的是確定可以訪問所有傳感器節(jié)點(diǎn)的最短路徑［3］.然而，對于大型網(wǎng)絡(luò)，生成的路徑可能無法滿足特定應(yīng)用程序的延遲方面的限制.因此，需要在延遲約束下實(shí)現(xiàn)從傳感器節(jié)點(diǎn)到移動Sink的多跳數(shù)據(jù)轉(zhuǎn)發(fā).另外，Sink的移動使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化，傳感器節(jié)點(diǎn)有必要知道在哪里轉(zhuǎn)發(fā)最終可以傳送到移動Sink的數(shù)據(jù).

1 相關(guān)工作

在部署了移動Sink的無線傳感網(wǎng)中，如何提高數(shù)據(jù)收集效率、延長網(wǎng)絡(luò)生命周期，以及降低節(jié)點(diǎn)的部署、運(yùn)行成本是研究中需要考慮的幾個重要問題.大致而言，所有這些數(shù)據(jù)采集方法大致包括以下幾個階段：駐留點(diǎn)的選擇、區(qū)域范圍內(nèi)節(jié)點(diǎn)至駐留點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)樹的形成以及用于數(shù)據(jù)采集的移動Sink遍歷軌跡的優(yōu)化.

KASWAN等 人［4］提 出 了 定 期 交 會 數(shù) 據(jù) 采 集（PRDC）和延遲界約化k均值的方法，將網(wǎng)絡(luò)劃分為若干個簇且使得所有簇頭節(jié)點(diǎn)至所有數(shù)據(jù)匯聚節(jié)點(diǎn)的跳距最小來優(yōu)化數(shù)據(jù)采集過程中的能量消耗.KUMAR等人［5］提出了范圍約束聚類數(shù)據(jù)采集方法（RCCDAM），只考慮簇頭節(jié)點(diǎn)和駐留點(diǎn)之間的距離，而在選擇信道時不考慮傳感器節(jié)點(diǎn)的能量因素.ALNUNIMI等人［6］提出了基于ferry的數(shù)據(jù)采集方法（FBDAM），考慮距離和能量因素來選擇信道.為了找到在避障情況下的最短路徑，NANNAPANENIA等人［7］提出了一種啟發(fā)式旅游規(guī)劃算法來實(shí)現(xiàn)對移動Sink的有效調(diào)度.為了提高網(wǎng)絡(luò)效率和Sink的利用率，LU等人［8］提出了一種基于簇樹的節(jié)能路由協(xié)議（CTEER），通過規(guī)劃接收器的移動路徑來創(chuàng)建交叉通信區(qū)域，在區(qū)域內(nèi)構(gòu)建以移動接收器為中心的交叉路由樹.JAIN等人［9］提出了一種基于非均勻分層分簇和動態(tài)路由調(diào)整方案，通過簇頭的交替選擇來分配數(shù)據(jù)收集過程中的負(fù)載.SALARIAN等人［10］設(shè)計了高效節(jié)能的移動路徑選擇策略，通過加權(quán)駐留規(guī)劃（WRP）的啟發(fā)式算法來解決移動Sink對駐留點(diǎn)的遍歷問題，提高數(shù)據(jù)采集效率.

上述基于移動Sink的數(shù)據(jù)收集方案的提出，對于提高數(shù)據(jù)收集效率和均衡化網(wǎng)絡(luò)中所有節(jié)點(diǎn)的能量消耗起到了積極作用.但是，Sink的移動性會導(dǎo)致數(shù)據(jù)收集產(chǎn)生更多的數(shù)據(jù)延遲，需要在數(shù)據(jù)的可靠傳輸和Sink節(jié)點(diǎn)移動路徑規(guī)劃等方面綜合考慮，以提高網(wǎng)絡(luò)的可用性.

2 本文方法

2.1 系統(tǒng)模型

假設(shè)n個傳感器隨機(jī)部署在D×D的正方形區(qū)域，基于移動Sink的傳感器網(wǎng)絡(luò)用M=(S，C，Ψ)來定義，其中，S表示傳感器節(jié)點(diǎn)集合，且|S|=n；C為駐留點(diǎn)集合，且|C|=m；Ψ表示整個系統(tǒng)的感知區(qū)域.移動Sink在駐留點(diǎn)之間移動并收集傳感器節(jié)點(diǎn)的數(shù)據(jù)，移動Sink具有無限的能量以支持其在整個網(wǎng)絡(luò)生命周期內(nèi)運(yùn)行.其他假設(shè)條件包括：Sink知道傳感器節(jié)點(diǎn)的所有信息，例如位置，可用能量等；Sink節(jié)點(diǎn)有足夠的空間來存儲收集的數(shù)據(jù)；Sink節(jié)點(diǎn)的移動軌跡上沒有障礙物.

移動Sink在駐留點(diǎn)停留的時間按輪次來進(jìn)行計量，每一輪的最小時間間隔用Δt來表示.整個傳感器網(wǎng)絡(luò)的生命周期被定義為從網(wǎng)絡(luò)初始化到第一個節(jié)點(diǎn)耗盡電量，用L來表示，則：

其中，Tc為移動Sink在第c個駐留點(diǎn)停留的時間.

為了表示第t輪移動Sink的駐留點(diǎn)位置，用變量表示：

根據(jù)上述定義，移動Sink在第c個駐留點(diǎn)停留的時間能表示為：

傳感器感知物理環(huán)境并將數(shù)據(jù)包傳輸?shù)揭苿覵ink.每個傳感器具有相同的有限初始能量Ei，每個傳感器的傳感數(shù)據(jù)速率為λ.移動Sink和傳感器節(jié)點(diǎn)具有最大的通信半徑d0.對于傳感器節(jié)點(diǎn)i來說，當(dāng)與節(jié)點(diǎn)j的距離dis(i，j)≤d0時，節(jié)點(diǎn)之間采用單跳進(jìn)行通信；否則，采用多跳方式將采集的數(shù)據(jù)交給匯聚節(jié)點(diǎn).

考慮到所有節(jié)點(diǎn)采集的數(shù)據(jù)通過一棵多跳轉(zhuǎn)發(fā)樹H轉(zhuǎn)發(fā)至Sink節(jié)點(diǎn)，假設(shè)在第t輪，節(jié)點(diǎn)i發(fā)送的數(shù)據(jù)為收到的數(shù)據(jù)為根據(jù)流增強(qiáng)算法［11］，的值可以表示為：

其中，Et為節(jié)點(diǎn)剩余能量的向量，且表示第t輪所有節(jié)點(diǎn)的分布.

當(dāng)移動Sink結(jié)束當(dāng)前駐留點(diǎn)的停留而移動至下一駐留點(diǎn)，多跳轉(zhuǎn)發(fā)樹H將重新生成.對于多跳轉(zhuǎn)發(fā)樹H中的葉子節(jié)點(diǎn)來說，它們只產(chǎn)生數(shù)據(jù)并不需要承擔(dān)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)，將其發(fā)送和接收的數(shù)據(jù)分別記為

對于任意傳感器節(jié)點(diǎn)來說，能量消耗分為數(shù)據(jù)發(fā)送和數(shù)據(jù)接收兩部分，接收和發(fā)送B比特數(shù)據(jù)包的能量消耗為［12］：

對于任意節(jié)點(diǎn)i，在整個網(wǎng)絡(luò)生命周期其能量消耗能被表示為：

因此，網(wǎng)絡(luò)生命周期最大化問題能被描述為：

其中，約束條件（8）表示移動Sink在每個候選駐留點(diǎn)允許的停留時間；約束條件（9）表示網(wǎng)絡(luò)中僅包含一個移動Sink；約束條件（10）表示任何節(jié)點(diǎn)在每輪的發(fā)送數(shù)據(jù)一定是包含接收其他節(jié)點(diǎn)的數(shù)據(jù)和自身采集數(shù)據(jù)之和，Δt表示發(fā)送數(shù)據(jù)兩輪之間的時間差；約束條件（11）表示在網(wǎng)絡(luò)生命周期內(nèi)節(jié)點(diǎn)還存在剩余能量.

2.2 優(yōu)化算法

蟻群算法（ACO）是一種受自然界真實(shí)螞蟻行為啟發(fā)的仿生技術(shù)［13］.通過在圖中尋找最優(yōu)路徑，它在求解組合優(yōu)化問題和旅行商問題的近似最優(yōu)解方面表現(xiàn)出了足夠好的性能［14］.蟻群算法本質(zhì)上是一種正反饋機(jī)制，它在求解過程中具有隨機(jī)性、適應(yīng)性和分布性等特點(diǎn)［15］.它適用于并行計算和精確解.移動Sink的駐留點(diǎn)的選擇和路徑確定提供了事件驅(qū)動無線傳感器網(wǎng)絡(luò)的最佳性能，本文采用蟻群優(yōu)化算法來對上述網(wǎng)絡(luò)生命周期最大化問題進(jìn)行求解.使用蟻群優(yōu)化算法通過迭代更新螞蟻的信息素值來生成解，信息素的數(shù)量計算為：

其中，其中Lk是第k個螞蟻的總軌跡距離，μ是一個常數(shù)值.

對于節(jié)點(diǎn)i到j(luò)之間由螞蟻k更新的信息素值為：

其中，ρ表示信息素的衰減，其取值范圍為（0，1）之間.(1-ρ)是單位時間內(nèi)信息素的蒸發(fā)率.K表示算法中使用的螞蟻總數(shù).τij是所有螞蟻在節(jié)點(diǎn)i到j(luò)之間沉積的信息素值.

從節(jié)點(diǎn)i中選擇另一個節(jié)點(diǎn)j時，算法考慮節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)載，用wj=Rj/Qj來表示.ηij表示強(qiáng)調(diào)啟發(fā)式數(shù)據(jù)的重要性，并能從當(dāng)前的網(wǎng)絡(luò)情況中獲得最佳的駐留點(diǎn)集，用ηij=1/dij來表示.則概率函數(shù)被定義為：

其中，Nil表示未被螞蟻k訪問過的節(jié)點(diǎn)i的鄰居節(jié)點(diǎn).參數(shù)α，β和γ分別用來控制信息素值、啟發(fā)式數(shù)據(jù)和數(shù)據(jù)轉(zhuǎn)發(fā)負(fù)載的相對重要性.

從ψ(Sp)中選擇一個可行解是由隨機(jī)構(gòu)造引導(dǎo)的，從表達(dá)式可以看到，構(gòu)造的結(jié)果受與ψ(Sp)的每個值相關(guān)的信息素的影響.節(jié)點(diǎn)l表示螞蟻k尚未訪問的節(jié)點(diǎn).每個螞蟻選擇下一個節(jié)點(diǎn)作為主流點(diǎn)，概率函數(shù)為其返回最高值，并更新當(dāng)前節(jié)點(diǎn)和選定駐留點(diǎn)之間的信息素.

一旦選擇了合適駐留點(diǎn)，算法需要計算移動Sink的遍歷路徑長度.構(gòu)建移動Sink路徑的概率函數(shù)為：

如果超過現(xiàn)有的解的遍歷路徑長度，將從集合C中刪除駐留點(diǎn)，并選擇另一個概率最高的節(jié)點(diǎn)重復(fù)上述過程.

3 實(shí)驗(yàn)結(jié)果與分析

通過MatLab進(jìn)行了仿真實(shí)驗(yàn)，將本文提出的算法與NHCDRA［9］和EMPS［10］等典型算法進(jìn)行了比較.在傳感器網(wǎng)絡(luò)中，隨機(jī)采用隨機(jī)部署的方式，區(qū)域大小為400 m×400 m矩形平面，傳感器節(jié)點(diǎn)在其正常工作狀態(tài)下以20 bit/s的速度產(chǎn)生數(shù)據(jù).傳感器節(jié)點(diǎn)初始能量為5 J，其發(fā)射機(jī)和接收機(jī)參數(shù)設(shè)置為：εtr=40 nJ/bit，εmp=100 pJ/bit/m2，εrec=50 nJ/bit.蟻群優(yōu)化算法中的調(diào)節(jié)參數(shù)α，β和γ分別設(shè)置為0.2，0.4和0.4，μ=100.為了驗(yàn)證算法的性能，選取了丟包數(shù)、網(wǎng)絡(luò)生命周期、數(shù)據(jù)包交付率、端到端時延等指標(biāo)進(jìn)行了比較分析.

首先，對不同輪次下的丟包數(shù)進(jìn)行對比.從圖1可以看出，在前200輪，三種算法的丟包術(shù)相差并不明顯.隨著網(wǎng)絡(luò)的運(yùn)行，丟包數(shù)逐漸增大.整體上EMPS算法具有較高的丟包數(shù).其主要原因該算法在轉(zhuǎn)發(fā)過程中沒有充分考慮時延或最大跳數(shù)約束條件，離Sink節(jié)點(diǎn)最近的節(jié)點(diǎn)作為數(shù)據(jù)轉(zhuǎn)發(fā)的根節(jié)點(diǎn)，容易因負(fù)載過大導(dǎo)致數(shù)據(jù)緩沖區(qū)溢出.本文提出的算法在駐留點(diǎn)的優(yōu)化選擇中充分考慮了節(jié)點(diǎn)的數(shù)據(jù)負(fù)載因素，使得丟包數(shù)相對較低.

圖1 丟包數(shù)的比較Fig.1 Comparison of packet loss

圖2為不同節(jié)點(diǎn)數(shù)下的網(wǎng)絡(luò)生命周期的比較.本文將網(wǎng)絡(luò)生存周期定義為無線傳感器網(wǎng)絡(luò)從網(wǎng)絡(luò)初始化到第一個節(jié)點(diǎn)耗盡電量的持續(xù)時間.隨著節(jié)點(diǎn)數(shù)的增加，網(wǎng)絡(luò)生命周期呈上升趨勢，節(jié)點(diǎn)之間可以通過多跳方式轉(zhuǎn)發(fā)數(shù)據(jù)，能夠有效降低單跳遠(yuǎn)距離傳輸造成的能量過量消耗.EMPS算法的網(wǎng)絡(luò)生命周期相比較而言更低，這是因?yàn)椋S著節(jié)點(diǎn)數(shù)量的增加數(shù)據(jù)轉(zhuǎn)發(fā)跳數(shù)也顯著增加，這將導(dǎo)致駐留點(diǎn)附近的節(jié)點(diǎn)具有更高的能量消耗并過早死亡.當(dāng)傳感器節(jié)點(diǎn)高于200時，我們提出的算法的生存期明顯優(yōu)于其他算法.但隨著網(wǎng)絡(luò)規(guī)模的增加，本文提出的算法在網(wǎng)絡(luò)生命周期上的表現(xiàn)逐漸突出，具有更好的節(jié)點(diǎn)存活時間.這說明算法在執(zhí)行時，移動策略中的駐留點(diǎn)的選擇更合理，可以平衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗.

圖2 網(wǎng)絡(luò)生命周期的比較Fig.2 Comparison of network lifetime

圖3為不同節(jié)點(diǎn)數(shù)量時數(shù)據(jù)交付率的比較.隨著網(wǎng)絡(luò)規(guī)模的增加，本文提出的算法具有更明顯的優(yōu)勢，始終保持在90%以上.當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)密集分布時，需要轉(zhuǎn)發(fā)的數(shù)據(jù)量會顯著增大，有效的數(shù)據(jù)收集方案應(yīng)該能夠通過合理調(diào)整移動Sink的移動軌跡和對駐留點(diǎn)的遍歷，及時回收各感知節(jié)點(diǎn)采集的數(shù)據(jù).這樣不會導(dǎo)致因溢出或時間延遲約束導(dǎo)致丟包，從而影響數(shù)據(jù)的及時交付.另外，駐留點(diǎn)的優(yōu)化選擇對于提高數(shù)據(jù)交付率也起到重要作用.

圖3 數(shù)據(jù)交付率的比較Fig.3 Comparison of data delivery rate

圖4顯示不同節(jié)點(diǎn)數(shù)條件下端到端時延的比較.更多的傳感器節(jié)點(diǎn)意味著來自源節(jié)點(diǎn)的更多數(shù)據(jù)需要轉(zhuǎn)發(fā)到駐留點(diǎn)，并且由于多跳傳輸，數(shù)據(jù)收集必須等待很長時間.移動Sink節(jié)點(diǎn)停留在駐留點(diǎn)附近進(jìn)行數(shù)據(jù)收集，也會增加了數(shù)據(jù)傳輸?shù)难舆t.在實(shí)驗(yàn)結(jié)果可以看到，本文提出的算法相比NHCDRA算法和EMPS算法都具有更好的性能.隨著傳感器節(jié)點(diǎn)數(shù)量的增加，在我們提出的算法中，駐留點(diǎn)選擇策略和移動Sink的路徑的優(yōu)化調(diào)整可以找到更優(yōu)的解決方案來實(shí)現(xiàn)數(shù)據(jù)的及時收集處理，有效降低了數(shù)據(jù)傳輸延遲.

圖4 端到端時延的比較Fig.4 Comparison of end-to-end delay

4 結(jié)語

為了提高基于移動Sink的無線傳感網(wǎng)的數(shù)據(jù)收集效率，本文提出了一種基于移動Sink的無線傳感器網(wǎng)絡(luò)能量高效的駐留點(diǎn)路由算法.首先，對數(shù)據(jù)采集過程中的網(wǎng)絡(luò)生命周期最大化問題進(jìn)行建模；其次，提出了基于蟻群優(yōu)化的算法來求解最優(yōu)的駐留點(diǎn)集合和移動Sink遍歷路徑.為了驗(yàn)證算法的性能，選取了丟包數(shù)、網(wǎng)絡(luò)生命周期、數(shù)據(jù)包交付率、端到端時延等指標(biāo)，將本文提出的算法與NHCDRA和EMP等典型算法進(jìn)行了比較.實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠有效延長網(wǎng)絡(luò)的生命周期、提高交付率和減少端到端時延.