基于改進最小生成樹的三維路由算法

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

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

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

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

近年來，三維的無線傳感器網絡逐漸成為研究熱點。Somauroo 等[11]將基于鏈的路由協議（ power-efficient gathering in sensor information systems，PEGASIS）應用到3D 環境下，并且使用遺傳算法代替了PEGASIS 中的貪婪算法進行鏈路的構建，同時結合了能量和距離選擇C 簇頭提高了網絡性能，但簇內路由也并沒有改進。Wang 等[12]提出了最小生成樹和邊緣相加運算的最優拓撲快速生成算法，求出三維最優剛性圖，但權重僅由距離計算，沒有考慮能量因素。Xu 等[13]提出了3D 無線傳感器網絡下的節能路由協議，對簇內路由進行了改進，減小了網絡能耗，但沒有考慮節點作為中繼次數對簇內節點的影響。

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

1 相關理論

1.1 網絡模型

對所提算法以及仿真實驗使用的網絡模型做如下假設：

1）傳感器節點隨機部署在一個立方體區域內，每個節點都有全局唯一的標識號（identity document，ID）；

2）每個節點都具有相同的通信和處理能力；

3）每個節點都可獨立地與基站通信，基站的位置已知且基站能量不受限；

4）所有節點部署后節點位置不改變，電池電量有限且無法充電；

5）節點可以根據信號強度得到自身的相對位置。

1.2 能量模型

網絡相互間的通信采用自由空間無線通信能耗模型[5]，是根據節點間的歐氏距離d計算。能耗計算公式如下：

節點發送kbit 數據消耗的能量為

接收和融合kbit 數據消耗的能量分別為

式中Eda為融合1 bit 數據所消耗的能量。

1.3 K-means++算法

K-means++算法是對K-means 算法的改進，初始聚類中心不再是隨機確定，而是選擇距離上一個聚類中心更遠的點作為下一個聚類中心。選出初始中心后，繼續使用標準K-means 聚類。改進算法能夠選出均勻的簇頭，均衡網絡能量。Kmeans++選取初始聚類中心的步驟如下：

1）隨機確定第一個聚類中心；

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

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

4）根據概率大小抽取下一個聚類中心；

5）重復步驟2）～4），直到選出K個聚類中心。

1.4 最小生成樹算法

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

圖1 帶權連通圖

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

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

1.5 CRITIC 算法

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

2 基于改進最小生成樹的三維路由協議

本文算法首先使用K-means++算法選擇簇頭，然后使用改進的最小生成樹算法求出簇間和簇內的最優路由，最后進行數據傳輸。系統框圖如圖2 所示。

圖2 基于改進最小生成樹的三維路由協議系統框圖

2.1 K-means++選舉簇頭

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

1）隨機確定第一個簇頭；

2）更新其他節點到已有簇頭的最小距離；

3）根據距離大小確定每個節點成為下一個簇頭的概率；

4）根據概率大小選擇下一個簇頭；

5）重復步驟2）～4），直至選出K個簇頭；

6）計算每個節點到簇頭的距離，并將其分到距離最小的簇頭所在的簇中；

7）重新計算每個簇的中心（即屬于該簇所有節點的位置的質心）；

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

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

2.2 基于優化最小生成樹的三維路由協議

簇頭選舉完成后，對簇內及簇間使用優化的最小生成樹路由協議。首先對簇頭與簇內節點生成簇內路由樹，然后對簇頭與基站生成簇間路由樹，最后進行數據傳輸。

2.2.1 簇間自適應單跳多跳

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

圖3 最小生成樹路由示意

單跳情況時，節點傳輸能量消耗如式(1)，即節點e單跳至sink 的能量消耗為ETX，網絡消耗能量也為ETX；當采用最小生成樹多跳時，節點e多跳到sink，則節點e的能耗表示為

式中de,cluster2是節點e與簇頭2 距離。簇頭2 作為中繼的消耗為

所以網絡能量消耗為

距離公式為

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

表1 單跳至基站距離與第一個死亡節點輪數

2.2.2 新權重與權重系數的計算

文獻[10]使用的最小生成樹算法的權重只考慮距離這一因素，但無線傳感器網絡中影響壽命的元素很多。由上節分析可知，作為中繼的節點能耗高，因此本文在舊權重的基礎上，加入能量與跳數，求出最優路由，減少能量消耗。新權重表達式為

式中：wi是節點i的總權重，wenergy,i、wdist,i、wneighbor,i分別為節點i的能量權重、距離權重和跳數權重，r1、r2、r3分別是能量權重、距離權重和跳數權重的權重系數。

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

2.2.3 CRITIC 計算權重系數

初始時由于能量差值小，所以賦值權重系數為等值，即1/3。但隨著網絡運行，節點的剩余能量減小，能量差值變大，其權重系數應該增大。為了調整權重系數，在一定輪次后重新計算權重系數，本文每100 輪后對權重系數重新判斷。重新判斷的依據為

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

2.3 算法復雜度分析

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

3 仿真分析

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

表2 仿真參數

3.1 網絡壽命分析

圖4是在相同三維環境下不同算法網絡中存活節點隨輪數變化的對比，網絡壽命可以用第一個死亡節點輪數代表。表3 給出了具體的死亡節點輪數，其中RFND為第一個節點死亡的輪數，RHND為一半節點死亡的輪數，RAND為所有節點死亡的輪數。

表3 不同算法網絡中傳感器節點死亡輪數

圖4 不同算法網絡中存活節點數對比

由表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%。因為IMST_3DRT 采用簇內多跳，其簇內節點數據傳輸的距離減小、能耗也減小。而且多跳路由時，父節點接收子節點的消息，代替簇內單跳時簇頭接收簇內所有節點消息的情況，均衡了簇內節點能耗，延長了網絡壽命。

3.2 能量消耗分析

圖5是網絡的剩余能量隨輪數變化對比，與3D-mst2017、3D-KBECRA、3D-LEACH 這3 種算法比較，IMST_3DRT 的剩余能量依次提高了22.1%、31.5%和38.9%。因為所提算法簇內多跳時，下一跳節點由能量、距離和跳數的加權和決定，當能量消耗變大時，權重系數根據當前參數重新計算，所以網絡的利用率增加，減少了能量消耗，延長了網絡壽命。

圖5 不同算法網絡剩余能量對比

3.3 吞吐量分析

吞吐量是直到最后一個節點死亡時網絡傳輸的數據量總和。圖6 是3 個場景下吞吐量的對比，3 個場景的節點數都為100，仿真范圍依次是邊長為70、100、125 m 的三維立方體?？梢钥闯?，3 個場景下吞吐量的變化趨勢相同，IMST_3DRT＞3D-mst2017＞ 3D-KBECRA＞3D-LEACH。因為隨著網絡壽命增長，傳輸的數據量也增加，所以其趨勢與壽命長度呈正相關。因而可以得出結論，改進的最小生成樹路由效果大于簇內單跳。

圖6 不同場景吞吐量對比

3.4 時延分析

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

圖7 不同場景時延對比

4 結束語

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

本文研究發現，距離近的節點會產生大量重疊信息，增加網絡能耗，在以后的工作中，可以加入調度算法進行研究。