基于業(yè)務(wù)質(zhì)量的網(wǎng)絡(luò)資源分配方法

朱紅　韋磊　李秋生　邵明馳　藺鵬

摘 要：為了高效利用無線傳感器網(wǎng)絡(luò)（WSN）能源資源，論文提出了一種基于業(yè)務(wù)質(zhì)量的網(wǎng)絡(luò)資源分配方法（SQNR）。該算法基于業(yè)務(wù)質(zhì)量需求分析，以節(jié)約傳輸能耗為優(yōu)化目標(biāo)，為不同優(yōu)先級的業(yè)務(wù)分配不同的傳輸路徑，從而節(jié)約傳輸能耗、優(yōu)化網(wǎng)絡(luò)資源效用。仿真結(jié)果表明，論文提出的方法能夠在保證業(yè)務(wù)質(zhì)量要求的條件下，優(yōu)化網(wǎng)絡(luò)運(yùn)行，并延長網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；資源分配；業(yè)務(wù)質(zhì)量；生命周期

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

1 引言

無線傳感器網(wǎng)絡(luò)（WSN）是由部署在監(jiān)測區(qū)域內(nèi)大量的微型傳感器節(jié)點(diǎn)構(gòu)成的多跳自組織網(wǎng)絡(luò)。該網(wǎng)絡(luò)利用傳感器節(jié)點(diǎn)采用無線通信方式協(xié)作地實(shí)時監(jiān)測、感知和采集各種對象信息，并對數(shù)據(jù)進(jìn)行處理[1]。WSN已在電力系統(tǒng)中的電量檢測、配電網(wǎng)繼電保護(hù)、故障定位、設(shè)備狀態(tài)檢測、應(yīng)對自然災(zāi)害等方面都有廣泛應(yīng)用。同時，結(jié)合能源互聯(lián)網(wǎng)中大量有源與無源的無線傳感器，WSN還可應(yīng)用于高塔監(jiān)測、發(fā)/用電信息實(shí)時采集、高空視頻協(xié)作傳輸?shù)取Ｈ欢?，在電力通信網(wǎng)中不同業(yè)務(wù)的傳輸質(zhì)量要求具有較大差異性[2]。因此，研究能在保證多種業(yè)務(wù)不同質(zhì)量要求的前提下，節(jié)約能耗并延長資源分配網(wǎng)絡(luò)生命周期的方法具有重要意義。

針對資源分配問題已有較多研究成果。Salehpour等人提出了一種用于大規(guī)模聚類的無線傳感器網(wǎng)絡(luò)資源分配算法。該算法令簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)直接發(fā)送至簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)使用蟻群優(yōu)化算法規(guī)劃通往基站的最佳路徑。算法通過使用蟻群優(yōu)化算法和分簇來最小化算法的延遲，最終達(dá)到降低功耗，平衡負(fù)載的目的[3]。

Xiao等人提出了一種基于簡單人工魚群優(yōu)化和蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)聚類資源分配算法。與以往基于蟻群的路由算法不同，該算法使簇頭節(jié)點(diǎn)的選擇要考慮備選節(jié)點(diǎn)的位置和所需簇頭節(jié)點(diǎn)的數(shù)量。該算法進(jìn)一步優(yōu)化了數(shù)據(jù)傳輸過程的能耗并提升了整個網(wǎng)絡(luò)的負(fù)載平衡性[4]。

Yao等人提出了一種基于低能量自適應(yīng)聚類分層集中算法的聚類資源分配協(xié)議。該算法是對LEACH-C算法的改進(jìn)，在簇間路由方面執(zhí)行一種單跳與多跳相結(jié)合的算法，所有數(shù)據(jù)在距離匯聚節(jié)點(diǎn)小于一定閾值后，數(shù)據(jù)通過單跳傳輸至匯聚節(jié)點(diǎn)。該算法降低了匯聚節(jié)點(diǎn)附近簇頭節(jié)點(diǎn)的通信負(fù)載，提升了整個通信網(wǎng)絡(luò)的負(fù)載均衡程度[5]。

從Heinzelman等人提出了LEACH分層資源分配協(xié)議開始，許多學(xué)者開始研究并擴(kuò)展優(yōu)化該協(xié)議[6，7]。然而，過去的簇間資源分配算法都沒有考慮到對分配業(yè)務(wù)進(jìn)行區(qū)分，從而降低了數(shù)據(jù)傳輸?shù)撵`活性。

為解決以上問題，本文提出了一種基于業(yè)務(wù)質(zhì)量的網(wǎng)絡(luò)資源分配方法（Service Quality based Network Resource allocation method，，SQNR）。該方法通過對到達(dá)簇頭節(jié)點(diǎn)的不同業(yè)務(wù)，根據(jù)其優(yōu)先級分配不同的傳輸路徑實(shí)現(xiàn)負(fù)載均衡。通過本文設(shè)計(jì)的算法，可以在各業(yè)務(wù)數(shù)據(jù)滿足其時延要求的情況下，低級別的業(yè)務(wù)通過“繞遠(yuǎn)”傳輸至目的節(jié)點(diǎn)，防止網(wǎng)絡(luò)擁堵，避免節(jié)點(diǎn)負(fù)載不均衡，從而減少失效節(jié)點(diǎn)的數(shù)量，以延長達(dá)網(wǎng)絡(luò)生命周期。

2 系統(tǒng)模型

假設(shè)整個網(wǎng)絡(luò)中有N個傳感器節(jié)點(diǎn)，每個傳感器節(jié)點(diǎn)位置都固定并具有一定的記錄能力。每個節(jié)點(diǎn)具有位置和剩余能量兩種屬性。節(jié)點(diǎn)的位置用二維坐標(biāo)表示為P（x， y）， 剩余能量用Elast表示。假設(shè)所有節(jié)點(diǎn)的業(yè)務(wù)信息最終都匯聚至匯聚節(jié)點(diǎn)，并且匯聚節(jié)點(diǎn)的被配置太陽能電板以及蓄電池，該節(jié)點(diǎn)能量不受限制。

算法為時延要求比較低的業(yè)務(wù)分配路徑時，由于時延需求比較低，可以在滿足時延約束的條件下通過犧牲時延來達(dá)到負(fù)載均衡，例如圖1中從黑色路徑轉(zhuǎn)為白色路徑，從而提高的網(wǎng)絡(luò)節(jié)點(diǎn)的利用率并延長了網(wǎng)絡(luò)的生命周期。

2.1 能耗模型

發(fā)送節(jié)點(diǎn)發(fā)送n-bits數(shù)據(jù)所需要的能耗是[8]：

（1）

接收節(jié)點(diǎn)接收n-bits數(shù)據(jù)所需要的能耗是：

（2）

Eelec為發(fā)射電路損耗的能量，其值取決于節(jié)點(diǎn)本身的物理屬性。因此整個網(wǎng)絡(luò)的總能耗為：

（3）

為節(jié)點(diǎn)i與它的下一跳j的歐式距離：

（4）

Index是距離指數(shù)，隨通信距離的變化而變化：

（5）

dthreshold是d的閾值：

（6）

為多路徑衰減信道模型的功率放大系數(shù)，為自由能量衰減模型功率放大系數(shù)。

為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均剩余能量：

（7）

2.2 業(yè)務(wù)質(zhì)量約束

在本文中，業(yè)務(wù)質(zhì)量即為業(yè)務(wù)數(shù)據(jù)傳輸?shù)臅r延。假設(shè)整個網(wǎng)絡(luò)中傳輸?shù)臉I(yè)務(wù)有M種，分別記為{S1， S2， …SM}，它們的時延限制分別為并且他們的關(guān)系為。

不同的業(yè)務(wù)真實(shí)的端到端一定要小于等于時延限制。所以時延的約束條件應(yīng)該是：

（8）

假設(shè)同種業(yè)務(wù)的數(shù)據(jù)包的排隊(duì)時延和處理時延近似相等，而由于數(shù)據(jù)傳輸?shù)木嚯x相比于速度可以忽略不計(jì)，即Lave=Lqueue+Lprocess+Ltransmission是一個定值，Lqueue， Lprocess， Ltransmission分別為同種業(yè)務(wù)的排隊(duì)時延，處理時延和傳播時延，因此可以將時延約束轉(zhuǎn)化為跳數(shù)約束：

（9）

2.3 基于時延的業(yè)務(wù)優(yōu)先級劃分

首先，在業(yè)務(wù)達(dá)到之前，根據(jù)業(yè)務(wù)的時延要求為業(yè)務(wù)制定初始優(yōu)先級x。然后，在調(diào)度時，根據(jù)網(wǎng)絡(luò)實(shí)時擁塞狀況，考察各優(yōu)先級類的平均排隊(duì)時延，對當(dāng)前優(yōu)先級X進(jìn)行實(shí)時計(jì)算，即對某些積壓嚴(yán)重的優(yōu)先級數(shù)據(jù)包暫時提高其優(yōu)先級等級。

假設(shè)數(shù)據(jù)包的初始優(yōu)先級為x，且該數(shù)據(jù)包滿足時延要求滿足，則該數(shù)據(jù)包當(dāng)前優(yōu)先級 的計(jì)算方法為：

（10）

其中，Lqueue是該數(shù)據(jù)包在某一調(diào)度時刻的排隊(duì)時延。v是用于提升業(yè)務(wù)優(yōu)先級的具體量化值。假設(shè)，當(dāng)前業(yè)務(wù)數(shù)據(jù)包的時延要求不滿足時，對該數(shù)據(jù)包的優(yōu)先級提升v，使其滿足時延要求。Ls為該業(yè)務(wù)對數(shù)據(jù)包時延L要求的標(biāo)準(zhǔn)值。p為對業(yè)務(wù)時延的評估值，其計(jì)算方式如下：

（11）

2.4 負(fù)載均衡約束

本文采用傳感器節(jié)點(diǎn)剩余能量的標(biāo)準(zhǔn)差來衡量整個網(wǎng)絡(luò)的負(fù)載均衡程度，即。本文假設(shè)，所有剩余能量不為0的節(jié)點(diǎn)標(biāo)準(zhǔn)差越小，整個網(wǎng)絡(luò)的負(fù)載越均衡。簇頭節(jié)點(diǎn)在進(jìn)行資源分配時，總能在滿足相應(yīng)業(yè)務(wù)質(zhì)量要求的情況下，盡可能的分配使整個網(wǎng)絡(luò)負(fù)載均衡的路徑。

當(dāng)整個傳感器網(wǎng)絡(luò)完成一次數(shù)據(jù)傳輸過程（單位：跳），每個節(jié)點(diǎn)的剩余能量進(jìn)行如下更新：

（12）

整個傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量的標(biāo)準(zhǔn)差應(yīng)該低于執(zhí)行本次數(shù)據(jù)轉(zhuǎn)發(fā)后所有節(jié)點(diǎn)能量的標(biāo)準(zhǔn)差，即在執(zhí)行本次數(shù)據(jù)轉(zhuǎn)發(fā)后，標(biāo)準(zhǔn)差應(yīng)滿足如下條件：

（13）

3 算法設(shè)計(jì)

3.1 算法分析

Dijkstra算法思想：設(shè)G=（V，E）是一個帶權(quán)有向圖，分頂點(diǎn)集合V為兩組，已求出最短路徑的頂點(diǎn)集合為第一組（用S表示，初始時S中只有一個源點(diǎn)，以后每求得一條最短路徑 ， 就將其頂點(diǎn)加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），其余未確定最短路徑的頂點(diǎn)集合為第二組（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。

在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個頂點(diǎn)對應(yīng)一個距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。

本文采用改進(jìn)型的Dijkstra算法。假設(shè)網(wǎng)絡(luò)有兩種業(yè)務(wù)：1業(yè)務(wù)和2業(yè)務(wù)，業(yè)務(wù)1的時延需求高于2。仍然設(shè)置一個帶權(quán)有向圖G=（V，E），那么將網(wǎng)絡(luò)中的節(jié)點(diǎn)集合V分為三組，V=（V1，V2，U）。已經(jīng)求出來的最短路徑的節(jié)點(diǎn)集合為第一組（用V1表示）；在求第一組的最短路徑集合時，同時記錄并排序其他路徑的集合，該集合為第二組（用V2表示）；其余未確定最短路徑的集合為第三組（用U表示）。在選擇當(dāng)前節(jié)點(diǎn)的下一跳時，1業(yè)務(wù)選擇V1集合中的頂點(diǎn)，2業(yè)務(wù)也優(yōu)先選擇V1集合中的節(jié)點(diǎn)（恰好2業(yè)務(wù)選擇的節(jié)點(diǎn)沒有被1業(yè)務(wù)使用），同時判斷是否滿足負(fù)載均衡約束，如果滿足，則繼續(xù)進(jìn)行下一跳，如果不滿足，則從V2集合中選擇最短的路徑下一跳，同樣判斷是否滿足負(fù)載均衡約束，滿足選擇下一跳，若不滿足則從集合V2選擇次短路徑的下一跳，一直循環(huán)直到滿足負(fù)載均衡條件。

簇頭節(jié)點(diǎn)在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時，根據(jù)業(yè)務(wù)優(yōu)先級劃分后的最高優(yōu)先級業(yè)務(wù)選擇最短路徑進(jìn)行轉(zhuǎn)發(fā)，對于較低優(yōu)先級業(yè)務(wù)的轉(zhuǎn)發(fā)需要考慮負(fù)載均衡約束條件，如果選擇的較短路徑不滿足負(fù)載均衡約束，則選擇更長的路徑，這樣可以均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量，進(jìn)而延長網(wǎng)絡(luò)的生命周期。

3.2 算法步驟

本文的算法將由無線傳感器網(wǎng)絡(luò)的管理中心執(zhí)行并將收集到的已排序好的路由表發(fā)送給各個簇頭節(jié)點(diǎn)。網(wǎng)絡(luò)管理中心已知所有節(jié)點(diǎn)的位置，剩余能量，點(diǎn)與點(diǎn)之間的權(quán)重（距離）等信息，并執(zhí)行改進(jìn)型的最短路徑算法將所有路徑放入V1， V2中。

改進(jìn)型的最短路徑算法流程如下：

Algorithm 1： Improved shortest path algorithm；

Input： Weight of each side w， G=（V，E）， V=（V1，V2，U）， source node s；

Output： V1， V2；

Initialization： V1=V2{s}； U={other vertices}； if u is not a neighbor of s， w=∞；

1： select a vertex x with the shortest distance to s from U， add x to V1； add other adjacent vertices to V2 set；

2： sort V2={VI， VII， VIII} according to their w；

3： select new vertex y with x as middle node；

4： if the distance from x to y is shorter than the distance from s to y；

5： w=w+w；

6： go to line 8；

7： else；

8： The vertices sorted in V2 set are taken as intermediate nodes and same operation is performed；

9： go to line 11；

10： end if；

11： if all vertices are included in V1 and V2；

12： end of the process；

13： else；

14： go to line 1；

15： end if。

在簇頭節(jié)點(diǎn)接收到路由表以后，每個簇頭節(jié)點(diǎn)先對該時刻內(nèi)到達(dá)的業(yè)務(wù)數(shù)據(jù)包進(jìn)行時延分析并排序它們的業(yè)務(wù)優(yōu)先級。在該時刻中，簇頭節(jié)點(diǎn)優(yōu)先考慮較高業(yè)務(wù)優(yōu)先級的數(shù)據(jù)包，在為一個數(shù)據(jù)包規(guī)劃路徑時，先根據(jù)數(shù)據(jù)包的時延限制及排隊(duì)情況更新其優(yōu)先級，如果該數(shù)據(jù)包的優(yōu)先級提升至最高，則按最短路徑進(jìn)行轉(zhuǎn)發(fā)，如果不是，則簇頭節(jié)點(diǎn)從排序好的V2中依次選擇較短路徑，并將所選路徑上傳至網(wǎng)絡(luò)管理中心。網(wǎng)絡(luò)管理中心分析該路徑是否滿足負(fù)載均衡約束，如果滿足則該業(yè)務(wù)按所選路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，否則簇頭節(jié)點(diǎn)從V2中依次選擇較長路徑并執(zhí)行上述過程直至所選路徑滿足負(fù)載均衡約束。

基于業(yè)務(wù)質(zhì)量分析的網(wǎng)絡(luò)資源分配方法流程如下：

Algorithm 2： Service Quality based Network Resource allocation method （SQNR）

Input： Packet hop limit H， packet priority x， cluster-head node set C， V1， V2， Esend， Ereceive；

Output： packet priority X， Elast ， ；

Initialization： initial energy of nodes Einit；

1： for each cluster-head node in set C；

2： analyze service quality requirements of arrived data packets and get packet priority x and delay limit in each of them；

3： sort arrived data packets according to their packets priority；

4： select a new data package；

5： update its packet priority X according to formula （10）；

6： if it is the highest-priority service；

7： select the next hop from V1；

8： if the package reach sink node；

9： go to line 4；

10： else；

11： go to line 5；

12： end if；

13： else；

14： select the next hop from V2 that can make decrease；

15： if the package reach sink node

16： go to line 4；

17： else；

18： go to line 5；

19： end if；

20： end if；

21： end for。

4 仿真實(shí)驗(yàn)

4.1 仿真參數(shù)設(shè)置

本文使用MATLAB模擬面向輸電線路在線監(jiān)測的WSN場景進(jìn)行仿真實(shí)驗(yàn)。仿真參數(shù)如表1所示，仿真結(jié)果均為多次實(shí)驗(yàn)結(jié)果的均值。

4.2 仿真結(jié)果

仿真實(shí)驗(yàn)中，假設(shè)匯聚節(jié)點(diǎn)位于最右端，每個傳感器節(jié)點(diǎn)都可以自發(fā)地產(chǎn)生數(shù)據(jù)包和轉(zhuǎn)發(fā)數(shù)據(jù)包，所有的資源分配算法基于靜態(tài)均勻分簇算法。對蟻群算法和SQNR算法的資源分配方式分別進(jìn)行仿真，仿真結(jié)果如圖2和圖3所示。

從圖2和圖3中可以看出，對于蟻群算法，該算法在進(jìn)行資源分配時，不考慮業(yè)務(wù)質(zhì)量需求。它先嘗試搜尋路徑并在搜尋路徑時留下信息素，最終根據(jù)留下信息素的多少判斷傳輸方式的優(yōu)劣。該算法會對所有需要轉(zhuǎn)發(fā)的信息都采用最優(yōu)的資源分配方式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。而SQNR算法中，該算法對不同業(yè)務(wù)的優(yōu)先級進(jìn)行排序。對于低質(zhì)量要求業(yè)務(wù)（時延要求低），該算法會在滿足業(yè)務(wù)質(zhì)量要求的前提下，選擇節(jié)約能耗并使整個網(wǎng)絡(luò)負(fù)載均衡的方式分配資源，最終使業(yè)務(wù)質(zhì)量要求比較高的業(yè)務(wù)選擇的較短路徑，而業(yè)務(wù)質(zhì)量要求比較低的業(yè)務(wù)選擇“繞遠(yuǎn)”路徑。

在仿真時，記錄下兩種算法每一輪的節(jié)點(diǎn)死亡情況，比較兩種算法死亡第一個節(jié)點(diǎn)和30%，60%及90%節(jié)點(diǎn)死亡的輪數(shù)，結(jié)果如圖4所示。

由于SQNR算法對于低時延要求的數(shù)據(jù)采用使整個網(wǎng)絡(luò)負(fù)載均衡的路由規(guī)劃方式，所以整個網(wǎng)絡(luò)的能耗較為均衡，節(jié)點(diǎn)死亡較慢。由圖4可以看出，SQNR算法的節(jié)點(diǎn)死亡時間晚于蟻群算法，因此有更好的能量效率。

圖5為兩種算法每五輪的所有生存節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差。從圖4中可以更加直觀的看出，SQNR算法的每輪所有生存節(jié)點(diǎn)剩余能量標(biāo)準(zhǔn)差明顯小于蟻群算法。

5 結(jié)束語

傳感器網(wǎng)絡(luò)被應(yīng)用在生活中的各個領(lǐng)域。無線傳感器網(wǎng)絡(luò)（WSN）是傳感器網(wǎng)絡(luò)中較為復(fù)雜的一個分支。本文提出了一種無線傳感器網(wǎng)絡(luò)場景下的網(wǎng)絡(luò)資源分配方法，即基于業(yè)務(wù)質(zhì)量的網(wǎng)絡(luò)資源分配方法（Service Quality based Network Resource allocation method， SQNR）。該算法是一種適用于簇間的資源分配方式。與基于蟻群算法的資源分配方式相比，SQNR算法通過轉(zhuǎn)發(fā)不同業(yè)務(wù)數(shù)據(jù)包給不同的路徑，節(jié)約了低延時要求業(yè)務(wù)的數(shù)據(jù)傳輸能耗并提升了整個網(wǎng)絡(luò)的負(fù)載均衡程度。仿真結(jié)果顯示，該算法可以在保證業(yè)務(wù)質(zhì)量要求的前提下，有效平衡資源分配網(wǎng)絡(luò)中各個節(jié)點(diǎn)的能耗，最終延長整個網(wǎng)絡(luò)的生命周期。

基金項(xiàng)目：

1. 國網(wǎng)江蘇省電力公司科技項(xiàng)目（項(xiàng)目編號：J2017072）；

2. 國家科技重大專項(xiàng)（項(xiàng)目編號：2017ZX03001013）。

參考文獻(xiàn)

[1] R. Fang， J. Wang， W. Sun， Q. Li. QoS Model of WSNs Communication in Smart Distribution Grid [J]. International Journal of Distributed Sensor Networks， 2016（8）： 1-23.

[2] Verma S， Rana P. Wireless communication application in smart grid： An overview[C]// IEEE， 2015：310-314.

[3] Salehpour A A， Mirmobin B， Afzali-Kusha A， et al. An energy efficient routing protocol for cluster-based wireless sensor networks using ant colony optimization[C]// International Conference on Innovations in Information Technology. IEEE， 2008：455-459.

[4] Xiao H， Zhao X， Ogai H. A New Clustering Routing Algorithm for WSN based on Brief Artificial Fish-School Optimization and Ant Colony Optimization[J]. Ieej Transactions on Electronics Information & Systems C， 2013， 133（7）：1339-1349.

[5] Yao F. Cluster Routing based on Low Energy Adaptive Clustering Hierarchy Centralized Algorithm in Wireless Senor Network[J]. Information Security & Technology， 2014.

[6] Heinzelman W R， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences. IEEE， 2000：8020.

[7] 黃韜，楊寧，張智江，等. LEACH及其演進(jìn)路由協(xié)議分析與仿真[J].無線電通信技術(shù)， 2009， 35（1）：4-7.

[8] 張志艷.無線傳感器網(wǎng)絡(luò)LEACH路由算法研究與改進(jìn)[D].西南交通大學(xué)， 2014.