無線多跳網(wǎng)絡(luò)的局部拓撲算法

孫智博

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

無線多跳網(wǎng)絡(luò)的局部拓撲算法

孫智博

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

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

無線多跳網(wǎng)絡(luò)；拓撲算法

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻

[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 發(fā)展背景

2 算法介紹

2016-5-20

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