基于服務質量的層次化結構資源分配算法

丁鋮，陳錦榮，曹小冬，王翊

研究與開發

基于服務質量的層次化結構資源分配算法

丁鋮，陳錦榮，曹小冬，王翊

（中國南方電網有限責任公司廣東電網公司佛山供電局，廣東 佛山 528010）

無線傳感器網絡（wireless sensor network，WSN）具有節點體積小、成本低、感知能力強等優勢，被廣泛應用于物聯網（internet of things，IoT）場景中。如何在保證WSN負載平衡的前提下，提高業務服務質量（quality of service，QoS）成為眾多學者關注的問題。在研究WSN中基于啟發式的資源分配方法和基于層次化結構的資源分配方法基礎上，提出了一種基于服務質量的層次化結構資源分配算法（quality of service based hierarchical resource allocation algorithm，QoSHRA）。首先，利用基于低能耗自適應聚類層次（low-energy adaptive clustering hierarchy，LEACH）協議的資源分配方法使整個網絡形成層次化結構；然后，利用QoSHRA進行資源分配。仿真結果表明，QoSHRA在保證網絡負載平衡的前提下，進一步節約了網絡傳輸能耗，保障了業務分配的有效性，提高了網絡資源的QoS需求滿足率。

物聯網；無線傳感器網絡；服務質量；資源分配方法

0 引言

物聯網（internet of things，IoT）是將各種信息傳感設備與互聯網結合在一起的網絡。作為21世紀初革命性的技術之一，它在現代無線電信場景中正迅速普及。無線傳感器網絡（wireless sensor network，WSN）具有節點體積小、成本低、感知能力強等優點，被廣泛應用于IoT的各個領域中，是IoT的核心技術之一。在電力行業中，WSN在輸電線路在線監測、配電網絡智能抄表等方面作用突出，具有較強的研究價值。

由于傳感器節點能量、數據處理能力及數據傳輸能力有限，如何高效利用WSN，平衡網絡負載，成為IoT資源分配方式領域的主要研究點。傳統的資源分配算法主要包含兩種類型，一種是啟發式算法，如基于蟻群的資源分配算法，通過建立能耗模型，將能量均衡因素加入概率轉移、信息素更新等公式模型中，提高節點能量使用效率，達到平衡網絡負載的目的；另一種是分層算法，如基于低能耗自適應聚類層次（low-energy adaptive clustering hierarchy，LEACH）協議的資源分配算法，通過選擇合適的節點成為資源分配節點，并形成層次化結構，利用動態分層的方式，達到有效利用節點能量、平衡網絡能耗的目的。然而，人們對WSN性能的要求遠不止如此。以輸電線路場景為例，面向輸電線路在線監測的WSN具有監測業務多樣、業務重要程度不同的特點，所以設計一種針對多業務場景的、能滿足重要業務服務質量（quality of service，QoS）需求的WSN資源分配方法至關重要。

目前在面向QoS的WSN資源分配算法方面的研究主要有：

● 文獻[10]提出了基于動態馬爾可夫鏈的資源分配方案，將物聯網中的業務流量分為優先級和非優先級，用于確保延遲敏感流量的QoS；

● 文獻[11]提出了基于業務優先級的資源分配方案，通過改進Dijkstra算法將業務分為高優先級和低優先級，建立負載均衡模型，在保證高優先級業務QoS的前提下，使整個網絡負載均衡；

● 文獻[12]針對物聯網技術中的傳統資源分配方法節點能耗差異大、業務分配靈活性不足的問題，提出了一種基于能耗的啟發式分層算法和一種基于業務優先級的層次化結構資源分配算法，將業務時延作為QoS的主要依據，為不同業務分配滿足時延需求的傳輸路徑，同時節約傳輸能耗，保證網絡負載均衡，該算法的設計理念與本文提出的資源分配算法有一些相似之處。

綜上所述，本文提出一種基于服務質量的層次化結構資源分配算法（quality of service based hierarchical resource allocation algorithm，QoSHRA）。

1 系統模型與算法研究

1.1 系統模型

1.1.1 拓撲模型

基于服務質量的層次化結構資源分配模型如圖1所示，物聯網主要由感知層、網絡層、應用層組成。感知層主要用于感知各種信息并匯聚給網絡層；網絡層主要利用互聯網將來自感知層的數據統一存儲并管理；應用層主要是將網絡層的數據處理后應用于IoT各個領域。本文重點研究物聯網感知層的資源分配協議，物聯網感知層主要由4部分組成：感知節點、資源分配節點、備份節點和網關節點。感知節點用于信息采集，并將信息發送給資源分配節點；資源分配節點用于收集感知節點及相鄰資源分配節點發送的信息并對信息按相關資源分配協議進行信息轉發；備份節點用于備份每個層次化結構內的資源分配節點，如果資源分配節點失效，則備份節點代替資源分配節點進行信息收集和轉發；網關節點用于收集感知網絡的信息，所有感知節點采集的信息最終都匯聚至網關節點。

圖1　基于服務質量的層次化結構資源分配模型

由圖1可以看出，本文的資源分配算法是一種基于層次化結構的資源分配算法。根據基于LEACH協議的資源分配算法形成層次化結構后，每個資源分配節點會根據收集到的各個業務數據QoS要求不同而規劃相匹配的路徑進行信息傳輸。除此之外，備份節點會替代失效的資源分配節點進行信息傳輸，從而進一步保障業務QoS需求并優化網絡能耗。

本文算法基于監測業務多樣、感知節點能量有限的場景特征，并做出如下假設：

● 所有傳感器都是靜止的，不同監測業務的QoS要求不同，但數據大小基本一致；

● 所有傳感器都知道自己的剩余能量，并根據通信距離調整傳輸功率；

● 鏈路是對稱的，無線電信號在所有方向上具有相同的能量衰減；

● 所有傳感器都能夠在資源分配模式和信息感知模式下運行。

1.1.2 能量模型

假設兩個距離為的節點之間傳輸bit數據時，發送端所消耗的能量sc為：

定義為兩節點之間的歐氏距離，即：

節點接收bit所消耗的能量為：

其中，rc為接收數據需要的能量。

因此，如果整個網絡共有個節點，則總能耗tc為：

其中，n*為節點向節點發送數據的過程中由于鏈路故障而使數據丟失的數量。

1.1.3 QoS要求

假設整個網絡中有多種資源，每種資源的QoS要求主要由時延要求衡量，端到端的總時延主要包括傳輸時延、處理時延和排隊時延，將第種資源記為S，其時延要求為cst，則資源分配節點從收集數據到數據傳輸至網關節點所用時間S應滿足Scst。

假設資源分配節點對同種資源處理的QoS需求為常數，并假設資源在各個分配節點的排隊時間相等且為常數，考慮到資源的傳輸速度值遠大于距離值，則本文將忽略傳輸時延，將各個資源的QoS需求=que+pro設置為定值，其中，que、pro分別為同種資源的排隊時延和處理時延。因此，本文將各個資源的QoS約束轉換為跳數約束如式（9）所示。

1.2 算法研究

1.2.1 算法分析

（1）基于QoS分析與負載均衡的資源分配機制

本文設計的資源分配機制基于QoS分析。在每一輪的數據傳輸階段，資源分配節點同時接收分層結構內節點數據及相鄰資源分配節點的轉發數據。假設每個業務資源都具有QoS要求，在分配資源過程中，每個資源分配節點利用Dijkstra算法計算到網關節點的最短距離；然后，對優先級最高的資源選擇與之相對應的最優路由進行資源分配，并標記該路徑；進而，考慮次優先級資源，在滿足QoS要求的情況下，優先在未被標記的節點中選擇與最優路由進行資源分配并同樣對該路徑進行標記，如果沒有滿足QoS要求的路徑，則分配最短路徑給該資源；最后，重復上述過程，直至所有資源被分配完畢。

1）基于數據有效率和QoS的路由排序機制

該機制首先根據以往數據傳輸是否滿足QoS需求確定規劃路徑的數據有效率，綜合考慮路徑長度和數據有效率確定路由質量，并最終對路由表排序。

假設每個資源分配節點每次轉發數據給相鄰分配節點后，該分配節點對相鄰分配節點的轉發計數加1，轉發計數用Cs表示（初始化為1），如果該轉發數據在滿足QoS需求的前提下到達網關節點，該分配節點對相鄰分配頭節點的接收計數加1，接收計數用Cr表示（初始化為1），則規劃路徑的數據有效率Eff為：

其中，表示發送數據的資源分配節點，表示接收數據的相鄰資源分配節點。

在形成層次化結構后，每個資源分配節點利用Dijkstra算法初始化到網關節點的距離用Len表示，則路由質量評價式RQ為：

其中，表示發送數據的資源分配節點，表示接收數據的相鄰資源分配節點，表示規劃路徑的數據有效率系數，表示路由長度倒數的系數。

2）基于QoS的資源排序機制

依據QoS要求制定優先級hc；每經過一個資源分配節點，更新優先級hc。

本文假設每個業務都具有一個基本QoS需求和最低QoS需求，基本QoS需求用hc表示，最低QoS需求用hc表示。初始化數據包的優先級為：

則經過hc跳后，該數據包的優先級為：

（2）基于能耗的資源分配節點故障備份機制

考慮到非資源分配節點的故障備份需求不高，為了優化節點能耗，本文算法只保證資源分配節點的有效性。備份節點與資源分配節點之間周期性地進行故障檢測以確定對方節點是否失效。

1）基于信息協商傳感協議的故障定位機制

在資源分配節點進行信息轉發的過程中，本文參考了一種基于傳感器信息協商協議（sensor protocols for information via negotiation，SPIN）的故障診斷機制，并對該機制進行了改進。本文的故障診斷機制主要使用檢測（CHECK）信息、認證（VERIFY）信息兩種類型的信息。

步驟1 每個分層結構中，資源分配節點或備份節點周期性向對方發送CHECK信息。

步驟2 如果目的節點正常，在接收到CHECK信息后，回復VERIFY信息給CHECK信息發送節點；否則，如果CHECK信息發送節點在一定時間內未收到相應的VERIFY信息，則認為對方節點發生故障，啟動故障節點備份機制。

步驟3 CHECK信息發送節點在收到相應的VERIFY信息后，確認對方節點未失效，本次故障診斷過程結束。

2）基于能耗的備份節點選擇機制

在網絡形成分層結構后，建立備份節點選擇模型，利用該模型選出資源分配節點的備份節點。資源分配節點周期性地與備份節點同步路由信息。備份節點選擇模型如下：

其中，為節點ID，1、2、3、4分別為節點與分層結構內其他節點的距離系數、節點與分層結構內資源分配節點的距離系數、節點與網關節點的距離系數以及節點剩余能量系數，ave-node為分層結構內節點與其他節點的平均距離，allot為分層結構內其他節點到資源分配節點的距離，sink為節點到網關節點的距離，remain為節點的剩余能量。

本文假設每個分層結構內有個節點，資源分配節點為0節點，則第個節點的ave-node可表示為：

其中，為兩點之間的距離。則ave-node的平均數`ave-node可表示為：

則allot的平均數`allot可表示為：

則每個分層結構內非資源分配節點到網關節點距離的平均數`sink可表示為：

則每個分層結構內非資源分配節點的平均剩余能量`remain可表示為：

1.2.2 算法設計

（1）基于QoS分析與負載均衡的資源分配機制

在利用基于LEACH協議的資源分配算法形成層次化結構后，本文提出了一種基于QoS分析與負載均衡的資源分配機制。該機制首先對可分配資源的傳輸路徑進行鏈路質量評估，然后根據業務QoS要求對業務數據排序，最終選擇與業務QoS要求匹配的路徑進行數據傳輸，保障業務的QoS需求并進一步優化節點能耗?；赒oS分析與負載均衡的資源分配機制流程如圖2所示。

圖2　基于QoS分析與負載均衡的資源分配機制流程

（2）基于能耗的資源分配節點故障備份機制

為了減小失效節點對資源分配可靠性的影響，提高數據傳輸質量，本文提出了一種基于能耗的資源分配節點故障備份機制。通過考慮層次化結構內節點的剩余能量、傳輸能耗、地理位置等因素，該機制建立基于能耗的備份節點選擇機制，挑選出每個層次化結構內的備份節點。當資源分配節點失效或備份節點失效時，基于SPIN的故障診斷機制可以保證觸發資源分配節點故障備份機制，從而維護整個網絡的正常運轉。基于能耗的資源分配節點故障備份機制流程如圖3所示。

2 仿真實驗與分析

2.1 仿真環境設置

本文模擬物聯網下的長鏈狀拓撲、多業務并存的場景結構，基于MATLAB仿真以驗證QoSHRA的有效性。

2.2 仿真參數設置

仿真參數設置見表1。

圖3　基于能耗的資源分配節點故障備份機制流程

表1　仿真參數設置

2.3 仿真實驗

本文對文獻[12]提出的基于時延和負載均衡的面向輸電線路物聯感知與監測應用的層次化結構路由規劃方法（delay and load-balancing based hierarchical route planning method for transmission line IoT sensing and monitoring applications，DLHRP）、基于蟻群的資源分配算法和本文所提出的QoSHRA分別進行仿真實驗。由于DLHRP的分層機制也是一種基于LEACH協議的資源分配機制，所以為了方便對比，在仿真時，使用DLHRP的分層機制形成層次化結構后，執行這3種資源分配算法。

QoSHRA是一種基于層次化結構的資源分配算法，本文記錄了每次形成分層結構后網絡節點的失效情況。在仿真時，記錄3種算法的節點失效情況，不同資源分配算法的節點失效情況如圖4所示。

對能量為0或發生故障的節點數量進行統計?；谙伻旱馁Y源分配算法和DLHRP的失效節點數都存在波動，這是因為這兩種算法未考慮資源分配節點失效情況，當資源分配節點失效時，該層次化結構內的所有節點數據都無法傳輸至網關節點，而本文算法具有故障備份機制，可以保證資源分配節點的有效性。本文提出的QoSHRA失效節點數明顯小于另外兩種算法，這是因為本文算法是一種基于業務優先級的資源分配方法，可以在為不同資源分配路徑的同時，考慮整個網絡的能耗狀況，與DLHRP相比，QoSHRA通過建立鏈路質量模型和業務優先級模型，能夠在保證網絡QoS的前提下，進一步優化網絡能耗。

圖4　不同資源分配算法的節點失效情況

為了直觀地看出3種資源分配算法下的網絡節點能量均衡情況，記錄了3種算法的有效節點剩余能量標準差，不同資源分配算法的有效節點剩余能量標準差如圖5所示。

圖5　不同資源分配算法的有效節點剩余能量標準差

與蟻群算法相比，本文所提出的QoSHRA和DLHRP都能使整個網絡節點具有更小的能量差異，這是因為QoSHRA和DLHRP在進行資源分配的時候，會考慮每個節點的負載情況，使業務更加均衡地分配給每個相鄰資源分配節點傳輸。與DLHRP相比，本文算法通過建立鏈路質量模型和業務優先級模型，使資源分配更加高效，通過建立故障備份機制，減少了失效節點數量，進一步均衡網絡能耗。

與DLHRP相比，本文所提出的QoSHRA在進行路由規劃時對鏈路質量進行了分析，同時，為保證業務資源能夠有效傳輸至網關節點，本文提出了一種基于能耗的資源分配節點故障備份機制。為了突出本文算法在保障業務QoS需求方面的優越性，對每次形成分層結構后各個業務的QoS滿足率進行了統計，業務QoS需求滿足率如圖6所示。

圖6　業務QoS需求滿足率

圖6中，本文所提出QoSHRA的業務QoS需求滿足率明顯高于DLHRP，這是因為本文算法的資源分配節點在進行路徑規劃的時候考慮了鏈路質量，對業務資源優先選擇高QoS保障的路徑進行傳輸。除此之外，本文所提出的故障備份機制保障了每個資源分配節點的有效性，降低了節點失效率，提高了整個網絡的QoS。

3 結束語

為了提高面向多業務場景的WSN的QoS，更有效地利用有限的能源資源，本文提出了QoSHRA。該算法主要包含基于QoS分析與負載均衡的資源分配機制和基于能耗的資源分配節點故障備份機制兩個子機制。通過建立基于QoS分析與負載均衡的資源分配機制，資源分配節點能夠為不同QoS需求的業務分配與其匹配的傳輸路徑，從而提高整個網絡的QoS，節約傳輸能耗、平衡網絡負載；通過建立基于能耗的資源分配節點故障備份機制，為每個資源分配節點選出合理的備份，從而保證資源分配節點的有效性，提高路由質量。仿真結果顯示，與基于蟻群的資源分配算法相比，QoSHRA可以平衡網絡負載，節約網絡傳輸能耗；與DLHRP相比，QoSHRA可以進一步節約網絡傳輸能耗，保障業務分配的有效性，提高網絡的QoS需求滿足率。

[1] PORTILLA J, MUJICA G, LEE J S, et al. The extreme edge at the bottom of the internet of things: a review[J]. IEEE Sensors Journal, 2019, 19(9): 3179-3190.

[2] ATZORI L, IERA A, MORABITO G. The internet of things: a survey[J]. Computer Networks, 2010, 54(15): 2787-2805.

[3] Attia T M. Challenges and opportunities in the future applications of IoT technology[C]//Proceedings of 2nd Europe-Middle East-North African Regional ITS Conference. New York: International Telecommunications Society (ITS), 2019: 52.

[4] XU N. A survey of sensor network applications[J]. Ad Hoc & Sensor Wireless Networks, 2002, 25(1): 1-44.

[5] GAUTAM P R, KUMAR S, VERMA A, et al. Energy-efficient localisation of sensor nodes in WSNs using single beacon node[J]. IET Communications, 2020, 14(9): 1459-1466.

[6] XUE J B, ZHANG T, WANG W H. A routing algorithm based on high energy efficiency in cooperation WSN[M]//Lecture Notes in Electrical Engineering. London: Springer London, 2013: 129-136.

[7] BEIRANVAND Z, PATOOGHY A, FAZELI M. I-LEACH: an efficient routing algorithm to improve performance & to reduce energy consumption in Wireless Sensor Networks[C]//Proceedings of 5th Conference on Information and Knowledge Technology. Piscataway: IEEE Press, 2013: 13-18.

[8] KONG P Y, LIU C W, JIANG J A. Cost-efficient placement of communication connections for transmission line monitoring[J]. IEEE Transactions on Industrial Electronics, 2017, 64(5): 4058-4067.

[9] DU L, WANG C S, LI X Z, et al. A novel power supply of online monitoring systems for power transmission lines[J]. IEEE Transactions on Industrial Electronics, 2010, 57(8): 2889-2895.

[10] SHARMA R, KUMAR N. QoS-alert Markov chain based scheduling scheme in Internet of Things[C]//Proceedings of 2015 IEEE Globecom Workshops (GC Wkshps). Piscataway: IEEE Press, 2015: 1-6.

[11] LI P, XU S Y, SUN K, et al. A path planning method of wireless sensor networks based on service priority[C]// Proceedings of 2017 13th International Conference on Network and Service Management (CNSM). Piscataway: IEEE Press, 2017: 1-4.

[12] DING C, XU S Y, CHEN X Y, et al. A delay and Load-balancing based hierarchical route planning method for transmission line IoT sensing and monitoring applications[C]// Proceedings of 2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM). Piscataway: IEEE Press, 2019: 207-215.

[13] 陸俊, 朱炎平, 徐志強, 等. 面向輸電線路監測的無線傳感網絡可靠路由方法研究[J]. 電網技術, 2017, 41(2): 644-650.

LU J, ZHU Y P, XU Z Q, et al. A reliable wireless sensor network routing method for power transmission line monitoring[J]. Power System Technology, 2017, 41(2): 644-650.

[14] 呂濤. 無線傳感器網絡分簇路由協議及其應用研究[D]. 成都: 電子科技大學, 2013.

Lü T. Research on cluster-based routing protocol and its application for wireless sensor networks[D]. Chengdu: University of Electronic Science and Technology of China, 2013.

[15] 羅杰. 輸電線路狀態監測中的無線傳感器網絡時延研究[D]. 長沙: 湖南大學, 2014.

LUO J. Research on delay of wireless sensor network in transmission line condition monitoring[D]. Changsha: Hunan University, 2014.

[16] KUMAR DEVA SARMA H, RAI P, DEKA B. Energy efficient communication protocol for wireless sensor networks with mobile node[C]//Proceedings of International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014). Piscataway: IEEE Press, 2014: 1-6.

[17] PAUL A K, SATO T. Effective data gathering and energy efficient communication protocol in wireless sensor network[C]//Proceedings of 2011 The 14th International Symposium on Wireless Personal Multimedia Communications (WPMC). Piscataway: IEEE Press, 2011: 1-5.

[18] ZHU H, LI Q S, SHAO M C, et al. A Load-balancing and Fault-tolerant based route planning algorithm for wireless sensor networks[C]//Proceedings of 2018 IEEE International Conference on Electronics and Communication Engineering (ICECE). Piscataway: IEEE Press, 2018: 81-85.

Quality of service based hierarchical resource allocation algorithm

DING Cheng, CHEN Jinrong, CAO Xiaodong, WANG Yi

Foshan Power Supply Bureau of China Southern Power Grid Co., Ltd., Foshan 528010, China

Wireless sensor network (WSN) is widely used in the internet of things (IoT) scene because of its small size, low cost and strong sensing ability. How to improve the quality of service (QoS) under the premise of load balancing in WSN has become the focus of many scholars. Based on the study of heuristic resource allocation method and hierarchical structure resource allocation method in WSN, a quality of service based hierarchical resource allocation algorithm (QoSHRA) was proposed. Firstly, the resource allocation method based on low energy adaptive clustering hierarchy (LEACH) made the whole network form a hierarchical structure. Then, QoSHRA was used for resource allocation. The simulation results show that QoSHRA can further save the energy consumption of network transmission, ensure the effectiveness of service allocation, and improve the satisfaction rate of network resource QoS requirements on the premise of ensuring network load balancing.

internet of things, wireless sensor network, quality of service, resource allocation method

TP393

A

10.11959/j.issn.1000?0801.2022005

2021?08?15；

2021?12?10

丁鋮（1993?），男，中國南方電網有限責任公司廣東電網公司佛山供電局助理工程師，主要研究方向為物聯網與無線傳感器網絡。

陳錦榮（1975?），男，中國南方電網有限責任公司廣東電網公司佛山供電局高級工程師，主要研究方向為電力物聯網技術。

曹小冬（1986?），男，中國南方電網有限責任公司廣東電網公司佛山供電局高級工程師，主要研究方向為物聯網與無線網絡優化。

王翊（1989?），男，中國南方電網有限責任公司廣東電網公司佛山供電局高級工程師，主要研究方向為物聯網與無線網絡優化。