無線多跳網(wǎng)絡(luò)的局部拓?fù)渌惴?/h1>
2016-07-12 09:02:35孫智博
大科技 2016年17期
孫智博
（中南大學(xué)信息科學(xué)與工程學(xué)院 湖南長沙 410000）
無線多跳網(wǎng)絡(luò)的局部拓?fù)渌惴?/p>
孫智博
（中南大學(xué)信息科學(xué)與工程學(xué)院 湖南長沙 410000）
無線多跳網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)性能有較大的影響。在許多情況下，無線多跳網(wǎng)絡(luò)中的節(jié)點(diǎn)往往是靠電池供電。當(dāng)節(jié)點(diǎn)的電池能量耗盡時，節(jié)點(diǎn)便不能再繼續(xù)工作。拓?fù)淇刂频哪繕?biāo)是實(shí)現(xiàn)稀疏性，減少能量消耗和無線接口，控制傳輸功率，并且延長網(wǎng)絡(luò)壽命。
無線多跳網(wǎng)絡(luò)；拓?fù)渌惴?/p>
中提出了一種局部的節(jié)能拓?fù)淇刂扑惴╔-LMST，可以通過在維持節(jié)點(diǎn)中的能量消耗平衡，有效地實(shí)現(xiàn)延長網(wǎng)絡(luò)的生命周期。算法復(fù)雜度是O（mlogn），m代表的是鏈路數(shù)量，n代表的是距離一個節(jié)點(diǎn)的“單跳”的相鄰節(jié)點(diǎn)的數(shù)量。
文獻(xiàn)中做出以下假設(shè)：①網(wǎng)絡(luò)中的每個節(jié)點(diǎn)能夠自適應(yīng)地調(diào)整其發(fā)射功率；②假設(shè)每個節(jié)點(diǎn)都配備了全方位天線；③干擾電平獨(dú)立于網(wǎng)絡(luò)流量，并且所有節(jié)點(diǎn)的干擾電平相同；④所有節(jié)點(diǎn)都知道其位置信息（可以通過某些定位技術(shù)或設(shè)備，例如GPS接收器），并且每個節(jié)點(diǎn)保持所有單跳相鄰節(jié)點(diǎn)的位置信息（這種位置信息可利用當(dāng)網(wǎng)絡(luò)最初部署時，鄰域節(jié)點(diǎn)之間交換hello消息的方式獲得，如果節(jié)點(diǎn)移動，可以定期交換等hello消息）；⑤假設(shè)MAC層是理想的，這可以保證數(shù)據(jù)包總是可以不丟失。
建立圖模型 G（V，E），V（G）代表節(jié)頂點(diǎn)集，E（G）代表邊集。（u，v）∈E（G）表示 u，v之間直接相連。如果的、d（u，v）≤R，那么 u，v之間存在鏈路（d（u，v）代表u，v兩點(diǎn)之間的幾何距離，而R代表節(jié)點(diǎn)在網(wǎng)絡(luò)中的最大均勻傳輸范圍）。
用euv代表節(jié)點(diǎn)u成功傳送信息單元到節(jié)點(diǎn)v所需的最小功率，在d（u，v）≤R 的前提下，euv=d（u，v）α+c，α 和 c是常數(shù)在特定的無線系統(tǒng)和傳播環(huán)境中（通常2≤α≤4）。c代表著由信號處理和成功接收信息所需的最小能量所造成的開銷。當(dāng)d（u，v）＞R，euv接近∞。對于給定的連接節(jié)點(diǎn)的路徑p，發(fā)送一個信息單元的整體功耗是鏈路中所有節(jié)點(diǎn)發(fā)射功率的總和。，用N（u）代表節(jié)點(diǎn)u的單跳相鄰節(jié)點(diǎn)集合，那么N（u）={v|v∈V（G），（u，v）∈E（G）}+{u}。讓 NE（u）表示 N（u）的兩個節(jié)點(diǎn)之間的邊的集合，那么NE（u）={（x，y）|（x，y）∈E（G）∧x，y∈N（u）}。該算法主要實(shí)現(xiàn)兩個目標(biāo)：①減少網(wǎng)絡(luò)節(jié)點(diǎn)的傳輸功率；②延長網(wǎng)絡(luò)的生存時間。
X-LMST中的關(guān)鍵問題是如何確定網(wǎng)絡(luò)中的鏈路的能量臨界值。該文獻(xiàn)定義了一個新的度量值。為了判定是否是能量關(guān)鍵鏈路，需要對鏈路的兩個端點(diǎn)節(jié)點(diǎn)的能量狀態(tài)進(jìn)行檢查。通常認(rèn)為，如果它們其中一個具有極低的能量，不管另一個節(jié)點(diǎn)剩余能量多么高，應(yīng)考慮該鏈路為能源關(guān)鍵鏈路。
想要描述每個節(jié)點(diǎn)影響一個在其單跳鄰域的鏈路是否是能量關(guān)鍵鏈路的程度，可以引入Lx表示每一個節(jié)點(diǎn)的能量等級，Lx=[L×Ex/Emax]。Emax表示一個節(jié)點(diǎn)能量總量，Ex表示一個節(jié)點(diǎn)的剩余能量，將Emax均勻分成L份。
對于鏈路（x，y）∈E（G），定義 ERGxy=1n（Lx×Ly）來描述鏈路能量狀態(tài)。這個新的度量具有以下突出的優(yōu)點(diǎn)：①對稱性，ERGxy=ERGyx=；②單調(diào)遞增性，隨著Ex，Ey增加而增加；③它的一階導(dǎo)數(shù)單調(diào)遞減；當(dāng)節(jié)點(diǎn)處于較低的能量水平時，自變量變化導(dǎo)致ERGxy的變化量比在較高的能量水平時更大，所以ERGxy可以正確反映出鏈路（x，y）的狀況。
定義的能量臨界比值K，這意味著單跳鄰域鏈路中的百分之K被認(rèn)為是能量關(guān)鍵鏈路。能量臨界值ERCcu與節(jié)點(diǎn)u∈V（G）有關(guān)，該值表示節(jié)點(diǎn)u的閾值，所以，只要NE（u）中某一鏈路的ERGxy小于ERCcu，就可判定該鏈路是能量關(guān)鍵鏈路。每個節(jié)點(diǎn)都有自己的能量臨界值ERCcu。
算法設(shè)計(jì)思想是首先，準(zhǔn)備節(jié)點(diǎn)u的單跳鄰域拓?fù)?，并且不使用能量關(guān)鍵鏈路；保留能量關(guān)鍵鏈路集合；然后，用非能量關(guān)鍵鏈路建立最小生成樹，使用到克魯斯卡爾算法；如果先前生成的最小生成樹不包含所有節(jié)點(diǎn)，繼續(xù)建立最小生成樹。這個過程中，優(yōu)先使用那些能量充足的鏈路；最后，生成一棵完整的最小生成樹Tu，將u點(diǎn)的新鄰域節(jié)點(diǎn)集合返回節(jié)點(diǎn)u。
并且對以下三種算法進(jìn)行仿真，X-LMST，E-LMST，和LMST算法。參考文獻(xiàn)比較了以下三項(xiàng)：網(wǎng)絡(luò)的生存時間（是指網(wǎng)絡(luò)中的第一個節(jié)點(diǎn)時能量耗盡的用時）；平均傳輸半徑；平均節(jié)點(diǎn)度。
文獻(xiàn)還對比了不同算法的平均網(wǎng)絡(luò)生存時間，以節(jié)點(diǎn)密度為自變量。X-LMST算法表現(xiàn)最好。一般來說，三種算法的平均網(wǎng)絡(luò)生命周期隨節(jié)點(diǎn)密度的增加而增加。并且X-LMST的優(yōu)勢也隨著節(jié)點(diǎn)密度增加而增加。這是因?yàn)?，網(wǎng)絡(luò)節(jié)點(diǎn)密度的增加可以提供更多的選擇，以避免過度使用能源的關(guān)鍵鏈路。
然后，比較了不同算法的平均傳輸半徑，以節(jié)點(diǎn)密度為自變量。傳輸半徑定義為一個節(jié)點(diǎn)與其鄰域節(jié)點(diǎn)集合中最遠(yuǎn)距離的節(jié)點(diǎn)之間的距離。平均傳輸半徑是在網(wǎng)絡(luò)中所有節(jié)點(diǎn)的傳輸半徑的總和（按不同的算法）。X-LMST具有最高的平均傳輸半徑。因?yàn)閄-LMST允許保留一些長鏈接的節(jié)點(diǎn)，同時消除一些雖然短但是能源關(guān)鍵的鏈路，實(shí)現(xiàn)網(wǎng)絡(luò)中的能量消耗平衡。
在平均節(jié)點(diǎn)度與節(jié)點(diǎn)密度方面，比較了不同算法的性能。最終得出X-LMST在三種算法中具有最大的平均節(jié)點(diǎn)度。
參考文獻(xiàn)
[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)有的拓?fù)淇刂扑惴ㄖ饕性诰W(wǎng)絡(luò)節(jié)點(diǎn)的低傳輸功率的分配問題上，同時保持全局連通。為了使每個節(jié)點(diǎn)學(xué)習(xí)到整個網(wǎng)絡(luò)的狀態(tài)信息，現(xiàn)有的算法不是結(jié)合全局網(wǎng)絡(luò)狀態(tài)信息，就是結(jié)合局部網(wǎng)絡(luò)狀態(tài)信息。前者的優(yōu)勢在于較低的發(fā)射功率，能更好的實(shí)現(xiàn)拓?fù)淇刂?，并在小型網(wǎng)絡(luò)表現(xiàn)出更好的性能，但是由于獲取全局狀態(tài)信息需要生成簡化圖，搜集和存儲該類信息開銷比較大，所以在實(shí)際情況下實(shí)現(xiàn)比較困難；而后者的優(yōu)勢在于以增加節(jié)點(diǎn)發(fā)射功率換取的高可伸縮性，并且，該算法允許每個節(jié)點(diǎn)獨(dú)立的控制其局部拓?fù)?，通過使用其鄰域信息（在保持網(wǎng)絡(luò)連接的同時）。然而，所有上述算法強(qiáng)調(diào)太多的網(wǎng)絡(luò)的稀疏性，缺乏對網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路的能量臨界狀態(tài)的考慮。
猜你喜歡
家紡“全鏈路”升級紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10 天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)移動通信(2021年5期)2021-10-25 11:41:48 高考考好是關(guān)鍵中學(xué)生數(shù)理化(高中版.高考理化)(2021年6期)2021-07-28 06:21:04 稀疏圖平方圖的染色數(shù)上界吉林大學(xué)學(xué)報(理學(xué)版)(2020年3期)2020-05-29 06:32:16 基于鄰域競賽的多目標(biāo)優(yōu)化算法自動化學(xué)報(2018年7期)2018-08-20 02:59:04 關(guān)于-型鄰域空間周口師范學(xué)院學(xué)報(2016年5期)2016-10-17 06:36:47 基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用中國交通信息化(2014年3期)2014-06-05 03:07:09 獲勝關(guān)鍵NBA特刊(2014年7期)2014-04-29 00:44:03 基于時序擴(kuò)展的鄰域保持嵌入算法及其在故障檢測中的應(yīng)用華東理工大學(xué)學(xué)報(自然科學(xué)版)(2014年2期)2014-02-27 13:48:48 高速光纖鏈路通信HSSL的設(shè)計(jì)與實(shí)現(xiàn)自動化與儀表(2014年10期)2014-02-26 08:21:17
孫智博
（中南大學(xué)信息科學(xué)與工程學(xué)院 湖南長沙 410000）
無線多跳網(wǎng)絡(luò)的局部拓?fù)渌惴?/p>
孫智博
（中南大學(xué)信息科學(xué)與工程學(xué)院 湖南長沙 410000）
無線多跳網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)性能有較大的影響。在許多情況下，無線多跳網(wǎng)絡(luò)中的節(jié)點(diǎn)往往是靠電池供電。當(dāng)節(jié)點(diǎn)的電池能量耗盡時，節(jié)點(diǎn)便不能再繼續(xù)工作。拓?fù)淇刂频哪繕?biāo)是實(shí)現(xiàn)稀疏性，減少能量消耗和無線接口，控制傳輸功率，并且延長網(wǎng)絡(luò)壽命。
無線多跳網(wǎng)絡(luò)；拓?fù)渌惴?/p>
中提出了一種局部的節(jié)能拓?fù)淇刂扑惴╔-LMST，可以通過在維持節(jié)點(diǎn)中的能量消耗平衡，有效地實(shí)現(xiàn)延長網(wǎng)絡(luò)的生命周期。算法復(fù)雜度是O（mlogn），m代表的是鏈路數(shù)量，n代表的是距離一個節(jié)點(diǎn)的“單跳”的相鄰節(jié)點(diǎn)的數(shù)量。
文獻(xiàn)中做出以下假設(shè)：①網(wǎng)絡(luò)中的每個節(jié)點(diǎn)能夠自適應(yīng)地調(diào)整其發(fā)射功率；②假設(shè)每個節(jié)點(diǎn)都配備了全方位天線；③干擾電平獨(dú)立于網(wǎng)絡(luò)流量，并且所有節(jié)點(diǎn)的干擾電平相同；④所有節(jié)點(diǎn)都知道其位置信息（可以通過某些定位技術(shù)或設(shè)備，例如GPS接收器），并且每個節(jié)點(diǎn)保持所有單跳相鄰節(jié)點(diǎn)的位置信息（這種位置信息可利用當(dāng)網(wǎng)絡(luò)最初部署時，鄰域節(jié)點(diǎn)之間交換hello消息的方式獲得，如果節(jié)點(diǎn)移動，可以定期交換等hello消息）；⑤假設(shè)MAC層是理想的，這可以保證數(shù)據(jù)包總是可以不丟失。
建立圖模型 G（V，E），V（G）代表節(jié)頂點(diǎn)集，E（G）代表邊集。（u，v）∈E（G）表示 u，v之間直接相連。如果的、d（u，v）≤R，那么 u，v之間存在鏈路（d（u，v）代表u，v兩點(diǎn)之間的幾何距離，而R代表節(jié)點(diǎn)在網(wǎng)絡(luò)中的最大均勻傳輸范圍）。
用euv代表節(jié)點(diǎn)u成功傳送信息單元到節(jié)點(diǎn)v所需的最小功率，在d（u，v）≤R 的前提下，euv=d（u，v）α+c，α 和 c是常數(shù)在特定的無線系統(tǒng)和傳播環(huán)境中（通常2≤α≤4）。c代表著由信號處理和成功接收信息所需的最小能量所造成的開銷。當(dāng)d（u，v）＞R，euv接近∞。對于給定的連接節(jié)點(diǎn)的路徑p，發(fā)送一個信息單元的整體功耗是鏈路中所有節(jié)點(diǎn)發(fā)射功率的總和。，用N（u）代表節(jié)點(diǎn)u的單跳相鄰節(jié)點(diǎn)集合，那么N（u）={v|v∈V（G），（u，v）∈E（G）}+{u}。讓 NE（u）表示 N（u）的兩個節(jié)點(diǎn)之間的邊的集合，那么NE（u）={（x，y）|（x，y）∈E（G）∧x，y∈N（u）}。該算法主要實(shí)現(xiàn)兩個目標(biāo)：①減少網(wǎng)絡(luò)節(jié)點(diǎn)的傳輸功率；②延長網(wǎng)絡(luò)的生存時間。
X-LMST中的關(guān)鍵問題是如何確定網(wǎng)絡(luò)中的鏈路的能量臨界值。該文獻(xiàn)定義了一個新的度量值。為了判定是否是能量關(guān)鍵鏈路，需要對鏈路的兩個端點(diǎn)節(jié)點(diǎn)的能量狀態(tài)進(jìn)行檢查。通常認(rèn)為，如果它們其中一個具有極低的能量，不管另一個節(jié)點(diǎn)剩余能量多么高，應(yīng)考慮該鏈路為能源關(guān)鍵鏈路。
想要描述每個節(jié)點(diǎn)影響一個在其單跳鄰域的鏈路是否是能量關(guān)鍵鏈路的程度，可以引入Lx表示每一個節(jié)點(diǎn)的能量等級，Lx=[L×Ex/Emax]。Emax表示一個節(jié)點(diǎn)能量總量，Ex表示一個節(jié)點(diǎn)的剩余能量，將Emax均勻分成L份。
對于鏈路（x，y）∈E（G），定義 ERGxy=1n（Lx×Ly）來描述鏈路能量狀態(tài)。這個新的度量具有以下突出的優(yōu)點(diǎn)：①對稱性，ERGxy=ERGyx=；②單調(diào)遞增性，隨著Ex，Ey增加而增加；③它的一階導(dǎo)數(shù)單調(diào)遞減；當(dāng)節(jié)點(diǎn)處于較低的能量水平時，自變量變化導(dǎo)致ERGxy的變化量比在較高的能量水平時更大，所以ERGxy可以正確反映出鏈路（x，y）的狀況。
定義的能量臨界比值K，這意味著單跳鄰域鏈路中的百分之K被認(rèn)為是能量關(guān)鍵鏈路。能量臨界值ERCcu與節(jié)點(diǎn)u∈V（G）有關(guān)，該值表示節(jié)點(diǎn)u的閾值，所以，只要NE（u）中某一鏈路的ERGxy小于ERCcu，就可判定該鏈路是能量關(guān)鍵鏈路。每個節(jié)點(diǎn)都有自己的能量臨界值ERCcu。
算法設(shè)計(jì)思想是首先，準(zhǔn)備節(jié)點(diǎn)u的單跳鄰域拓?fù)?，并且不使用能量關(guān)鍵鏈路；保留能量關(guān)鍵鏈路集合；然后，用非能量關(guān)鍵鏈路建立最小生成樹，使用到克魯斯卡爾算法；如果先前生成的最小生成樹不包含所有節(jié)點(diǎn)，繼續(xù)建立最小生成樹。這個過程中，優(yōu)先使用那些能量充足的鏈路；最后，生成一棵完整的最小生成樹Tu，將u點(diǎn)的新鄰域節(jié)點(diǎn)集合返回節(jié)點(diǎn)u。
并且對以下三種算法進(jìn)行仿真，X-LMST，E-LMST，和LMST算法。參考文獻(xiàn)比較了以下三項(xiàng)：網(wǎng)絡(luò)的生存時間（是指網(wǎng)絡(luò)中的第一個節(jié)點(diǎn)時能量耗盡的用時）；平均傳輸半徑；平均節(jié)點(diǎn)度。
文獻(xiàn)還對比了不同算法的平均網(wǎng)絡(luò)生存時間，以節(jié)點(diǎn)密度為自變量。X-LMST算法表現(xiàn)最好。一般來說，三種算法的平均網(wǎng)絡(luò)生命周期隨節(jié)點(diǎn)密度的增加而增加。并且X-LMST的優(yōu)勢也隨著節(jié)點(diǎn)密度增加而增加。這是因?yàn)?，網(wǎng)絡(luò)節(jié)點(diǎn)密度的增加可以提供更多的選擇，以避免過度使用能源的關(guān)鍵鏈路。
然后，比較了不同算法的平均傳輸半徑，以節(jié)點(diǎn)密度為自變量。傳輸半徑定義為一個節(jié)點(diǎn)與其鄰域節(jié)點(diǎn)集合中最遠(yuǎn)距離的節(jié)點(diǎn)之間的距離。平均傳輸半徑是在網(wǎng)絡(luò)中所有節(jié)點(diǎn)的傳輸半徑的總和（按不同的算法）。X-LMST具有最高的平均傳輸半徑。因?yàn)閄-LMST允許保留一些長鏈接的節(jié)點(diǎn)，同時消除一些雖然短但是能源關(guān)鍵的鏈路，實(shí)現(xiàn)網(wǎng)絡(luò)中的能量消耗平衡。
在平均節(jié)點(diǎn)度與節(jié)點(diǎn)密度方面，比較了不同算法的性能。最終得出X-LMST在三種算法中具有最大的平均節(jié)點(diǎn)度。
參考文獻(xiàn)
[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)有的拓?fù)淇刂扑惴ㄖ饕性诰W(wǎng)絡(luò)節(jié)點(diǎn)的低傳輸功率的分配問題上，同時保持全局連通。為了使每個節(jié)點(diǎn)學(xué)習(xí)到整個網(wǎng)絡(luò)的狀態(tài)信息，現(xiàn)有的算法不是結(jié)合全局網(wǎng)絡(luò)狀態(tài)信息，就是結(jié)合局部網(wǎng)絡(luò)狀態(tài)信息。前者的優(yōu)勢在于較低的發(fā)射功率，能更好的實(shí)現(xiàn)拓?fù)淇刂?，并在小型網(wǎng)絡(luò)表現(xiàn)出更好的性能，但是由于獲取全局狀態(tài)信息需要生成簡化圖，搜集和存儲該類信息開銷比較大，所以在實(shí)際情況下實(shí)現(xiàn)比較困難；而后者的優(yōu)勢在于以增加節(jié)點(diǎn)發(fā)射功率換取的高可伸縮性，并且，該算法允許每個節(jié)點(diǎn)獨(dú)立的控制其局部拓?fù)?，通過使用其鄰域信息（在保持網(wǎng)絡(luò)連接的同時）。然而，所有上述算法強(qiáng)調(diào)太多的網(wǎng)絡(luò)的稀疏性，缺乏對網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路的能量臨界狀態(tài)的考慮。
猜你喜歡
紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10
移動通信(2021年5期)2021-10-25 11:41:48
中學(xué)生數(shù)理化(高中版.高考理化)(2021年6期)2021-07-28 06:21:04
吉林大學(xué)學(xué)報(理學(xué)版)(2020年3期)2020-05-29 06:32:16
自動化學(xué)報(2018年7期)2018-08-20 02:59:04
周口師范學(xué)院學(xué)報(2016年5期)2016-10-17 06:36:47
中國交通信息化(2014年3期)2014-06-05 03:07:09
NBA特刊(2014年7期)2014-04-29 00:44:03
華東理工大學(xué)學(xué)報(自然科學(xué)版)(2014年2期)2014-02-27 13:48:48
自動化與儀表(2014年10期)2014-02-26 08:21:17
