多移動匯聚節點的無線傳感網中基于服務質量的能耗

王漫漫，束永安

(安徽大學 計算機科學與技術學院，合肥 230601)

0 引言

無線傳感技術已經被廣泛應用到不同的領域，例如健康監測、軍事和環境監測與跟蹤。由于傳感器網絡節點部署密度大、環境復雜、節點體積小、電池容量有限，所以通過最優化能量消耗來有效延長網絡生命周期是無線傳感網絡需要解決的一個問題。另外，針對傳統Ad Hoc網絡提出的服務質量(Quality of Service, QoS)協議都存在由端到端路徑發現和資源預留引起的大量開銷，因此，它們不適用于資源受限的無線傳感器網絡。為此，專門設計了一些機制為無線傳感網(Wireless Sensor Network, WSN)提供QoS服務。在這里，主要集中在時延和數據完整性的度量上。

在能耗方面，文獻[1-2]提出通過利用移動匯聚節點來延長無線傳感網的生命周期。該方法通過對移動匯聚節點路徑的控制，使得在延長傳感網生命周期上有明顯的效果；然而，該方法雖然簡單，易于實現，但是不可控、性能較差，因此，文獻[3]主要通過確定移動匯聚節點的移動的最佳軌跡來延長無線傳感網絡的網絡生存時間。在該類型中，主要存在兩個問題。第一，移動匯聚節點必須經過預先確定的特殊位置或特殊節點。第二，在移動節點快速移動的過程中，需要確定移動匯聚節點移動的速度和軌跡。以前的研究表明可以通過數學模型化來解決最佳移動軌跡。另外，在移動軌跡方面，文獻[4]還提出了VGDRA(Virtual Grid-based Dynamic Routes Adjustment)方法，該方法通過將網格區域劃分為同樣大小的網格，從而簡單而精確地確定移動匯聚節點的軌跡，因此虛擬骨干網是由格頭節點組成的網絡。該方法主要是由網格內的傳感器節點將數據傳送至格頭節點，格頭節點再通過虛擬骨干網將數據路由至移動匯聚節點，但是，該方法使得數據包經過較長的路徑傳輸至移動匯聚節點，浪費較多的能量。為此，文獻[5]提出了GLRM(Grid-based Load-balanced Routing Method)方法，該方法利用文獻[4]類似的分簇方法，區別是該方法僅把數據包路由至邊界節點，再等待移動匯聚節點移動至該區域內進行數據包傳送，從而節省了能量。

在服務質量方面(QoS)，文獻[6]提出了ReInforM(Reliable Information forwarding using Multiple paths)。該方法通過采用動態數據包狀態的概念來控制所需路徑的可靠性，但是，缺點在于該方法需要知道全局拓撲架構。因此，文獻[7]提出LIEMRO(Low-Interference Energy-efficient Multipath ROuting protocol)，該方法在網絡運行過程中，根據最新感知的路徑質量，利用動態路徑維護機制監測活動路徑的質量和調整該路徑數據包的注入率；然而，它并沒有根據活動節點的緩沖容量和服務速率估計和調整活動路徑的流量。

于是，文獻[8]提出LOCALMOR(LOCALized MOdular Routing)，該方法考慮了時延、可靠性和能耗。該方法根據需求將輸入的數據包分成三個隊列，然后把完整性要求高的數據包發送到主匯聚點和次匯聚點，從而造成很大的開銷。在[8]的基礎上，文獻[9]提出了一種基于兩跳鄰居信息的梯度路由機制來提高實時性能，該方法中的路由是由源節點到匯聚節點的跳數信息和兩跳信息決定的。文獻[10]提出了IDDR(Integrity and Delay Differentiated Routing)算法，該算法通過引入引力域的概念，并具體介紹深度引力域和隊列引力域，通過該方法將不同要求數據包選擇最合適的路徑傳輸至匯聚節點，從而滿足了數據包的時延要求和完整性要求，該方法在整體性能上取得進一步的提升。

針對無線傳感器網絡，如何設計能夠提供數據完整性和時延敏感性要求，同時節省能耗的路由協議，是一個極具挑戰性的問題。本文的主要工作在于引入多移動匯聚節點的機制,提出一種多移動匯聚節點考慮服務質量的算法——時延敏感和數據完整性(Multi-Sink Time Sensitive Data Integrity, MSTSDI)算法。首先，將網絡按照K-means聚類方法分成合適的自治區域，再給每個自治區域分配一個移動匯聚節點；然后利用支持向量回歸(Support Vector Regression, SVR)方法確定移動匯聚節點的軌跡；最后引入深度引力域和隊列引力域采用Improved-IDDR算法對數據包進行傳送，從而提供高完整性和時延敏感的服務。

1 系統場景及模型

本文提出的算法的系統模型如圖1所示，系統所設場景為由N個隨機部署的傳感器節點組成的無線傳感網絡。該網絡中數據僅由傳感器節點產生，移動匯聚節點不產生數據。網絡中只有匯聚節點移動，傳感器節點會根據傳感器節點之間的距離調整傳輸功率使其相一致。另外，移動匯聚節點沒有資源限制。在該網絡中，每個傳感器節點都有兩種模式：監視和發送。若傳感節點捕獲事件，則將狀態傳感節點改變至發送狀態；處于發送節點的傳感器節點將會把數據發送至移動匯聚節點。由于移動匯聚節點的速度是有限的，在大規模無線傳感器網絡中收集數據是不切實際的，因此引入多移動匯聚節點機制。首先，采用K-means方法將無線傳感器網絡劃分為m個自治區域，Zi,i=1∶m，然后給每個自治區域分配一個匯聚節點。其中每個區域由n個隨機部署的無線傳感器節點Si，i=1∶n和一個移動匯聚節點組成的。該移動匯聚節點以有限的恒定速度V移動。

圖1 系統模型圖 Fig. 1 Diagram of system model

2 算法總體流程

當該無線傳感網部署完成后，所有傳感節點進入監測狀態。當傳感節點捕獲事件，將狀態轉換為發送狀態，然后傳感器節點將感知的數據發送到該自治區域的移動匯聚節點。

該算法的總體流程如圖2所示，主要分為3部分：1)利用K-means聚類算法將該無線傳感網聚類成合適的自治區域。2)利用SVR數學模型找出移動匯聚節點的最佳軌跡。3)引入引力域，利用Improved-IDDR算法將時延敏感和數據完整性要求高的數據包傳送至移動匯聚節點，普通數據包則采用“坐等算法”。

圖2 MSTSDI流程 Fig. 2 Flow chart of MSTSDI algorithm

3 MSTSDI算法各環節設計

3.1 生成自治區域

由于移動匯聚節點的速度和無線傳感節點的傳輸范圍是有限的，因此，在大規模的無線傳感網中及時有效地收集數據是不現實的，于是，將無線傳感網中分成若干個自治區域。

在傳感器網絡部署階段，基站向所有傳感器節點廣播信標信號。傳感器節點通過接收信號強度計算到基站(Base Station, BS)的距離。首先，根據節點密度，BS從網絡中確定K個傳感器節點作為每一個自治區域的平均值或中心值；其次，對于剩余的每個傳感器節點，計算其與各自治中心的距離，將它賦給最近的自治區域；然后，重新計算每個自治區域的平均值。這個過程不斷重復，直到準則函數收斂。通常采用平方誤差準則，其定義如下：

(1)

其中：E是該自治區域中所有傳感器節點的平方誤差的總和，p是自治區域中的傳感器節點，mi是每個自治區域的平均值。該目標函數使生成的自治區域盡可能地緊湊獨立，該方法使用的距離是歐幾里得距離。K-means聚類算法的流程如下：

1)根據節點密度選擇K個傳感器節點作為初始的自治區域的中心。

2)根據自治區域的平均值，將其余每個傳感器節點劃分至距離最近的自治區域。

3)更新自治區域的平均值，即每個自治區域對象的平均值。

4)重復上述步驟，直到自治區域中的傳感器節點基本穩定，不再發生變化即可。

3.2 確定最佳軌跡

如引言所述，為了避免發生網絡空洞的現象，從而使網絡生命周期最大化，因此需要確定移動匯聚節點的最佳軌跡，下面利用SVR方法來確定移動匯聚節點的最佳軌跡。

將傳感器節點劃分為自治區域以后，采用SVR的方法找出移動匯聚節點的最佳軌跡。假定有一組傳感器節點目標對{(xi,yi)},xi∈Rn,yi∈Rn,i=1∶j，線性SVR通過訓練找出線性函數F(x)=φTxi+θ的φ和θ。對于所有的訓練數據，該線性函數與實際獲得的目標yi偏離至多為ε。因此，需要最小化歐幾里得范數，它可以寫成如下凸優化問題：

(2)

滿足：

yi-φTxi-θ≤ε； ?i

(3)

yi-φTxi-θ≥ε； ?i

(4)

其中:φ和θ是自由變量，用來確定軌跡方程。

(5)

滿足：

yi-φTxi-θ≤ε+ξi； ?i

(6)

(7)

接下來，采用拉格朗日乘子法，則有：

(8)

滿足：

λi≥0；i=1,2,…,n

(9)

(10)

1-yi(xiφT+θ)≤0；i=1,2，…,n

(11)

(12)

消去φ之后得：

(13)

可知，適用拉格朗日乘子法和KKT條件以后，求φ和θ的問題轉換為求拉格朗日因子的問題λ的問題。

3.3 使用Improved-IDDR算法將數據傳送至移動匯聚節點

如引言所述，在無線傳感網中，針對傳統Ad Hoc網絡提出的服務質量(QoS)協議都存在由端到端路徑發現和資源預留引起的大量開銷，因此它們不適用于資源受限的無線傳感器網絡。針對該問題，提出Improved-IDDR算法。

3.3.1 引力域的概念

在確定移動匯聚節點的最佳軌跡以后，將采用Improved-IDDR算法來傳輸數據包。該算法通過減少時延敏感數據包的路徑長度來降低端到端的時延，同時使數據完整性要求高的數據包通過負載低的路徑來提高數據包的完整性。

該算法引入引力域模型作為數據傳輸的模型，即將數據包的傳輸過程看作是類似于水流從碗的表面流向碗底的過程，那么數據包的傳輸軌跡即是由作用于數據包上的力決定的。

(14)

深度差[DA(t)-DB(t)]∈{-1，0，1}，因為兩個節點之間的跳數多于一跳的話就不是鄰居節點。

(15)

可以發現，節點B緩存的數據包越少，隊列域力就越大。因此，被這個隊列域驅動，包將會繞過負載比較重的區域被提交到輕負載的區域。

(16)

假設α=0，只有隊列域工作，它不能保證由節點產生的數據包最后被傳送到匯聚節點，因此，讓α>0。

3.3.2 包的權值以及α值和β值

每個數據包頭部含8位的權值，高4位表示時延敏感度的等級，低4位表示數據完整性的等級。高4位權值越大，則數據包的時延越敏感；低4位權值越大，則數據包的完整性要求越高。Improved-IDDR用權值來計算不同的引力域斜率：

(17)

(18)

0xf0是高四位權值的最大值，0x0f是低四位權值的最大值。較大的α表示深度引力域的權值較大，該數據包很難被踢出最短路徑隊列；較大的β表示隊列引力域的權值較大，該數據包會沿著負載小的路徑傳輸數據包。Improved-IDDR選擇較短路徑傳輸高四位權值較大的數據包，從而降低端到端的時延，選擇負載小的路徑傳輸低四位權值較大的數據包來提高數據包的完整性。

3.3.3 “坐等”算法

在MSTSDI算法中，采用“坐等”方法傳輸普通數據包。首先把離移動匯聚節點軌跡最近的左右節點定義為邊界節點。當傳感器節點產生了普通的數據包，會沿著如圖3所示的路徑傳輸，將數據包傳輸到該行的邊界簇頭節點，直到匯聚節點移動至距該邊界格頭節點最近時進行傳輸。

圖3 “坐等”算法圖 Fig. 3 Diagram of “wait” algorithm

3.3.4 Improved-IDDR算法

Improved-IDDR在節點i的主要算法步驟如下。

1)如果節點i的隊列不空，則隊列頭部數據包P的α和β為：

2)W(i,b)(t)={βQi(t)+αDi(t)-[βQb(t)+αDb(t)]}其中b∈Ωi[n]。

3)選擇{W(i,b)(t)}max為最大值的鄰居節點b為下一跳。

4) 節點i發送數據包P。

5) 如此循環，直至數據包發送至匯聚節點。

3.4 復雜度分析

假設該無線傳感網中有N個傳感器節點，并且被分為K個自治區域，那么每個自治區域的節點個數平均為N/K。自治區域的建立階段分為控制數據廣播、選擇自治區域的中心和網絡配置。在控制數據的廣播階段，每個傳感器節點的控制信息包括自身ID號的HELLO包，共有N個數據包。基站收到所有的信息包之后，在網絡配置階段，會以泛洪的方式發送一個數據包，使得網絡節點了解網絡的整體情況。

另外，該網絡的傳感器節點會根據網絡的整體情況從N個傳感器節點選擇K個傳感器節點作為初始的中心節點，而對于剩下的傳感器節點，則根據它們與這些中心節點的距離將它們分配給距離最近的中心節點。然后，重新計算每個新的中心節點，直到標準測度函數收斂。因此，該算法是一種基于劃分的歸類算法，算法快速簡單，對大數據有較高的效率，并且是可伸縮的，時間復雜度趨于線性為O(NKt)，t是迭代的次數，其中K?N,t?N，該算法的空間復雜度為O(N*h),其中N為傳感器節點的個數，h是每個傳感器節點特征個數。

4 性能仿真與分析

4.1 仿真場景與參數設置

為了驗證所提算法的有效性，在Matlab中進行了仿真實驗，場景設置：400個傳感節點被隨機部署在400 m×400 m的正方形區域，表1為該算法設置的實驗仿真參數。

表1 實驗中所使用的仿真參數Tab. 1 Simulation parameters used in the experiment

4.2 仿真結果分析

參數α和參數β分別代表數據包的時延敏感度的等級和數據完整性的等級，因此，這兩個參數在該算法起著非常重要的作用。為了探討參數α和參數β對該算法的影響，通過設置不同的權值，進而產生不同的參數值，進行一系列的仿真實驗。圖4所示為不同應用場景下，三種算法在初始能量相同的情況下運行相同輪數時所剩余的能量圖。可以看出，這三種算法隨著運行的輪數增加，所剩余的能量不斷降低。在各個場景中，新算法所剩余能量最多，GLRM次之，低功耗自適應集簇分層型協議(Low Energy Adaptive Clustering Hierarchy protocol, LEACH)最少。原因在于，GLRM采用三個參數的方法選擇簇頭，因此，在給定的時間內，可以比LEACH節省更多的能量。而本文所提出的算法，針對普通數據包采用“坐等”算法傳輸數據包至移動匯聚節點。該算法可以使數據包經過最短的路徑至移動匯聚節點，節省最多的能量。針對時延敏感的數據包則引入深度引力域，立即采用最短路徑傳送數據包至移動匯聚節點，經過較短的路徑，較短的時間傳送至移動匯聚節點，節省較多的能量。針對數據完整性較高的數據包，則引入隊列引力域，將數據包經過負載較低的路徑將數據包傳送至移動匯聚節點。所以，該算法比其他兩種算法所剩余的平均能量要高。

圖4 三種算法剩余能量隨運行輪數的變化曲線 Fig. 4 Relationship between residual energy and rounds

平均時延和包丟失率隨參數α和參數β的性能變化曲線如圖5和圖6所示。

從圖5可以看出，在不同的應用下，隨著α的增加，平均時延逐漸減小。這是因為隨著α的增大，說明數據包的時延敏感等級逐漸增加，該數據包將通過最短路徑傳輸至移動匯聚節點。所以，每個應用都會隨著α的增加，數據包的時延會降低。從圖6可以看出，在不同的應用下，隨著β的增加，丟包率逐漸降低。這是因為隨著β的增加，說明數據包的數據完整性等級逐漸增加，該數據包將通過負載比較低的路徑被傳輸至移動匯聚節點。所以，每個應用都會隨著β的增加數據包的丟包率降低。

圖5 時延隨α的變化曲線 Fig. 5 Relationship between end-to-end delay and parameter α

圖6 丟包率隨β的變化曲線 Fig. 6 Relationship between packet loss rate and parameter β

平均能耗隨參數α和β的性能變化曲線如圖7。從圖7可以看出，在不同的應用下，隨著α的增加，能耗逐漸減少。這是因為隨著α的增大，說明數據包的時延敏感度等級逐漸增加，該數據包將通過較短的路徑被傳送至移動匯聚節點，因此該數據包會經過較少的跳數到達移動匯聚節點，從而消耗較少的能量。

圖7 能耗隨α的變化曲線 Fig. 7 Relationship between energy consumption and parameter α

5 結語

本文分析了傳統的無線傳感網所面臨的挑戰，特別是路由策略在減少傳感器節點能耗的同時，不能兼顧數據包的時延敏感性和數據完整性。針對該問題，本文進行了多移動匯聚節點關于QoS的能耗研究。本文通過采用多移動匯聚節點的機制，避免能量空洞的發生。首先，將該傳感網通過K-means聚類方法分成多個自治區域；然后，采用SVR方法找出移動匯聚節點的最佳軌跡；最后，采用Improved-IDDR算法傳輸數據包，使得數據完整性高的數據包經過低負載的路徑傳輸至匯聚節點，使得時延敏感的數據包經過較短的路徑傳輸至匯聚節點。實驗結果表明，MSTSDI算法利用引力域比普通的路由策略有更好的節能性，并達到較好的服務質量的要求，證明了該路由策略的有效性。下一步，主要綜合考慮研究在多移動匯聚節點的情況下，如何使用分布式算法確定最佳軌跡，以及如何使用確定最佳的多跳傳輸方案從而實現多目標的優化策略。

參考文獻(References)

[1] LUO J , HUBAUX J P. Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility [J]. IEEE/ACM Transactions on Networking, 2010, 18(3)：871-884.

[2] LI Z, LI M. WANG J, et al. Ubiquitous data collection for mobile users in wireless sensor networks [EB/OL]. [2017- 03- 09]. http://www3.ntu.edu.sg/home/limo/papers/Mobile-INFO11.pdf.

[3] TASHTARIAN F, HOSSEIN Y M M. SOHRABY K, et al. On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks [J]. IEEE Transactions Vehicular Technology, 2015, 64(7): 3177-3189.

[4] KHAN A W, ABDULLAH A H, RAZZAQUE M A, et al. VGDRA: a virtual grid-based dynamic routes adjustment scheme for mobile sink-based wireless sensor networks [J]. IEEE Sensors Journal, 2015, 15(1): 526-534.

[5] LIU Q, ZHANG K, SHEN J, et al. GLRM: an improved grid-based load-balanced routing method for WSN with single controlled mobile sink [C]// Proceedings of the 2016 18th International Conference on Advanced Communication Technology. Piscataway, NJ: IEEE, 2016: 34-38.

[6] DEB B, BHATHATNAGAR S, NATH B. ReInForM: reliable information forwarding using multiple paths in sensor networks [C]// LCN ’03: Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks. Washington, DC: IEEE Computer Society, 2003: 406.

[7] RADI M, DEZFOULI B, BAKAR K A, et al. Interference-aware multipath routing protocol for QoS improvement in event-driven wireless sensor networks [J]. Tsinghua Science and Technology, 2011,16(5): 475-490.

[8] DJENOURI D, BALASINGHAM I. Traffic-differentiation-based modular QoS localized routing for wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2010,10(6): 797-809.

[9] QUANG P T A, KIM D S. Enhancing real-time delivery of gradient routing for industrial wireless sensor networks [J]. IEEE Transactions on Industrial Informatics, 2012, 8(1): 61-68.

[10] ZHANG J, REN F, GAO S, et al. Dynamic routing for data integrity and delay differentiated services in wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2015, 14(2): 328-343.

[11] 馮曉蒲,張鐵峰.四種聚類方法之比較[J].微型機與應用,2010,29(16):1-3.(FENG X P, ZHANG T F. Comparison of four clustering methods [J]. Microcomputer & Its Applications, 2010,29(16):1-3.)

This work is partially supported by Natural Science Foundation of Anhui Province (1408085MF125).

WANGManman, born in 1989, M. S. candidate. Her research interests include wireless sensor network.

SHUYong’an, born in 1966, Ph.D., professor. His research interests include wireless sensor network, software defined network, next-generation network.