無線多跳網絡的局部拓撲算法

孫智博

（中南大學信息科學與工程學院 湖南長沙 410000）

無線多跳網絡的局部拓撲算法

孫智博

（中南大學信息科學與工程學院 湖南長沙 410000）

無線多跳網絡的拓撲結構對網絡性能有較大的影響。在許多情況下，無線多跳網絡中的節點往往是靠電池供電。當節點的電池能量耗盡時，節點便不能再繼續工作。拓撲控制的目標是實現稀疏性，減少能量消耗和無線接口，控制傳輸功率，并且延長網絡壽命。

無線多跳網絡；拓撲算法

中提出了一種局部的節能拓撲控制算法X-LMST，可以通過在維持節點中的能量消耗平衡，有效地實現延長網絡的生命周期。算法復雜度是O（mlogn），m代表的是鏈路數量，n代表的是距離一個節點的“單跳”的相鄰節點的數量。

文獻中做出以下假設：①網絡中的每個節點能夠自適應地調整其發射功率；②假設每個節點都配備了全方位天線；③干擾電平獨立于網絡流量，并且所有節點的干擾電平相同；④所有節點都知道其位置信息（可以通過某些定位技術或設備，例如GPS接收器），并且每個節點保持所有單跳相鄰節點的位置信息（這種位置信息可利用當網絡最初部署時，鄰域節點之間交換hello消息的方式獲得，如果節點移動，可以定期交換等hello消息）；⑤假設MAC層是理想的，這可以保證數據包總是可以不丟失。

建立圖模型 G（V，E），V（G）代表節頂點集，E（G）代表邊集。（u，v）∈E（G）表示 u，v之間直接相連。如果的、d（u，v）≤R，那么 u，v之間存在鏈路（d（u，v）代表u，v兩點之間的幾何距離，而R代表節點在網絡中的最大均勻傳輸范圍）。

用euv代表節點u成功傳送信息單元到節點v所需的最小功率，在d（u，v）≤R 的前提下，euv=d（u，v）α+c，α 和 c是常數在特定的無線系統和傳播環境中（通常2≤α≤4）。c代表著由信號處理和成功接收信息所需的最小能量所造成的開銷。當d（u，v）＞R，euv接近∞。對于給定的連接節點的路徑p，發送一個信息單元的整體功耗是鏈路中所有節點發射功率的總和。，用N（u）代表節點u的單跳相鄰節點集合，那么N（u）={v|v∈V（G），（u，v）∈E（G）}+{u}。讓 NE（u）表示 N（u）的兩個節點之間的邊的集合，那么NE（u）={（x，y）|（x，y）∈E（G）∧x，y∈N（u）}。該算法主要實現兩個目標：①減少網絡節點的傳輸功率；②延長網絡的生存時間。

X-LMST中的關鍵問題是如何確定網絡中的鏈路的能量臨界值。該文獻定義了一個新的度量值。為了判定是否是能量關鍵鏈路，需要對鏈路的兩個端點節點的能量狀態進行檢查。通常認為，如果它們其中一個具有極低的能量，不管另一個節點剩余能量多么高，應考慮該鏈路為能源關鍵鏈路。

想要描述每個節點影響一個在其單跳鄰域的鏈路是否是能量關鍵鏈路的程度，可以引入Lx表示每一個節點的能量等級，Lx=[L×Ex/Emax]。Emax表示一個節點能量總量，Ex表示一個節點的剩余能量，將Emax均勻分成L份。

對于鏈路（x，y）∈E（G），定義 ERGxy=1n（Lx×Ly）來描述鏈路能量狀態。這個新的度量具有以下突出的優點：①對稱性，ERGxy=ERGyx=；②單調遞增性，隨著Ex，Ey增加而增加；③它的一階導數單調遞減；當節點處于較低的能量水平時，自變量變化導致ERGxy的變化量比在較高的能量水平時更大，所以ERGxy可以正確反映出鏈路（x，y）的狀況。

定義的能量臨界比值K，這意味著單跳鄰域鏈路中的百分之K被認為是能量關鍵鏈路。能量臨界值ERCcu與節點u∈V（G）有關，該值表示節點u的閾值，所以，只要NE（u）中某一鏈路的ERGxy小于ERCcu，就可判定該鏈路是能量關鍵鏈路。每個節點都有自己的能量臨界值ERCcu。

算法設計思想是首先，準備節點u的單跳鄰域拓撲，并且不使用能量關鍵鏈路；保留能量關鍵鏈路集合；然后，用非能量關鍵鏈路建立最小生成樹，使用到克魯斯卡爾算法；如果先前生成的最小生成樹不包含所有節點，繼續建立最小生成樹。這個過程中，優先使用那些能量充足的鏈路；最后，生成一棵完整的最小生成樹Tu，將u點的新鄰域節點集合返回節點u。

并且對以下三種算法進行仿真，X-LMST，E-LMST，和LMST算法。參考文獻比較了以下三項：網絡的生存時間（是指網絡中的第一個節點時能量耗盡的用時）；平均傳輸半徑；平均節點度。

文獻還對比了不同算法的平均網絡生存時間，以節點密度為自變量。X-LMST算法表現最好。一般來說，三種算法的平均網絡生命周期隨節點密度的增加而增加。并且X-LMST的優勢也隨著節點密度增加而增加。這是因為，網絡節點密度的增加可以提供更多的選擇，以避免過度使用能源的關鍵鏈路。

然后，比較了不同算法的平均傳輸半徑，以節點密度為自變量。傳輸半徑定義為一個節點與其鄰域節點集合中最遠距離的節點之間的距離。平均傳輸半徑是在網絡中所有節點的傳輸半徑的總和（按不同的算法）。X-LMST具有最高的平均傳輸半徑。因為X-LMST允許保留一些長鏈接的節點，同時消除一些雖然短但是能源關鍵的鏈路，實現網絡中的能量消耗平衡。

在平均節點度與節點密度方面，比較了不同算法的性能。最終得出X-LMST在三種算法中具有最大的平均節點度。

參考文獻

[1]Shang D，Zhang B，Yao Z，et al.An energy efficient localized topology control algorithm for wireless multihop networks[J].Journal of Communications&Networks，2014，16（16）：371～377.

TN929.5

A

1004-7344（2016）17-0247-01

1 發展背景

2 算法介紹

2016-5-20

現有的拓撲控制算法主要集中在網絡節點的低傳輸功率的分配問題上，同時保持全局連通。為了使每個節點學習到整個網絡的狀態信息，現有的算法不是結合全局網絡狀態信息，就是結合局部網絡狀態信息。前者的優勢在于較低的發射功率，能更好的實現拓撲控制，并在小型網絡表現出更好的性能，但是由于獲取全局狀態信息需要生成簡化圖，搜集和存儲該類信息開銷比較大，所以在實際情況下實現比較困難；而后者的優勢在于以增加節點發射功率換取的高可伸縮性，并且，該算法允許每個節點獨立的控制其局部拓撲，通過使用其鄰域信息（在保持網絡連接的同時）。然而，所有上述算法強調太多的網絡的稀疏性，缺乏對網絡中的節點和鏈路的能量臨界狀態的考慮。