移動協助傳感器網絡中Sink的路徑優化策略

張希偉，沈琳，蔣益峰

（1.河海大學 計算機與信息學院，江蘇 南京 210098; 2.江蘇理工學院 電氣信息工程學院，江蘇 常州 213001）

1 引言

無線傳感器網絡（WSN, wireless sensor network）中存在能量空洞（energy hole）、冗余覆蓋（overlap）和熱點（hot spot）等問題[1～3]。盡管可以在基站周圍部署更多的節點輪流工作（即離基站近的區域節點密度較大）[3～6]，但無疑會增加網絡的成本和計算代價。

在無線傳感器網絡中引入了移動性，即在Sink節點上配備移動裝置可以有效地解決上述問題。通過基站的移動，使負責向 Sink轉發的節點經常變化，將網絡負載分擔到不同的節點上。利用移動節點進行數據收集的一個典型是 Shah等提出的數據騾子（data mule）的模式[3]。近年來在煤礦、森林等傳感器網絡應用中也出現了利用移動節點來進行數據收集的例子[7,8]。

移動性帶來的一個問題是增加了數據的延時。由于移動Sink的運行速度有限（一般為1～2m/s），遠遠小于無線網絡傳輸的速度，因此，在選擇移動Sink傳輸和無線傳輸中存在一個折中[9]。例如在圖1中，移動Sink綜合考慮了能量和延時之間的關系，并不是訪問所有的靜態節點，而是只訪問數據匯聚點（CP, collection point）。靜態節點事先將數據發送到匯聚點，當移動Sink到來時再進行轉發。文獻[10]提出了一種基于旅行商問題的匯聚點選擇算法，總是選擇那些能夠節約最大能量的位置作為匯聚點。文獻[11]在此基礎上提出了基于虛擬點優先級的移動Sink路徑優化方法。同樣地，當傳感器通信范圍內存在多個移動 Sink時，需選擇一個合適的 Sink進行數據傳輸[12]。

圖1 一個典型的利用移動Sink收集數據的WSN應用

本文主要研究移動Sink的路徑優化策略。通過分析移動路徑和網絡能耗之間的制約關系，建立優化模型。根據數據采集的不確定性，提出了一種基于訪問概率的匯聚節點選擇算法。移動Sink按照一定的概率訪問匯聚節點，在滿足數據收集效率的前提下，該方法可以有效地縮短移動軌跡。

2 網絡模型

本文的主要目標是:針對Sink移動軌跡可控的無線傳感器網絡，綜合考慮數據延時和能耗兩項技術指標，提出了一種優化的Sink路徑選擇機制，提高了系統能耗利用率，具體包含以下2個優化目標:

1) 移動距離在滿足系統要求的情況下最短化；2) 在目標1) 的基礎上，系統整體能耗最小化。首先，定義一個由N個傳感器節點和一個Sink節點組成的無線傳感器網絡，網絡是全連通的。節點間采用多跳方式通信；節點具有相同的初始能量，且能量有限，但Sink的能量不受限制；每個節點可以通過 GPS或其他定位算法知道各自的位置信息；Sink節點具有移動性，并且移動方式可控，其以恒定的速度 Vm移動。

采用樹形結構來表示網絡的拓撲。設移動Sink從節點B出發，并最終回到節點B。令 T( V, E)為以B為根節點的一顆樹，其中，V為所有傳感器節點，E為這些節點間的連接線。所有源節點的集合S = {Si}? V ；所有CP節點的集合表示為 C ={ p0,…, pnp-1}，pi表示第i個CP節點。當然一個CP節點也是一個源傳感器節點。此時，將以每個 pi為根節點形成子樹，子樹中的每個節點將數據傳輸給 pi并等待Sink節點來收集數據。用 np和 nnumber來表示CP節點的數量和成員節點的數量。即

2.1 移動路徑最短化

利用移動Sink進行數據收集時，數據延時等于數據產生到移動Sink收集該數據的時間差。可以看出，最大數據延時是移動Sink訪問所有CP節點所需要的時間。數據延時要求越小，Sink的移動路徑越短。

假設在Sink的移動路徑上共有 np個CP節點，每一對 CP節點間的直線距離可以表示為 [p0,p1],[p1,p2],…, [pnp-2,pnp-1]，這里可以用{z0,z1,… , znp-2}來表示。對于用戶給定的最大數據延時 Dr，應該滿足

2.2 系統能耗最小化

本文采用文獻[13]中的簡化能耗模型，節點總能耗p由接收和發送的數據總量kr和kt來決定。e為常數，表示發送和接收單位比特數據的能耗。如式(3)所示。

當 Sink移動到終點并返回到起點時，稱其完成一“輪”移動。在每一輪中，任意節點i接收數據量和發送數據量之間的關系為=+q，q表示節點i在單輪中所采集到的數據總量。故有下式

其中，hi表示節點i到其所屬CP節點的最短跳數。如果節點i為CP，則hi為0。根據式（4）可以將單輪系統總能耗ptotal表述為最小跳數和的形式。

其中，pi為任意節點i的單輪總能耗。根據式（5）可知，系統總能耗最小化問題等價于全網節點距離其所屬CP節點跳數和的最小化問題。

2.3 最小能耗最短路徑問題

根據上述分析，可以發現當選擇較長的 Sink節點移動路徑時，移動Sink可以訪問更多的CP點，使每個以CP點為根節點的子樹規模較小，從而節約網絡的能耗。但由于移動路徑較長，數據傳輸的延時會增加。相反，要求較小的數據延時，網絡的能耗也會變大。因此，在網絡能耗與移動路徑的長度上存在一個折中，稱為最小能耗最短路徑問題（MEMD, min-energy min-distance）。Sink移動路徑的優化問題可描述為

目標函數

滿足約束條件

3 匯聚節點的選擇

3.1 問題定義

定義1 （MEMD問題）給定樹結構 T( V, E)，由根節點（B）和一組傳感器節點 S =? V 組成。尋找一條路徑U，從B出發，并訪問所有CP節點后回到B。使得路徑U的長度不超過規定延時內的移動距離，即 Drvm，同時滿足

定理1 MEMD是NP-hard問題。

證明 可以將 MEMD問題規約為一個旅行商問題（TSP, traveling salesman problem）。MEMD問題的一個特例是尋找一條移動路徑使得網絡的傳輸能耗為 0。在這種情況下，所有的源節點都必須為CP節點，即移動Sink訪問所有傳感器節點。此時，可以規約為一種旅行商問題，在規定的時間內訪問一組城市并使路徑最短。

證畢。

3.2 基于效用的貪心算法

這里給出一種基于效用的貪心算法（utilitybased greedy heuristic）來選擇CP節點，稱為CPUG算法。該算法總是選擇那些能夠節約最大網絡能量的節點作為CP，并且所有CP節點間的距離和不超過Drvm。因此效用（utility）可定義為該CP節點節約的網絡能量與增加的移動距離之間的比值。

需要注意的是，CP節點的功效會隨著移動路徑長度的變化而變化。如在圖2所示，如果移動Sink的路徑只能覆蓋B和其余一個CP點，即p1、p2或p3，那么應該選擇p1，因為有5個源節點在它的子樹中，其節約的能量最多。如果移動Sink的路徑可以覆蓋 B、p2和 p3，所有的數據將在 p2和 p3點收集，p1的效用將為0。因此，CPUG算法必須在Sink的移動過程中動態地更新每一個節點的效用，通過多次迭代執行獲得最佳的CP集合。

圖2 CPUG算法執行示例

圖3給出了CPUG算法的偽代碼。初始情況下CP隊列中只包含根節點B，通過計算節點的效用不斷地加入CP節點。CPUG算法利用TSP()I過程來計算訪問集合I中所有節點的最短路徑。TSP()I可以采用基于幾何結構的旅行商問題求解算法。每次迭代時，首先確定所有的CP候選節點（第2）步）。如果一個節點的加入使得移動Sink以更短的路徑訪問所有的CP，同時這些CP節點的子樹中源節點的跳數和減少，那么該節點可以是一個候選節點。

候選節點x的效用定義為

u(x)等于源節點傳輸數據時跳數的減少和Sink移動距離的增加之間的比值。CPUG算法選擇具有最大效用值的CP候選節點加入到CP隊列中（3）和4）），同時將CP隊列中效用值變為0的節點清除出去（5））。如果所有的源節點都已在Q中，則結束，否則開始新一輪的迭代。

圖3 CPUG—— 一種基于效用的CP節點選擇算法

以圖2中的例子來說明CPUG的執行過程。圖2給出了CP隊列，需要3次迭代完成。在第1次迭代過程中選擇 s1作為CP節點。第2次迭代中，在所有節點中 s2具有最大的效用值。盡管 s2和 s3在路徑的距離增加上是相同的，但 s2節約的能量比 s3多，因為 s3的子樹中只有一個源節點，而 s2的子樹中有2個。在第3次迭代中 s3也被選擇CP節點，同時由于 s1的效用值變為0，將 s1清除出CP節點隊列。

4 概率路徑選擇算法

在 WSN應用中，sensor節點按照一定的duty-cycle進行工作。數據的產生具有時間性。當移動Sink對某個CP節點收集數據時，如果該CP節點沒有數據上傳，那將造成訪問該節點的時間浪費。因此，移動Sink對CP節點可以按照某種概率進行訪問，通過概率的變化和移動Sink的數量來保證數據收集的完整性。

4.1 數據延時限制

通常情況下，用戶對數據采集的延時會提出要求，例如最大數據延時為 Dr，而系統必須保證數據延時值不大于Dr。設移動Sink訪問所有CP節點一次為一個周期，所需要的時間為τperiod。為了實現時間限制，首先給出訪問率的定義。

定義2 訪問率:一個CP節點在一個周期內被移動Sink至少訪問一次的概率定義為該CP的訪問率γp。

設某CP節點p的數據傳輸延時為Dp，則Dp和γp之間存在如下關系。

定理2 Dp的累積分布函數（cdf）如下

證明 Dp的cdf函數表示為

這表示在時間長度為d的范圍內，沒有移動Sink訪問該節點。共經歷了k個τperiod周期以及剩余的d-kτperiod時間。τperiod內未訪問該節點的概率為1-γp，d-kτperiod時間未訪問該節點的概率為1-γp。

證畢。

根據這個性質，可以得到傳輸延時的上限。定義CP節點的最小訪問率為γ0，其數據傳輸延時D0應該滿足

顯然，如果CP節點的訪問率大于該最小訪問率，那么數據傳輸延時應更小，即

結合式（11）和式（12），可以得到

因此，當確保對每一個CP節點的訪問率均大于γ0，那么可以保證所有數據的傳輸延時都低于用戶要求的最大延時Dr。由于對Dr要求的不同，因此γ0也會隨之變化。γ0情況下D0的期望如式(14)所示。

定理3 當CP節點的訪問率為γ0時，D0的期望為

因此，可以得到D0的期望為

證畢。

上式中可以看出D0的期望值是γ0的單調遞減函數。

4.2 基于訪問概率的最短路徑選擇

本文給出了一種基于CP節點訪問概率的路徑選擇優化算法。每個CP節點在系統初始化時分配一個訪問概率，該訪問概率由最大數據延時、Sink移動路徑長度和移動Sink的數量等因素決定，以保證在最大數據延時內獲得最長的路徑，相應地可以選擇更多的CP節點來節約網絡能量。

圖4給出了一個基于概率訪問的簡單例子。圖4(a)中，移動Sink需要訪問5個CP節點。對于每個 CP節點 pi（pi∈C），其訪問概率設為βi，而忽略該節點的概率為1-βi。在Sink的移動過程中，要實現平滑的移動路線是很困難的，采用圖4(b)中的方法，用節點間的歐式距離作為移動長度。每個連線上的權值即為該節點的訪問概率。

圖4 概率路徑選擇問題

結合CP節點的訪問概率和歐式距離來處理最短路徑選擇算法。對于CP隊列中每一個CP節點pi，其訪問概率為βi，設前一個CP節點到pi節點的歐式距離為 wi，當前系統中共使用了m個移動Sink來收集數據。那么，可以構造整型線性規劃（IPL）模型為

滿足約束條件

式（18）確保了CP節點的訪問率不低于最大延時需求下的訪問率。

本文采用了單一訪問概率方法（identical probability schema），在多個移動Sink訪問某CP時采用單一的概率，并且在系統的運行過程中不變?？梢郧蟪鯟P節點的傳輸延時期望與訪問概率之間的關系。

定理 4 當對 CP節點采用單一訪問概率方法時，其數據傳輸延時的期望值為

證明 設M為該 CP節點的數據被移動 Sink收集前經過的訪問輪數，那么M的概率分布函數為

其中，θ為單輪內CP節點的訪問概率，則

將θ代入式（20）中，得

如果數據在第i輪被收集，那么將增加傳輸延時 （i- 1）τperiod，因此，計算條件M下的期望值為

證畢。

5 性能分析

5.1 實驗設置

本節采用 NS2模擬器和真實的移動傳感器實驗床來測試CPUG算法和基于路徑選擇算法在網絡能耗和數據傳輸延時方面的性能。

在 NS2模擬器中主要測試網絡的能耗。設在300m × 300m的區域內隨機部署400個節點，并從中選取100個節點作為CP節點。假設移動Sink從區域的左上角出發。源節點以較低的duty-cycle進行數據采集，并傳輸給CP節點。最大數據延時為5min，那么duty-cycle可在5min以內。

模擬實驗采用 C++語言編寫。通信規范符合CC2420 協議（Mica2 節點）[14]。傳輸帶寬為 40kbit/s，傳輸能耗為4dBm。設數據分組的大小為30byte。為了模擬網絡鏈接的不可靠性，采用USC鏈接層模型[15]。

筆者在室內進行真實的實驗床性能測試。如圖5所示，在15m×15m的房間內劃分成11×11的網格，20個TelosB傳感器節點（配置CC2420通信模塊）隨機放置在這些網格中，每個網格最多放置一個節點。傳感器節點使用TinyOS 2.x操作系統，編程語言為nesC。移動Sink節點使用自主設計的DataTruck移動傳感器節點[16]。該節點具有強計算能力和大存儲容量，采用了32bit ARM處理芯片，配置4個直流電機，最快速度接近2m/s。移動Sink節點如圖5(b)所示。

圖5 實驗環境及移動Sink

5.2 網絡能耗

為了便于觀察網絡的性能，將本文算法和其他2種方法進行比較。一種是未使用移動Sink的情況，即通過多跳協議進行數據傳輸，稱之為NET；另一種是文獻[10]中使用的RP-CP算法，它也是一種利用移動節點和匯聚點進行數據收集的方法。首先，測試網絡能耗與移動節點速度的關系。從圖6中可以看出，隨著移動Sink速度的增加，網絡能耗逐漸減少。這是因為移動Sink可以在規定的時間范圍內收集更多的數據。圖6中的CPUG-PPS方法是指利用CPUG并結合概率路徑選擇算法共同完成數據收集?？梢钥闯鯟PUG-PPS方法收集相同數據量時所需的能量開銷更小，是由于它可以減少更多的時間。如果按照特定的移動路徑，CPUG-PPS方法比NET方法節約40%～70%的能量?？梢钥闯鲆苿铀俣葘W絡能耗有較大的影響，在下面的實驗中固定Sink的移動速度為1.5m/s。

圖6 網絡能耗與移動Sink的速度關系

圖7給出不同節點密度下性能的比較。當節點密度高時，網絡的鏈接性能將會更佳，所以在能耗方面3個算法的性能都優于密度低的情況。同樣地，因為 CPUG-PPS方法忽略了一些沒有數據傳輸的CP節點，節約了更多的網絡能量。

圖7 網絡能耗與傳感器節點的關系

接下來，關注在不同的傳輸延時要求下算法的性能變化。設有8個不同的時延上限，從5min到40min，每個時延間隔5min。從最低的5min開始，每個條件下的源節點數目相同。從圖8中可以看出，隨著時延上限的增加，網絡的能耗卻相應地減少。這是因為在較長的時延上限情況下，算法可以訪問更多的CP節點，減少了源節點到CP節點的跳數，從而節約了能量。

圖8 網絡能耗與延時限制的關系

網絡能耗的一個指標是以CP節點為根節點的子樹中數據傳輸的跳數之和。為了方便起見，通過統計所有子樹的路由長度來表示。路由長度越長，相應地，數據傳輸的跳數也越多。圖9給出了不同算法下網絡中所有子樹的路由長度。可以看出，當規定的時延上限增加時，由于可以選擇更多的CP節點，因此路由的長度減少了。圖10說明了當網絡中傳感器節點增加時，由于每個CP節點的子樹規模也會增加，因此網絡能耗也增加了。

圖9 節點路由樹長度與延時限制的關系

圖10 節點路由樹長度與節點數量的關系

另一組實驗用來測試移動 Sink數目變化時網絡的性能。每個移動Sink輪流訪問CP隊列中的節點，其間隔可根據移動Sink數據的增加相應減少。從圖11可以看出，當移動Sink的數目增加時，由于在相同的規定時間內可以訪問更多的CP節點，所以網絡能耗逐漸減少。

圖11 網絡能耗與移動Sink數量的關系

5.3 概率路徑選擇算法性能

利用移動傳感器實驗床單獨測試概率路徑選擇算法的性能。主要包括2個性能參數，一個是傳輸的時延，一個是路由樹的長度。

為了標識網絡中的每個節點，節點必須具有唯一的地址以及特定的數據傳輸格式。節點地址可以用數字來表示，傳輸格式如圖12所示。

字段的含義如下:

實驗中選擇5個節點作為CP節點，其他作為源節點。移動Sink按照一定的概率訪問這5個CP節點。通常情況下移動Sink以閉環的方式循環訪問這些CP節點，通過測量可知這 5個節點間的最短距離為50m，那么平均延時為25s左右。圖13給出了CP節點的訪問概率與平均傳輸延時之間的關系。從圖13中可以看出，移動Sink根據訪問概率會避免訪問一些 CP節點，減少了移動路徑，因此縮短了傳輸延時。圖14中的曲線說明了當一些 CP節點沒有訪問但其有數據需要傳輸時，在最大延時之前通過多跳的方式發送到基站，這樣增加了網絡能量的開銷，所以隨著訪問概率的降低能耗會增大。

圖13 平均傳輸延時與初始概率的關系

圖14 節點路由樹長度與初始概率的關系

在第2組實驗中，假設20個傳感器節點均為CP節點，當一個移動Sink訪問這些節點的概率均為80%，那么它在2輪中對這些節點的訪問情況如圖15所示?？梢钥闯鲈谶@兩輪中，移動Sink訪問90%以上的節點。因此，可以說當對 CP節點確保相對較高的訪問概率時，絕大部分的節點可以在較少的時間內訪問到。

圖15 單個Sink在2輪移動過程中的路徑選擇情況

6 結束語

本文利用移動Sink來解決WSN中能量空洞等問題。提出了一種最短移動距離最小能耗的路徑優化算法，并證明了該模型是一個NP-hard問題。為了在規定的最大傳輸延時范圍內訪問盡可能多的CP節點，提出了一種基于CP節點訪問概率的路徑選擇算法。通過模擬實驗以及實驗床的真實數據，驗證了本文提出的算法能夠很好地在滿足延時要求的同時節約網絡的能量。

[1]TOLLE G, POLASTRE J, SZEWCZYK R, et al.Amacroscope in the redwoods[A].ACM SenSys[C].San Diego, USA, 2005.51-63.

[2]MAYER K, ELLIS K, TAYLOR K.Cattle health mon-itoring using wireless sensor networks[A].Proc of the ACM IASTED[C].Cambridge, Massachusetts, USA, 2004.375-380.

[3]XUE W, LUO Q, CHEN L, et al.Contour mapmatching for event detection in sensor networks[A].Proc of the ACM SIGMOD[C].Chicago, USA, 2006.375-380.

[4]DU W, FANG L, NING P.Lad:localization anomaly detection for wireless sensor networks[A].Proc of the IEEE IPDPS[C].Denver,Colorado, 2005.121- 127.

[5]ASLAM J, BUTLER Z, CONSTANTIN F, et al.Tracking a moving object with a binary sensor network[A].Proc of the ACM SenSys[C].San Diego, USA, 2005.150-161.

[6]SRINIVASAN W W V, CHUA K C.Trade-offs between mobility and density for coverage in wireless sensor networks[A].Proc of the ACM MobiCom[C].Montreal, Quebec, Canada, 2007.39-50.

[7]LI Z J, LI M, WANG J L, et al.Ubiquitous data collection for mobile users in wireless sensor networks[A].Proc of the IEEE INFOCOM[C].Shanghai, China, 2011.2246-2254.

[8]LUO J, ZHANG Q, WANG D.Delay tolerant event collection for underground coal mine using mobile sinks[A].Proc of the IEEE IWQoS[C].Charleston, USA, 2009.1-9.

[9]SUGIHARA R, GUPTA R K.Optimizing energy-latency trade-off in sensor networks with controlled mobility[A].Proc of the IEEE INFOCOM[C].Rio, Brazil, 2009.1398-1408.

[10]XING G L, WANG T, JIA W J, et al.Rendezvous design algorithms for wireless sensor networks with a mobile base station[A].Proc of the ACM MobiHoc[C].Hongkong, China, 2008.231-240.

[11]郜帥, 張宏科.時延受限傳感器網絡移動 Sink路徑選擇方法研究[J].電子學報, 2011, 39(4):742-747.GAO S, ZHANG H K.Optimal path selection for mobile Sink in delayguaranteed sensor networks[J].Acta Electronica Sinica, 2011,39(4):742-747.

[12]程龍, 陳燦峰, 馬建.無線傳感器網絡中多移動 Sink的選擇策略[J].通信學報, 2008, 29(11):12-18.CHENG L, CHEN C F, MA J.Selection schema of mobile Sinks in wireless sensor networks[J].Journal on Communications, 2008, 29(11):12-18.

[13]KIM H S, ABDELZAHER T F, KWON W H.Dynamic delay- constrained minimum-energy dissemination in wireless sensor networks[J].ACM Transactions on Embedded Computing System, 2005,4(3):679-706.

[14]CROSSBOW.Mica and mica2 wireless measurement system datasheets[EB/OL].2004.

[15]ZHAO J, GOVINDAN R.Understanding packet delivery performance in dense wireless sensor networks[A].Proc of the ACM SenSys[C].Los Angeles, USA, 2003.311-320.

[16]張希偉，陳貴海.基于SDMA應用的移動Sink節點的設計與實現[J].計算機研究與發展, 2012, 49(3):541-549.ZHANG X W, CHEN G H.Design of mobile Sink node for SDMA applications in WSN[J].Journal of Computer Research and Development, 2012, 49(3):541-549.