基于改進(jìn)最小生成樹的三維路由算法

崔穎，李巧玨，高山，陳立偉

哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001

無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSN）包含大量傳感器節(jié)點(diǎn)和1 個(gè)基站（sink）節(jié)點(diǎn)，傳感器節(jié)點(diǎn)分布在監(jiān)控區(qū)域中采集數(shù)據(jù)，然后將數(shù)據(jù)上傳到監(jiān)控區(qū)域邊緣的sink 節(jié)點(diǎn)，最后對數(shù)據(jù)進(jìn)行分析。這些傳感器節(jié)點(diǎn)收集、傳輸信息的過程中消耗能量，但由于它們采用電池供電，電池電量有限且不能被補(bǔ)充，所以能量的高效利用格外重要。合理的路由鏈路能夠使網(wǎng)絡(luò)能量利用率增加，延長網(wǎng)絡(luò)壽命。無線傳感器網(wǎng)絡(luò)的早期研究主要是在理想二維平面中，但許多無線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用環(huán)境是在三維（3D）空間中，例如水下環(huán)境監(jiān)測[1]、森林火災(zāi)跟蹤[2]、精準(zhǔn)農(nóng)業(yè)[3-4]等。因此，研究三維無線傳感器網(wǎng)絡(luò)的路由鏈路具有重要意義。

早期基于二維無線傳感器網(wǎng)絡(luò)的研究有很多。低功耗自適應(yīng)分簇路由協(xié)議(low energy adaptive clustering hierarchy，LEACH)[5]算法是最早的分簇算法，但簇頭單跳傳輸至基站，簇節(jié)點(diǎn)消耗能量高，網(wǎng)絡(luò)壽命降低。所以學(xué)者們提出了簇間多跳方式來減少簇頭的能耗。孫愛晶等[6]采用多元素加權(quán)的路徑評價(jià)函數(shù)，結(jié)合貓群算法求簇頭的最優(yōu)路由，減少了簇間的能量消耗，但簇內(nèi)的能量消耗沒有優(yōu)化。廖福保等[7]和戴志強(qiáng)等[8]都使用了最小生成樹方法求簇頭至基站的多跳路徑，使用了不同的多元素權(quán)重，但簇內(nèi)的單跳都沒有改進(jìn)。Jin 等[9]提出基于路徑樹的多跳路由算法，簇頭根據(jù)與基站距離從小到大順序依次成樹，形成簇間路由，也未改進(jìn)簇內(nèi)的單跳。以上算法使用智能優(yōu)化算法或最小生成樹算法對簇間多跳路由進(jìn)行了改進(jìn)，但都沒有考慮從簇內(nèi)單跳入手節(jié)約能耗。潘琢金等[10]在簇內(nèi)路由中使用了最小生成樹，這使得簇內(nèi)節(jié)點(diǎn)的路由從單跳變成多跳，路由距離減小，節(jié)點(diǎn)消耗的能量減小，延長了網(wǎng)絡(luò)壽命。但是其分簇時(shí)直接將網(wǎng)絡(luò)分成了4 塊，分簇過程中并沒考慮其他信息，可移植性差。

近年來，三維的無線傳感器網(wǎng)絡(luò)逐漸成為研究熱點(diǎn)。Somauroo 等[11]將基于鏈的路由協(xié)議（ power-efficient gathering in sensor information systems，PEGASIS）應(yīng)用到3D 環(huán)境下，并且使用遺傳算法代替了PEGASIS 中的貪婪算法進(jìn)行鏈路的構(gòu)建，同時(shí)結(jié)合了能量和距離選擇C 簇頭提高了網(wǎng)絡(luò)性能，但簇內(nèi)路由也并沒有改進(jìn)。Wang 等[12]提出了最小生成樹和邊緣相加運(yùn)算的最優(yōu)拓?fù)淇焖偕伤惴ǎ蟪鋈S最優(yōu)剛性圖，但權(quán)重僅由距離計(jì)算，沒有考慮能量因素。Xu 等[13]提出了3D 無線傳感器網(wǎng)絡(luò)下的節(jié)能路由協(xié)議，對簇內(nèi)路由進(jìn)行了改進(jìn)，減小了網(wǎng)絡(luò)能耗，但沒有考慮節(jié)點(diǎn)作為中繼次數(shù)對簇內(nèi)節(jié)點(diǎn)的影響。

基于以上問題，本文提出了基于改進(jìn)最小生成樹（improved minimum spanning tree，IMST）的三維路由協(xié)議（three dimensional routing protocol，3DRT）算法研究。

1 相關(guān)理論

1.1 網(wǎng)絡(luò)模型

對所提算法以及仿真實(shí)驗(yàn)使用的網(wǎng)絡(luò)模型做如下假設(shè)：

1）傳感器節(jié)點(diǎn)隨機(jī)部署在一個(gè)立方體區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)都有全局唯一的標(biāo)識號（identity document，ID）；

2）每個(gè)節(jié)點(diǎn)都具有相同的通信和處理能力；

3）每個(gè)節(jié)點(diǎn)都可獨(dú)立地與基站通信，基站的位置已知且基站能量不受限；

4）所有節(jié)點(diǎn)部署后節(jié)點(diǎn)位置不改變，電池電量有限且無法充電；

5）節(jié)點(diǎn)可以根據(jù)信號強(qiáng)度得到自身的相對位置。

1.2 能量模型

網(wǎng)絡(luò)相互間的通信采用自由空間無線通信能耗模型[5]，是根據(jù)節(jié)點(diǎn)間的歐氏距離d計(jì)算。能耗計(jì)算公式如下：

節(jié)點(diǎn)發(fā)送kbit 數(shù)據(jù)消耗的能量為

接收和融合kbit 數(shù)據(jù)消耗的能量分別為

式中Eda為融合1 bit 數(shù)據(jù)所消耗的能量。

1.3 K-means++算法

K-means++算法是對K-means 算法的改進(jìn)，初始聚類中心不再是隨機(jī)確定，而是選擇距離上一個(gè)聚類中心更遠(yuǎn)的點(diǎn)作為下一個(gè)聚類中心。選出初始中心后，繼續(xù)使用標(biāo)準(zhǔn)K-means 聚類。改進(jìn)算法能夠選出均勻的簇頭，均衡網(wǎng)絡(luò)能量。Kmeans++選取初始聚類中心的步驟如下：

1）隨機(jī)確定第一個(gè)聚類中心；

2）更新每一個(gè)樣本到已有聚類中心的最小距離；

3）根據(jù)距離大小確定每個(gè)樣本成為下一個(gè)聚類中心的概率；

4）根據(jù)概率大小抽取下一個(gè)聚類中心；

5）重復(fù)步驟2）～4），直到選出K個(gè)聚類中心。

1.4 最小生成樹算法

圖1是具有N個(gè)頂點(diǎn)的帶權(quán)連通圖G，其中存在很多子圖。如果某個(gè)子圖中的任意2 個(gè)頂點(diǎn)既互相連通，又是樹結(jié)構(gòu)，那么子圖G'叫做生成樹。如果G'的各邊權(quán)值之和最小，則G'為圖G的最小生成樹，如圖1 中虛線即為G的最小生成樹。

圖1 帶權(quán)連通圖

最小生成樹有2 種查找算法，分別為克魯斯卡爾(Kruskal)算法和普利姆(Prim)算法，二者均為貪心算法。不同的是，Kruskal 算法對每個(gè)邊按照權(quán)重大小進(jìn)行排序，Prim 算法則是對節(jié)點(diǎn)進(jìn)行操作。由于本文是尋找節(jié)點(diǎn)間的最優(yōu)路由，所以采用Prim 算法。

Prim 算法步驟是隨機(jī)從一個(gè)節(jié)點(diǎn)開始，找到這個(gè)節(jié)點(diǎn)相鄰權(quán)重最小的邊；將此邊添加到這個(gè)節(jié)點(diǎn)上，形成一個(gè)集合；再從集合的節(jié)點(diǎn)中查找相鄰權(quán)重最小的邊，并添加到集合中；不斷重復(fù)直到所有節(jié)點(diǎn)都在集合中。圖1 中的具體步驟即為從b點(diǎn)開始，權(quán)重最小邊為b-a，a的權(quán)重最小邊為a-e，以此類推最后得到的最小生成樹為b-ae-f-d-g-c。

1.5 CRITIC 算法

CRITIC (criteria importance though intercrieria correlation)是Diakoulaki 等[14]提出的一種客觀權(quán)重賦權(quán)法，以對比強(qiáng)度和沖突性為基礎(chǔ)確定指標(biāo)的權(quán)重系數(shù)。對比強(qiáng)度表示同一指標(biāo)在各個(gè)評價(jià)方案中的取值差距，以標(biāo)準(zhǔn)差的形式表現(xiàn)；沖突性是以指標(biāo)之間的相關(guān)性為基礎(chǔ)，如果2 個(gè)指標(biāo)之間正相關(guān)強(qiáng)，則2 個(gè)指標(biāo)沖突性低。計(jì)算權(quán)重時(shí)，對比強(qiáng)度與沖突性相乘后進(jìn)行歸一化處理，即可得到最終的權(quán)重。

2 基于改進(jìn)最小生成樹的三維路由協(xié)議

本文算法首先使用K-means++算法選擇簇頭，然后使用改進(jìn)的最小生成樹算法求出簇間和簇內(nèi)的最優(yōu)路由，最后進(jìn)行數(shù)據(jù)傳輸。系統(tǒng)框圖如圖2 所示。

圖2 基于改進(jìn)最小生成樹的三維路由協(xié)議系統(tǒng)框圖

2.1 K-means++選舉簇頭

簇頭既要接收、融合簇節(jié)點(diǎn)轉(zhuǎn)發(fā)的信息，又要將信息傳輸出去，能量消耗大，所以引入Kmeans++算法，均衡選舉簇頭。利用其聚類中心相對距離遠(yuǎn)的特性，選出無線傳感器網(wǎng)絡(luò)中均勻分布的簇頭，避免產(chǎn)生能量空洞。本文的初始簇頭數(shù)是根據(jù)文獻(xiàn)[15]中最優(yōu)簇頭數(shù)計(jì)算公式計(jì)算得到的，計(jì)算后的初始簇頭數(shù)為10，且簇頭數(shù)隨著節(jié)點(diǎn)的死亡等比例減小。K-means++選舉簇頭具體步驟如下:

1）隨機(jī)確定第一個(gè)簇頭；

2）更新其他節(jié)點(diǎn)到已有簇頭的最小距離；

3）根據(jù)距離大小確定每個(gè)節(jié)點(diǎn)成為下一個(gè)簇頭的概率；

4）根據(jù)概率大小選擇下一個(gè)簇頭；

5）重復(fù)步驟2）～4），直至選出K個(gè)簇頭；

6）計(jì)算每個(gè)節(jié)點(diǎn)到簇頭的距離，并將其分到距離最小的簇頭所在的簇中；

7）重新計(jì)算每個(gè)簇的中心（即屬于該簇所有節(jié)點(diǎn)的位置的質(zhì)心）；

8）將簇中心映射到距離最近的節(jié)點(diǎn)上，這些節(jié)點(diǎn)是此次迭代選出的簇頭；

9）重復(fù)步驟6）～8），直至達(dá)到某個(gè)終止條件（迭代次數(shù)或最小誤差變化），輸出簇頭。

2.2 基于優(yōu)化最小生成樹的三維路由協(xié)議

簇頭選舉完成后，對簇內(nèi)及簇間使用優(yōu)化的最小生成樹路由協(xié)議。首先對簇頭與簇內(nèi)節(jié)點(diǎn)生成簇內(nèi)路由樹，然后對簇頭與基站生成簇間路由樹，最后進(jìn)行數(shù)據(jù)傳輸。

2.2.1 簇間自適應(yīng)單跳多跳

圖3是基于最小生成樹的路由示意，可以看出，節(jié)點(diǎn)e是經(jīng)由簇頭2 多跳至基站，然而根據(jù)式(1)、式(2)和sink 節(jié)點(diǎn)能量不受限的條件，能夠看出單跳e-sink 的能耗小，所以最優(yōu)路由應(yīng)該是單跳而非多跳。由此對節(jié)點(diǎn)的能量傳遞消耗進(jìn)行以下分析，找到最優(yōu)路由的普遍結(jié)論。

圖3 最小生成樹路由示意

單跳情況時(shí)，節(jié)點(diǎn)傳輸能量消耗如式(1)，即節(jié)點(diǎn)e單跳至sink 的能量消耗為ETX，網(wǎng)絡(luò)消耗能量也為ETX；當(dāng)采用最小生成樹多跳時(shí)，節(jié)點(diǎn)e多跳到sink，則節(jié)點(diǎn)e的能耗表示為

式中de,cluster2是節(jié)點(diǎn)e與簇頭2 距離。簇頭2 作為中繼的消耗為

所以網(wǎng)絡(luò)能量消耗為

距離公式為

式中de,sink是節(jié)點(diǎn)e與基站距離。由以上分析可知，滿足ETX＜Eall即式(3)中的距離公式時(shí)，采用單跳傳輸。 但能量消耗是非確定多項(xiàng)式（nondeterministic polynominal，NP）難問題，幾個(gè)節(jié)點(diǎn)間的分析并不能代表能量的總消耗，所以此處采用枚舉法，取不同de,sink的值對網(wǎng)絡(luò)分析，運(yùn)行程序后得出的結(jié)果如表1。 可以看出， 當(dāng)de,sink=20 時(shí)，第一個(gè)死亡節(jié)點(diǎn)輪數(shù)最大，所以當(dāng)節(jié)點(diǎn)距基站距離小于等于20 m 時(shí)，節(jié)點(diǎn)單跳至基站。所以圖3 中節(jié)點(diǎn)a、d、e均單跳至基站。

表1 單跳至基站距離與第一個(gè)死亡節(jié)點(diǎn)輪數(shù)

2.2.2 新權(quán)重與權(quán)重系數(shù)的計(jì)算

文獻(xiàn)[10]使用的最小生成樹算法的權(quán)重只考慮距離這一因素，但無線傳感器網(wǎng)絡(luò)中影響壽命的元素很多。由上節(jié)分析可知，作為中繼的節(jié)點(diǎn)能耗高，因此本文在舊權(quán)重的基礎(chǔ)上，加入能量與跳數(shù)，求出最優(yōu)路由，減少能量消耗。新權(quán)重表達(dá)式為

式中：wi是節(jié)點(diǎn)i的總權(quán)重，wenergy,i、wdist,i、wneighbor,i分別為節(jié)點(diǎn)i的能量權(quán)重、距離權(quán)重和跳數(shù)權(quán)重，r1、r2、r3分別是能量權(quán)重、距離權(quán)重和跳數(shù)權(quán)重的權(quán)重系數(shù)。

式中：D為N×N維矩陣，代表兩兩節(jié)點(diǎn)間的距離，N為節(jié)點(diǎn)個(gè)數(shù)；e，n為1×N維矩陣，分別代表節(jié)點(diǎn)的能量、節(jié)點(diǎn)作為中繼的次數(shù)；dij為節(jié)點(diǎn)i與節(jié)點(diǎn)j歐式距離，ei、ni分別為節(jié)點(diǎn)i的能量、節(jié)點(diǎn)i為中繼的次數(shù)；max、min 分別為求最大最小值的函數(shù)。

2.2.3 CRITIC 計(jì)算權(quán)重系數(shù)

初始時(shí)由于能量差值小，所以賦值權(quán)重系數(shù)為等值，即1/3。但隨著網(wǎng)絡(luò)運(yùn)行，節(jié)點(diǎn)的剩余能量減小，能量差值變大，其權(quán)重系數(shù)應(yīng)該增大。為了調(diào)整權(quán)重系數(shù)，在一定輪次后重新計(jì)算權(quán)重系數(shù)，本文每100 輪后對權(quán)重系數(shù)重新判斷。重新判斷的依據(jù)為

式中：Em為前m輪消耗的總能量，m為經(jīng)過的輪數(shù)，Er為當(dāng)前第r輪消耗的能量。如果當(dāng)前能量消耗大于之前的平均消耗，就將該輪的能量、距離和跳數(shù)作為CRITIC 的輸入，重新計(jì)算權(quán)重系數(shù)。首先將能量、距離和跳數(shù)的數(shù)據(jù)標(biāo)準(zhǔn)化，其中能量是正向指標(biāo)，距離和跳數(shù)是負(fù)向指標(biāo)；然后計(jì)算對比性和矛盾性得到信息承載量，其中對比性由標(biāo)準(zhǔn)差表示，矛盾性用皮爾遜相關(guān)系數(shù)表示；最后由信息承載量歸一化求出權(quán)重，回代式(4)得到權(quán)重公式。

2.3 算法復(fù)雜度分析

假設(shè)初始化階段網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，簇頭數(shù)為k，算法復(fù)雜度分別從簇頭選舉和路由選擇2 個(gè)階段進(jìn)行分析。在簇頭選舉階段，Kmeans++算法迭代次數(shù)為M，節(jié)點(diǎn)數(shù)為N，簇頭數(shù)為k，復(fù)雜度為O(MNk)，化簡后為O(MN)；在路由選擇階段，節(jié)點(diǎn)數(shù)為N，簇頭數(shù)為k，簇間多跳復(fù)雜度為O(k2)，簇內(nèi)多跳復(fù)雜度為O((N-k)2)，因此該階段復(fù)雜度為O(N2+2Nk)，化簡后為O(N2)。因此，每輪的復(fù)雜度為O(N2+NM)，等于O(N2)，復(fù)雜度等同于算法執(zhí)行所需要的基本運(yùn)算次數(shù)，即所提算法每輪可以在O(N2)次的運(yùn)算中得到結(jié)果，算法可行。

3 仿真分析

利用表2 中的仿真參數(shù)對提出算法進(jìn)行Python 仿真以評估其性能，并在相同三維環(huán)境下對LEACH[5]、基于最小生成樹的非均勻分簇路由協(xié)議(mst2017)[7]以及基于K-means 聚類的無線傳感器網(wǎng)絡(luò)WSN 能耗均衡路由算法KBECRA[16]進(jìn)行仿真對比。

表2 仿真參數(shù)

3.1 網(wǎng)絡(luò)壽命分析

圖4是在相同三維環(huán)境下不同算法網(wǎng)絡(luò)中存活節(jié)點(diǎn)隨輪數(shù)變化的對比，網(wǎng)絡(luò)壽命可以用第一個(gè)死亡節(jié)點(diǎn)輪數(shù)代表。表3 給出了具體的死亡節(jié)點(diǎn)輪數(shù)，其中RFND為第一個(gè)節(jié)點(diǎn)死亡的輪數(shù)，RHND為一半節(jié)點(diǎn)死亡的輪數(shù)，RAND為所有節(jié)點(diǎn)死亡的輪數(shù)。

表3 不同算法網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)死亡輪數(shù)

圖4 不同算法網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)對比

由表3 可以得到，IMST_3DRT 的RFND分別比3D-mst2017、 3D-KBECRA、 3D-LEACH 提高了12.5%、7.0%和30.6%，RHND分別提高了15.0%、27.9%和31.9%，RAND分別提高了52.4%、70.8%和41.6%。因?yàn)镮MST_3DRT 采用簇內(nèi)多跳，其簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)木嚯x減小、能耗也減小。而且多跳路由時(shí)，父節(jié)點(diǎn)接收子節(jié)點(diǎn)的消息，代替簇內(nèi)單跳時(shí)簇頭接收簇內(nèi)所有節(jié)點(diǎn)消息的情況，均衡了簇內(nèi)節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命。

3.2 能量消耗分析

圖5是網(wǎng)絡(luò)的剩余能量隨輪數(shù)變化對比，與3D-mst2017、3D-KBECRA、3D-LEACH 這3 種算法比較，IMST_3DRT 的剩余能量依次提高了22.1%、31.5%和38.9%。因?yàn)樗崴惴ù貎?nèi)多跳時(shí)，下一跳節(jié)點(diǎn)由能量、距離和跳數(shù)的加權(quán)和決定，當(dāng)能量消耗變大時(shí)，權(quán)重系數(shù)根據(jù)當(dāng)前參數(shù)重新計(jì)算，所以網(wǎng)絡(luò)的利用率增加，減少了能量消耗，延長了網(wǎng)絡(luò)壽命。

圖5 不同算法網(wǎng)絡(luò)剩余能量對比

3.3 吞吐量分析

吞吐量是直到最后一個(gè)節(jié)點(diǎn)死亡時(shí)網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量總和。圖6 是3 個(gè)場景下吞吐量的對比，3 個(gè)場景的節(jié)點(diǎn)數(shù)都為100，仿真范圍依次是邊長為70、100、125 m 的三維立方體。可以看出，3 個(gè)場景下吞吐量的變化趨勢相同，IMST_3DRT＞3D-mst2017＞ 3D-KBECRA＞3D-LEACH。因?yàn)殡S著網(wǎng)絡(luò)壽命增長，傳輸?shù)臄?shù)據(jù)量也增加，所以其趨勢與壽命長度呈正相關(guān)。因而可以得出結(jié)論，改進(jìn)的最小生成樹路由效果大于簇內(nèi)單跳。

圖6 不同場景吞吐量對比

3.4 時(shí)延分析

傳播時(shí)延由信道長度除以電磁波在信道上的傳播速率得到。圖7 是3 個(gè)場景下時(shí)延的對比圖，場景與3.3 節(jié)相同。由圖7 可以看出3 個(gè)場景下IMST_3DRT 的時(shí)延最小。在場景1 下，其他3 種方法時(shí)延大致相同；在場景2、3 下的時(shí)延：3D-KBECRA≥3D-LEACH＞3D-mst2017。 因 為IMST_3DRT 簇內(nèi)使用改進(jìn)最小生成樹的生成路由，簇內(nèi)節(jié)點(diǎn)的傳輸距離減小，時(shí)延也減小，而3D-mst2017 是基于最小生成樹的簇間多跳，因此小于簇間單跳的3D-KBECRA 和3D-LEACH。

圖7 不同場景時(shí)延對比

4 結(jié)束語

目前，三維的無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用于實(shí)際環(huán)境，本文針對簇內(nèi)節(jié)點(diǎn)單跳能耗大的問題，提出了基于改進(jìn)最小生成樹的路由協(xié)議，該算法能夠減少簇內(nèi)節(jié)點(diǎn)能耗，延長網(wǎng)絡(luò)壽命。該算法使用K-means++算法選舉簇頭，保證簇頭均衡分布。數(shù)據(jù)傳輸時(shí)，簇間路由將近基站節(jié)點(diǎn)單跳至基站，減少了中繼節(jié)點(diǎn)的能耗，簇內(nèi)使用改進(jìn)的最小生成樹路由協(xié)議，減小了簇內(nèi)節(jié)點(diǎn)的傳輸能耗。計(jì)算權(quán)重時(shí)引入了能量和跳數(shù)，系數(shù)采用CRITIC 算法，利用各個(gè)要素之間的相對關(guān)系求出更合適的權(quán)重系數(shù)，選舉更均衡的下一跳。仿真分析結(jié)果表明，相較于其他比較算法，本文所提算法能夠減少能耗，延長網(wǎng)絡(luò)生命周期。

本文研究發(fā)現(xiàn)，距離近的節(jié)點(diǎn)會產(chǎn)生大量重疊信息，增加網(wǎng)絡(luò)能耗，在以后的工作中，可以加入調(diào)度算法進(jìn)行研究。