基于移動sink的無線傳感器網絡數據采集方案

郭劍，孫力娟，許文君，王汝傳，肖甫

（1. 南京郵電大學 計算機學院， 江蘇 南京210003；2. 南京郵電大學 江蘇省無線傳感網高技術研究重點實驗室，江蘇 南京 210003；3. 南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003）

1 引言

無線傳感器網絡[1,2]（WSN, wireless sensor network）是一種具有廣泛用途的網絡，數據采集是其基本應用之一。人們在工作環境中布置大量的傳感器節點，并對需要的各種數據進行采集，如溫度、濕度、濃度、圖像、聲音、視頻等。實際應用中，許多業務的數據量都較大，比如圖像和視頻相關的應用，這就給數據采集方案的設計帶來了一定的挑戰。傳統的處理方法中，所有節點位置固定，采集到數據后，借助于路由協議將信息提交給sink。它的主要問題是：1）漏斗效應，距離 sink越近的節點能量消耗越大，網絡會較早地出現分割，大數據量的業務尤其如此；2）通信開銷，無論是哪種路由算法，都會有一定的控制開銷，需要耗費節點的能量；3）連通約束，網絡不連通時必然有部分節點的數據無法提交。

圖1 可移動節點

上述缺陷的部分根源在于sink的靜止性。隨著RacemoteZ[3]、quadcopter[4]等可移動節點的提出（如圖 1所示），一些學者提出了基于移動節點的采集方案[5,6]，部分解決了上述問題。此類方法的問題是存在一些時延[7,8]，并且難以確定 sink節點的移動方案。由于大多數數據采集型應用（data-gathering applications）對實時性要求不高，因此sink的移動控制才是關鍵，目前已有這方面的一些成果發表。隨機漫游[9]策略算法簡單，但是它不考慮節點的分布狀況，會導致節點能耗嚴重不均衡。AKKAYA等提出了一個啟發式移動策略[10]，sink每次向發送數據量最多的節點移動。這個策略比較適合事件驅動型應用（event-driven applications），但不適合數據采集型網絡。LUO[11]等提出了沿區域邊際移動的Peripheral策略，但Peripheral較為理想化，對MAC層的沖突考慮不夠。LMREM[12]方案根據節點的剩余能量來選擇移動位置，它的計算開銷較大，并且節點還需要保存和轉發較多的數據，網絡負荷很重時，節點很容易死亡。

針對這些問題，本文提出了一種軌跡固定的數據采集方案（DCSR, data collection scheme with regular track）。DCSR的移動策略包括2個環節：第一，根據節點的分布狀況選出一批采集點；第二，找到經過這些點的最短環路。這個環路就作為sink的采集路線，sink沿著它運動和收集數據。根據文獻[10]，在網絡中尋找最優采集地點是一個 NP問題。而計算最短環路是一個旅行商問題，也屬于NP問題。這2個步驟都沒有特別好的處理方法，因此本文均進行了簡化與近似。選取采集點時，DCSR盡量少選一些采集點，計算最短環路時，DCSR使用了量子遺傳算法[13,14]（QGA, quantum genetic algorithm）。對比測試表明，DCSR的性能較好，且能夠收集更多的數據。

2 WSN網絡模型

本文使用了如下的網絡模型。

1) 傳感器節點：網絡中使用的是同類型的傳感器節點，且它們具有相同的初始能量。這些節點被隨機部署在一個邊長為e的正方形監控區域中，且放置后不可移動。

2) sink節點：sink節點具有充沛的電池能量與較高的存儲容量，并有一定的移動能力。sink節點的通信距離與普通節點相同，均為r。

3) 業務類型：周期采集型業務，節點定期從傳感器上收集數據。

4) 數據提交模式：被動提交。節點收集到數據后存入自己的緩存；只有當它收到sink節點的通知時，它才提交數據。

在上述假設中，sink節點是較為關鍵的一個環節，實現時可以采用 RacemoteZ、quadcopter等可移動節點來獲得移動性，并通過大容量電池或定期充電等方式來保障能量供應。此外，本文在計算sink的移動路線時，沒有考慮現實道路情況對節點移動路徑的限制，也就是假設監控場景中地面較為平整，sink可以任意移動。當然，如果 sink采用quadcopter等飛行傳感器節點，這個問題就不存在。

3 采集點的確定

在第1個階段中，DCSR需要從監控區域中選出一批采集點。采集點的數量應該盡可能少，這樣可以減輕第2個階段的計算量，并且計算出的最短環路也相對更短。由于sink在每個采集點的通信范圍可以看成一個以采集點位置為圓心的圓盤，因此，第1個階段的任務就是找到一組坐標集合，并滿足如下條件：

1) 坐標的數量盡可能少；

2) 以這些坐標為圓心，r為半徑的一組圓盤能夠覆蓋監控區域。

3.1 圓盤位置的確定

在部署圓盤時，為了避免空隙，相鄰圓盤必然相互重疊。如圖2所示，圓盤A與B相鄰，它們相互重疊，而它們下方的空隙又由圓盤C來覆蓋，因此圓盤C也和它們相交。為了減少圓盤數，重疊的部分應越小越好。因此C的邊界應恰好覆蓋A與B的交點O。否則，它們之間或者產生三重重疊，或者出現空洞。此時就有了定理1。

圖2 相互重疊的3個圓盤

定理1 當兩兩重疊的3個圓盤圓心組成等邊三角形時，它們的重疊面積最小[15]。

證明 假設圓盤 A、B、C重疊的面積分別為SAB、SBC、SAC，則重疊的總面積S為

由于AXCYBZ是一個六邊形，因此有

2α+(π-α)+2β+(π-β)+2γ+(π-γ) = 4π

即

這里就是要求解滿足式(2)條件下的式(1)的極值。根據拉格朗日乘數法，可求得當 α= β= γ = π/3時，S的值最小。此時3個圓盤的圓心組成等邊三角形，且三角形的邊長為 3r。

滿足定理1的圓盤位置集合有多組，其中一組如式（3）所示，圖3為其分布示意。

圖3 圓盤分布示意

其中，m1、m2、m3、m4皆為非負整數，且滿足

3.2 采集點的選取

確定完所有的圓盤后，DCSR將在每個圓盤中選擇一個采集點。確定這個位置時，DCSR主要考慮了能耗的因素。

根據文獻[16]，當傳感器節點向外發送數據時，遵循式(4)。

其中，Gr、Gt分別表示接收端和發送端的天線增益，Pr、Pt分別表示接收端和發送端的天線功率，d為源節點與目標節點間的距離，L表示系統損耗因子，λ表示載波波長，通常Gr、Gt、L、λ都是常量。對于某一個具體的網絡來說，如果節點同質且干擾抑制較為理想，則Pr也可以認為是一個常量。因此式(4)可以簡寫為式(5)。

假定一個圓盤中有n個節點，則每次數據采集過程中，n個節點的總發射功率P為

其中，（xi，yi）表示第 i個節點的位置，(xs，ys)表示采集點的位置。

從式（6）可以看出，要使總發射功率最小，就應該選擇合理的采集點位置，使所有節點到它的距離平方和最小。

定理2 假定半徑為r的圓域中有n個點，每個點的坐標為（xi，yi），1≤i≤n。欲在該圓中找到一點，使得它到所有節點距離的平方和最小，則該點坐標是

證明 假設圓心的坐標為（xc，yc），該點坐標為（xs，ys），每個點到它的距離為di，1≤i≤n，則所有距離的平方和fs為

式(7)受式(8)的約束，

根據拉格朗日乘數法，可求得

定理2指出了sink節點的理想位置。但是，定理2不保證每個節點到該位置的距離di≤r。因此如果sink節點選擇該位置，部分節點的信息有可能會收集不到。此時就有了定理3。

定理 3 假設圓盤中最大、最小橫縱坐標分別為 xmax、xmin、ymax、ymin，(xs，ys)是所有節點坐標的平均值，則當式(10)成立時，圓盤內節點到（xs，ys）的距離均小于r。

因此，（xs，ys）到任一節點的距離

定理3說明，當圓盤內的節點分布符合式(10)時，可以采用式(9)計算采集點的位置。

進一步對節點分布進行分析。由于圓盤的半徑為r，易知

即(xs，ys)的范圍不會超出一個矩形區域，如圖4所示。假設該矩形的邊長分別為l1、l2。則有

圖4 采集點位置的坐標范圍

由式（11）可以看出，當圓盤中節點較為集中時，l1、l2相對較大，矩形面積SR也較大；反之當節點較為分散時，SR較小。由此可以得到定理4。

定理 4 當矩形面積 SR滿足式(12)時，式(10)成立。

證明 將式(12)展開并整理，即可得式(10)。

定理4說明，當矩形面積較大，滿足式(12)時，可采用所有節點的坐標均值作為采集點位置。

而當矩形的面積較小時，定理2不再適用。DCSR進行了近似處理，在水平方向和垂直方向上分別用 l條直線對這個矩形區域進行等分。等分之后，包括邊界在內，相交得到了(l+2)2個點。DCSR依次對這些點進行嘗試，找出距離之和最小的位置作為采集點。l值的大小跟求解精度相關，本文中取值40。

綜合以上各種情況，DCSR采用如下方法來計算采集點位置。

對于任一圓盤，設其中有n個節點，(xs，ys)為待求的采集點位置：

① 如果n=0，該圓盤內不設采集點；

② 如果 n=1，采集點位置即為唯一的節點坐標；

③ 如果n=2，取兩節點連線的中點作為采集點；

④ 如果n＞2，計算(xs，ys)所在的矩形區域：當該矩形區域面積較大，滿足式(12)時，計算所有節點坐標的平均值作為采集點，否則采用劃分網格的方法求近似點。

4 移動路徑的計算

得到了采集點之后，DCSR采用QGA來尋找經過這些點的最短環路。QGA是在遺傳算法的基礎上發展起來的一種算法。它引入了量子計算的概念，具有快速的收斂速度和較強的并行搜索能力，被廣泛運用于求解各種優化問題。在QGA中，組成種群的基本單位是量子染色體。每個量子染色體由多個量子比特組成。一條典型的量子染色體如式(13)所示。

其中，αij、βij∈C，且滿足i∈[1, n]，j∈[1, k]。n為染色體中的基因數，k為基因中的量子比特個數。

量子染色體向傳統染色體的轉換通過量子觀測操作實現，量子染色體的更新通過量子旋轉門實現。應用QGA的主要問題是染色體的編碼和適應度的計算。下面分別進行說明。

1) 染色體的編碼

DCSR采用了對采集點可選鏈路進行編碼的方法，在這種編碼策略中，染色體的每個基因對應一個采集點，基因的值就是在該采集點選中的鏈路編號。圖5給出了一個監控區域的實例，在圖5中共有A～G 7個采集點，連線表示可選的鏈路（過長的已剔除）。表1給出了這些鏈路的編號。圖6給出了一條染色體示例，它代表環路A-B-C-E-F-G-D-A。

圖5 采集點分布示意

表1 各采集點的鏈路編號

圖6 染色體示例

2) 適應度的計算

適應度主要考查2個因素：第一，染色體包含的鏈路中所構成的最長路徑是多少跳；第二，該最長路徑的長度是多少。適應度的計算如式(14)所示。

其中，f是計算出的適應度值，h是染色體中的鏈路所形成的最長路徑的跳數，l是該最長路徑的長度，α是調節系數，根據具體網絡決定。

5 DCSR方案

5.1 DCSR的具體步驟

DCSR的具體步驟如下。

1) 初始化：各節點向 sink節點匯報自己的位置信息。

2) 路徑計算：sink根據各節點的位置分布，依次采用第3節和第4節的方法分別計算出本網絡所需要的采集點以及經過這些采集點的最短回路。

3) 數據收集：sink沿計算好的路線移動，每到達一個采集點便廣播一條收集通知。附近的節點收到通知后，將保存的數據提交。為減少信道沖突，每個節點回復數據前需要隨機等待一段時間。

5.2 DCSR方案的性能分析

1) 時間復雜度

DCSR的路徑規劃包含2個步驟：計算采集點和計算路徑。

計算采集點時，由第3節可知，對于邊長為e的區域，其中至多有個圓盤，每個圓盤在最壞情況下嘗試(l+2)2個點，因此這一步驟的時間復雜度為

計算路徑采用了QGA。QGA的復雜性分析較難，學術界還沒有精確的理論成果發表，此處僅作近似分析。根據第4節的編碼方式，每個染色體有個基因，每個基因最多有個量子比特，因此每條染色體最多有個量子比特。假設QGA一共有m個染色體，算法一共迭代n次，每次迭代中要進行染色體的觀測、適應度的計算、染色體的更新和最優染色體的選擇4個操作，其時間復雜度分別為、O(m)。因此計算路徑的時間復雜度應為

由于l值不需要取很大，通常有mn＞ l2，因此，綜合這 2個步驟可知 DCSR的時間復雜度為

2) 通信代價及效率

采集數據時，DCSR在每個采集點僅廣播一條通知。整個監控區域至多有個圓盤，因此DCSR的通信代價是。

假設傳感器網絡由k個節點組成。在每一輪的數據采集中，sink節點至多廣播條通知，至少收到k個數據分組，因此，通信效率應不小于

6 仿真及測試

6.1 場景設置及測試指標

本文在NS 2.34環境下實現了DCSR 協議。為了驗證其性能，本文將它與靜止sink（stationary）方式、隨機（random）漫游策略和 Peripheral協議進行了對比測試。在這4個策略中，DCSR、Random采用了被動提交模式，節點收集到數據后將其保存在本地，收到通知后才發送給sink節點，Stationary、Peripheral采用了主動提交模式，節點收集到任何數據都主動向sink節點發送，因此需要借助于路由協議。其他實驗參數的設置如表2所示。

表2 實驗參數設置

在測試時，本文主要考察了如下6個指標。

1) 采集數據量：到達 sink節點的有效數據分組的數量。所謂有效數據分組是指含有采集數據的數據分組。

2) 吞吐量：網絡中所有數據分組的總數與網絡工作時間之比。網絡中的所有數據分組包括發送的數據分組、沖突重發的數據分組、節點轉發的數據分組、路由探詢分組和路由控制分組等。

3) 效率：sink收到的有效數據分組總數與網絡中所有數據分組的總數之比。

4) 剩余能量：網絡不能正常工作，即 sink采集不到數據時，網絡中所有節點的剩余能量。

5) 能量利用率：sink收集到的數據總量與網絡的總耗能之比。

6) 平均時延：到達 sink節點的有效數據分組的時延平均值。

6.2 實驗結果

1) 采集數據量

4種協議的采集數據量對比如圖7所示。其中，圖7(a) sink以5m/s的速度移動，圖7(b)sink以25m/s的速度移動，Stationary的sink節點均靜止不動，下同。從圖中可以發現，由于節點的增多和移動速度的加快，網絡中的沖突增加，因此所有方案收集的數據量均有所下降。DCSR由于節點不需要轉發數據，所以能耗較輕，工作時間相對較長，采集到的數據最多。Random由于路線不夠合理，會出現部分節點過早死亡和部分節點訪問不到的情況，因此收集的數據量要少一些。Stationary由于網絡很早就中斷，因此收集數據最少。

圖7 采集的數據量

2) 效率

4種協議的采集效率比較如圖 8所示。由于DCSR沒有路由開銷，且節點不需要轉發數據，因此采集效率較高。

3) 吞吐量

4種協議的網絡吞吐量（單位：分組數/s）比較如圖9所示。網絡吞吐量是衡量網絡性能的重要指標之一。從圖中可以看出，被動提交模式網絡的吞吐量要高于主動提交模式的網絡。這是因為節點沒有轉發數據的負擔，因此可以一直工作，不會過早死亡。而主動提交模式的網絡，大量節點很早就死亡，個別節點的數據sink節點又不易采集，因此網絡的吞吐量較低。DCSR由于路線比Random合理，數據采集更穩定，吞吐量更高。

圖8 網絡效率

圖9 吞吐量

4) 剩余能量

4種協議的網絡剩余能量比較如圖10所示。從圖中可以看出，在Stationary策略中，sink靜止不動導致周圍節點很快死亡，網絡很早中斷，所以剩余能量較多，這實際上也是能量的浪費。在使用移動sink的3種策略中，DCSR的路線最為合理，且節點不承擔轉發任務，能量消耗較為均衡，因此網絡工作結束時，能量幾乎全部消耗完，且全部用在提交數據上。

圖10 剩余能量

5) 能量利用率

4種協議的能量利用率比較如圖11所示。它的實際意義是網絡每消耗1J能量，sink所能采集到的有效數據量。從圖中可以看出，DCSR能量的利用率比其他3個協議都高。

圖11 能量利用率

6) 平均時延

4種協議的平均時延比較如圖12所示。從圖中可以發現，被動提交模式的時延比主動提交模式的時延要高，這是因為數據的轉發速度要高于sink的移動速度。而Random的時延又要遠高于DCSR，這是由于DCSR盡量尋找最短的路徑，路線較為合理，因此時間較少。需要說明的是，大多數數據采集型應用，尤其是非實時業務，其時延要求并不高，DCSR還是比較適用的。

圖12 平均時延

7 結束語

在數據采集型應用中采用移動sink節點能夠帶來多方面的好處。它可以提升網絡的吞吐量，均衡節點的能量消耗，提高數據的采集效率，并且當網絡出現分割時也能正常工作。本文設計的DCSR協議，較好地體現了這些優勢。受到節點移動速度的限制，DCSR協議在收集數據時會產生一定的時延。因此，對于數據量較大、時限要求不高的采集型業務，DCSR協議具有較好的應用前景。下一步的研究內容是在傳感器節點上引入數據融合機制，將它與DCSR協議結合后，網絡的性能應該會更好。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] POTDAR V, SHARIF A, CHANG E. Wireless sensor networks: a survey[A]. Proceedings of International Conference on Advanced Information Networking and Applications[C]. Bradford, 2009. 636-641.

[3] SONG G M, ZHOU Y X, DING F, et al. A mobile sensor network system for monitoring of unfriendly environments[J]. Sensors, 2008, 8:7259-7274.

[4] ACHTELIK M, ZHANG T G, KUHNLENZ K, et al. Visual tracking and control of a quadcopter using a stereo camera system and inertial sensors[A]. Proceedings of the International Conference on Mechatronics and Automation[C]. Changchun, China, 2009. 2863-2869.

[5] WANG W, SRINIVASAN V, CHAING K C. Using mobile relays to prolong the lifetime of wireless sensor networks[A]. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking[C]. Cologne, 2005. 270-283.

[6] BI Y Z, SUN L M, MA J, et al. HUMS: an autonomous moving strategy for mobile sinks in data-gathering sensor networks[J]. EURASIP Journal on Wireless Communications and Networking, 2007: 1-15.

[7] XING G L, WANG T, XIE Z H, et al. Rendezvous planning in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1442.

[8] 郜帥, 張宏科, 徐懷松. Sink 軌跡固定傳感器網絡的高效數據采集機制[J]. 軟件學報, 2010, 21(1): 147-162.GAO S, ZHANG H K, XU H S. Efficient data gathering approach in sensor networks with path-fixed sinks[J]. Journal of Software, 2010,21(1): 147-162.

[9] JAIN S, SHAH R C, BORRIELLO G. Exploiting mobility for energy efficient data collection in sensor networks[J]. Mobile Networks and Applications, 2006, 11(3): 327-339.

[10] AKKAYA K, YOUNIS M, BANGAD M. Sink repositioning for enhanced performance in wireless sensor networks[J]. Computer Networks, 2005, 49(4): 512-534.

[11] LUO J, HUBAUX J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[A]. Proceedings of the 24th Annual Conf of the IEEE Computer and Communications Societies[C]. Miami,2005. 1735-1746.

[12] TAN C G, XU K, WANG J X, et al. A sink moving scheme based on local residual energy of nodes in wireless sensor networks[J]. Journal of Central South University of Technology, 2009, 16(2): 265-268.

[13] XIAO J, YAN YP, ZHANG J, et al. A quantum-inspired genetic algorithm for k-means clustering[J]. Expert Systems with Applications,2010, 37(7): 4966-4973.

[14] GU J W, GU M Z, CAO C W, et al. A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J]. Computers & Operations Research, 2010,37(5): 927-937.

[15] ZHANG H H, HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(1-2): 89-124.

[16] PAOLO S. Topology Control in Wireless Ad Hoc and Sensor Networks[M]. Chichester: John Wiley & Sons Ltd, 2005.

[17] SETHI S, ROUT A, MOHANTA D. Hybrid activities of AODV for wireless ad hoc sensor network[A]. Proceedings of International Conference on Recent Trends in Business Administration and Information[C]. Trivandrum, 2010. 39-44.