基于DRNG與DLSS拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)模型優(yōu)化研究

彭文良

摘要：對(duì)基于鄰近圖的主流拓?fù)淇刂扑惴ㄟM(jìn)行了闡述，通過(guò)OMNET++軟件仿真建模，設(shè)計(jì)出基于DRNG與DLSS拓?fù)淇刂扑惴ǖ木W(wǎng)絡(luò)模型，仿真并收集分析數(shù)據(jù)結(jié)果，結(jié)果表明：改進(jìn)DLSS算法與DRNG算法都能夠?qū)崿F(xiàn)通信拓?fù)浣Y(jié)構(gòu)的簡(jiǎn)化，達(dá)到降能的目的;改進(jìn)DRNG算法比DLSS算法優(yōu)化的拓?fù)浣Y(jié)構(gòu)的魯棒性更好，更適合實(shí)際應(yīng)用推廣。同時(shí)提出改進(jìn)和優(yōu)化的策略。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò);拓?fù)淇刂?鄰近圖;DRNG;DLSS;

中圖分類(lèi)號(hào)：TP391? 文獻(xiàn)標(biāo)志碼：A? 文章編號(hào)：1008-4657（2021）02-0079-05

0 引言

無(wú)線傳感器網(wǎng)絡(luò)是集合信息傳遞、接收和處理與一體的自組織的網(wǎng)絡(luò)系統(tǒng)，涉及環(huán)境、醫(yī)療、軍事、工業(yè)、農(nóng)業(yè)以及交通等應(yīng)用領(lǐng)域[1]。拓?fù)淇刂萍夹g(shù)是保證無(wú)線傳感器網(wǎng)絡(luò)通信機(jī)制與數(shù)據(jù)融合的重要支撐技術(shù)之一，對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化與節(jié)能降耗等方面具有直接關(guān)系[2]。陳軍[3]提出了一種啟發(fā)式分簇拓?fù)淇刂品椒ǎ昧Ｗ尤簩?shí)現(xiàn)通信節(jié)點(diǎn)的分簇，從而提升通信網(wǎng)絡(luò)的連通性與生命周期。劉志龍等[4]采用群交叉與變異的方式達(dá)到非均勻分簇，控制傳感器節(jié)點(diǎn)的剩余能量與負(fù)載直接的均衡，在較大的網(wǎng)絡(luò)吞吐量下仍然能夠保持較長(zhǎng)的生命周期。除了通過(guò)建立粒子群算法達(dá)到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的控制之外，還可以通過(guò)優(yōu)化節(jié)點(diǎn)可靠性權(quán)值的方式達(dá)到節(jié)能的目的。宋偉奇等[5]通過(guò)構(gòu)建網(wǎng)絡(luò)節(jié)點(diǎn)模型優(yōu)化傳輸節(jié)點(diǎn)的權(quán)值約束，提升數(shù)據(jù)傳輸?shù)牧鲿扯?，達(dá)到延長(zhǎng)網(wǎng)絡(luò)壽命周期的目的。本文通過(guò)OMNET++軟件對(duì)改進(jìn)后的DRNG（Directed Relative Neighborhood Graph）算法與DLLS（Directed Local Spanning Subgraph）算法的網(wǎng)絡(luò)模型進(jìn)行仿真，比較不同節(jié)點(diǎn)優(yōu)化技術(shù)的優(yōu)勢(shì)，為拓?fù)淇刂萍夹g(shù)在無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能降耗研究提供依據(jù)。

1 基于鄰近圖的拓?fù)淇刂?/p>

1.1 DRNG算法改進(jìn)

在DRNG算法中[6]，在得到u的鄰居節(jié)點(diǎn)集之后，在鄰居節(jié)點(diǎn)集內(nèi)尋找距離節(jié)點(diǎn)u最遠(yuǎn)的節(jié)點(diǎn)v，并且根據(jù)這兩節(jié)點(diǎn)間的距離來(lái)確定節(jié)點(diǎn)的最大發(fā)射功率。所以此算法的最終目的就是找到距離節(jié)點(diǎn)最遠(yuǎn)的鄰居節(jié)點(diǎn)。在原有的DRNG算法中需要判斷所有的n個(gè)鄰居節(jié)點(diǎn)是否為u的鄰居節(jié)點(diǎn)，而改進(jìn)DRNG算法減少了n/2需要確定的鄰居節(jié)點(diǎn)的個(gè)數(shù)。那么在尋找鄰居節(jié)點(diǎn)的時(shí)候如果對(duì)于它的可達(dá)節(jié)點(diǎn)進(jìn)行排序，算法的復(fù)雜度將會(huì)從原來(lái)的n4比較次數(shù)下降為n2比較次數(shù)。算法步驟如圖1所示。

DRNG算法改進(jìn)主要是在確定可達(dá)鄰居集合N后，將N中的節(jié)點(diǎn)按照與u的距離從大到小進(jìn)行排序，記為v1、v2、v3、...、vn。每個(gè)節(jié)點(diǎn)vi（i=1，2，3，...，n）兩兩之間的集合{vi+1，vn}，如果不存在一點(diǎn)p滿足max{d（u，p），d（v，p）}< d（u，v），則vi即是u的最遠(yuǎn)鄰居節(jié)點(diǎn)。按照vi到u的距離d（ui，v）調(diào)節(jié)發(fā)射功率。

1.2 DLSS的拓?fù)淇刂扑惴?/p>

基于DLSS算法的拓?fù)浣Y(jié)構(gòu)的通信流程與DRNG算法的結(jié)構(gòu)類(lèi)似[6]。通過(guò)每個(gè)節(jié)點(diǎn)發(fā)送最大功率的廣播Hello信息，結(jié)合DLSS算法的節(jié)點(diǎn)定位確定鄰居節(jié)點(diǎn)從而實(shí)現(xiàn)最高效率的通信路徑篩選。具體的算法如下：

輸入?yún)?shù)：Gu：u的可達(dá)鄰居子圖G;

輸出參數(shù)：Su=（V（Su），E（Su）），根據(jù)Gu得到的局部生成子圖。

Begin

1 Sort（E （Gu））;將E（Gu）中的邊按照權(quán)重排序

2 for each edge （u0，v0） in the order

3? ?if u0 is not connected to v0 in Su

4??? ?E（Su）：=E（Su）∪{（u0，v0）}

5? ?end if

6 end

End

在完成上述過(guò)程后，調(diào)整節(jié)點(diǎn)發(fā)射功率，使之能與最遠(yuǎn)的鄰居節(jié)點(diǎn)通信。最后將拓?fù)鋱D中的單向邊刪去，僅保留雙向連通的鏈路，保證網(wǎng)絡(luò)的雙向連通。

1.3 基于鄰近圖的仿真建模

本文使用OMNET++（Objective Modular Network TestBed in C++）仿真軟件進(jìn)行實(shí)驗(yàn)的仿真。

1.3.1 節(jié)點(diǎn)模塊構(gòu)成

在OMNET++中其實(shí)節(jié)點(diǎn)也可以看成是一個(gè)混合模塊，只是有幾個(gè)混合模塊和簡(jiǎn)單模塊相互連接就構(gòu)成了節(jié)點(diǎn)。在本文的實(shí)驗(yàn)中建立了最基本的節(jié)點(diǎn)模塊：BaseNode。參數(shù)如下：

parameters：

string applType; //type of the application layer

string netwType; //type of the network layer

string mobType; //type of the mobility module可以設(shè)置節(jié)點(diǎn)是否移動(dòng)

@display（"bgb=301，256，white"）;

整個(gè)節(jié)點(diǎn)內(nèi)部個(gè)模塊之間的連接：

nic.upperGateOut --> net.lowerGateIn;

nic.upperGateIn <-- net.lowerGateOut;

nic.upperControlOut --> { @display（"ls=red;m=m，70，0，70，0"）; } -->net.lowerControlIn;

nic.upperControlIn <-- { @display（"ls=red;m=m，70，0，70，0"）; } <--net.lowerControlOut;

net.upperGateOut --> appl.lowerGateIn;

net.upperGateIn <-- appl.lowerGateOut;

net.upperControlOut --> { @display（"ls=red;m=m，70，0，70，0"）; } -->appl.lowerControlIn;

net.upperControlIn <-- { @display（"ls=red;m=m，70，0，70，0"）; } <-- appl.lowerControlOut;

radioIn --> nic.radioIn;

1.3.2 功率與通信距離

在接收靈敏度一定情況下，采用無(wú)線發(fā)射功率P和接收半徑R之間關(guān)系是：

P∝Rn（2 < n < 5）（1）

也就是P可能會(huì)遠(yuǎn)遠(yuǎn)大于R2。n的取值與很多因素有關(guān)，主要是環(huán)境因素，在本文的實(shí)驗(yàn)環(huán)境中，通過(guò)設(shè)置一系列參數(shù)之后，使得n取值為3，與一般實(shí)際情況相符合。一般而言，傳感器節(jié)點(diǎn)的無(wú)線通信半徑在100 m以內(nèi)比較合適。因此，本文選擇0～99 m作為節(jié)點(diǎn)通信實(shí)驗(yàn)的測(cè)試距離。

1.3.3 功率調(diào)節(jié)

將路徑損失系數(shù)alpha設(shè)置為3.0，將最小信號(hào)衰減閥值sat設(shè)置為-84 dBm，載波頻率carrierFrequency設(shè)置為2.412e+9 Hz。在OMNET++中有對(duì)于發(fā)射功率和節(jié)點(diǎn)間距的一個(gè)計(jì)算函數(shù)，但是在仿真過(guò)程中發(fā)現(xiàn)，在距離超過(guò)50 m的時(shí)候就存在較大的偏差，因此，本文分別通過(guò)調(diào)節(jié)節(jié)點(diǎn)發(fā)射間距和節(jié)點(diǎn)發(fā)射功率，得出兩者之間的函數(shù)關(guān)系。然后再另選一些點(diǎn)，并且根據(jù)兩者之間的距離，將他們的功率調(diào)節(jié)為由公式計(jì)算得出的值，驗(yàn)證是否能夠相互通信。

2 基于鄰近圖的仿真結(jié)果分析

2.1 調(diào)整功率與通信距離的關(guān)系

2.1.1 實(shí)驗(yàn)場(chǎng)景

對(duì)于本次實(shí)驗(yàn)場(chǎng)景已有一定的描述，如圖2所示。

node[0]向周?chē)l(fā)送BROADCAST_MESSAGE信號(hào)，如果node[1]在收到發(fā)送的信號(hào)之后認(rèn)為該信號(hào)是有效信號(hào)，即信號(hào)強(qiáng)度大于sensitivity則認(rèn)為是有效信號(hào)，發(fā)送BROADCAST_REPLY_MESSAGE。否則，node[1]節(jié)點(diǎn)將會(huì)將該廣播信號(hào)認(rèn)為是干擾信號(hào)直接丟棄。

2.1.2 節(jié)點(diǎn)距離與發(fā)射功率的關(guān)系

根據(jù)功率調(diào)整與距離調(diào)節(jié)的方式，探討節(jié)點(diǎn)距離與發(fā)射功率之間的關(guān)系，分別測(cè)量了間距為10～99 m之間的發(fā)射功率，結(jié)果如表1所示。隨著間距的不斷增大調(diào)整功率隨之增大，并在間距為99 m時(shí)，功率達(dá)到100 mW。

2.2 鄰近圖算法控制與網(wǎng)絡(luò)生命周期分析

2.2.1 改進(jìn)DRNG和DLSS算法功率比較

在200 m * 200 m的范圍內(nèi)設(shè)置10個(gè)隨機(jī)分布的節(jié)點(diǎn)，節(jié)點(diǎn)的最大發(fā)射功率為100 mW，節(jié)點(diǎn)的最大發(fā)射距離為99 m。根據(jù)改進(jìn)DRNG和DLSS算法，分別計(jì)算得到節(jié)點(diǎn)對(duì)應(yīng)的發(fā)射功率。節(jié)點(diǎn)分布如圖3所示。

由圖3可知，除0號(hào)節(jié)點(diǎn)外，在改進(jìn)DRNG和DLSS算法的相同坐標(biāo)下的發(fā)射功率均一致。而在0號(hào)節(jié)點(diǎn)中，DLSS算法的發(fā)射功率較大，達(dá)到10.1 mW。

2.2.2 仿真實(shí)驗(yàn)與結(jié)果

圖4顯示了網(wǎng)絡(luò)運(yùn)行中的節(jié)點(diǎn)建立拓?fù)涞倪^(guò)程，在建立初期，已經(jīng)確立了每個(gè)節(jié)點(diǎn)的發(fā)射功率。圖4（a）中的node[8]首先發(fā)送廣播消息，圖4（b）的node[9]節(jié)點(diǎn)和node[5]同時(shí)接收到廣播消息，形成消息隊(duì)列，node[9]節(jié)點(diǎn)首先轉(zhuǎn)發(fā)reply消息，然后node[5]節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，如圖4（c）所示。

（a） node[8]發(fā)送廣播信號(hào)（b） node[7]發(fā)送reply信號(hào)（c） node[5]發(fā)送reply信號(hào)圖4 節(jié)點(diǎn)信號(hào)發(fā)送過(guò)程圖

如果網(wǎng)絡(luò)節(jié)點(diǎn)的初始發(fā)射功率為最大值，經(jīng)過(guò)如圖4的網(wǎng)絡(luò)節(jié)點(diǎn)不斷轉(zhuǎn)發(fā)探測(cè)過(guò)程，建立了網(wǎng)狀的網(wǎng)絡(luò)拓?fù)潢P(guān)系圖如圖5（a）所示。用改進(jìn)DRNG拓?fù)淇刂扑惴窗凑毡?發(fā)射功率，確立的拓?fù)浣Y(jié)構(gòu)如圖5（b）所示。圖5（c）是按照DLSS算法得到個(gè)拓?fù)浣Y(jié)構(gòu)。

從圖5中可以看出，在網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)中無(wú)論是采用改進(jìn)DRNG算法還是DLSS算法優(yōu)化，拓?fù)鋱D都比原始圖更簡(jiǎn)化，從而實(shí)現(xiàn)通信網(wǎng)絡(luò)的節(jié)能與生存時(shí)間的延長(zhǎng)。對(duì)比圖5（b）和圖5（c）可以看出在網(wǎng)絡(luò)通信鏈路上DLSS算法優(yōu)化的路徑比較單一化，僅僅存在一條通信回路，所以DLSS算法優(yōu)化的拓?fù)渚W(wǎng)絡(luò)比改進(jìn)DRNG算法更節(jié)能。然而，改進(jìn)DRNG算法優(yōu)化的拓?fù)浣Y(jié)構(gòu)中存在兩條可選擇的通信鏈回路，在網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性上比DLSS算法更好，既保證了網(wǎng)絡(luò)結(jié)構(gòu)的通信降能耗，也保障網(wǎng)絡(luò)結(jié)構(gòu)通信的穩(wěn)定性。因此，在實(shí)際應(yīng)用中改進(jìn)DRNG算法相較于DLSS算法更具推廣性與實(shí)用性。

3 結(jié)論

拓?fù)淇刂萍夹g(shù)是無(wú)線傳感網(wǎng)絡(luò)實(shí)現(xiàn)節(jié)能降耗，延長(zhǎng)通信生命周期的關(guān)鍵。本文在原有DRNG算法的基礎(chǔ)上，利用尋找最遠(yuǎn)通信節(jié)點(diǎn)的方式重新對(duì)算法進(jìn)行優(yōu)化，并與經(jīng)典DLSS算法和原始拓?fù)浣Y(jié)構(gòu)進(jìn)行比較分析與仿真，得到以下結(jié)論：改進(jìn)DLSS算法與DRNG算法都能夠?qū)崿F(xiàn)通信拓?fù)浣Y(jié)構(gòu)的簡(jiǎn)化，達(dá)到降能的目的;改進(jìn)DRNG算法比DLSS算法優(yōu)化的拓?fù)浣Y(jié)構(gòu)的魯棒性更好，更適合實(shí)際應(yīng)用推廣。

參考文獻(xiàn)：

[1] 李安瑩，房鑫平，孫福陽(yáng).無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯烤C述[J].中國(guó)新技術(shù)新產(chǎn)品，2015（23）：17.

[2]? 司永潔，張健.低損耗無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǚ抡鎇J].計(jì)算機(jī)仿真，2019，36（10）：273-276.

[3]? 陳軍.無(wú)線傳感器網(wǎng)絡(luò)啟發(fā)式分簇拓?fù)淇刂品椒╗J].科學(xué)技術(shù)與工程，2018，18（19）：94-99.

[4]? 劉志龍，張淋江，周紅雷，等.非均勻分簇?zé)o線傳感器網(wǎng)絡(luò)拓?fù)淇刂品抡鎇J].計(jì)算機(jī)仿真，2019，36（4）：260-264.

[5]? 宋偉奇，王代遠(yuǎn).基于節(jié)點(diǎn)優(yōu)化的無(wú)線傳感網(wǎng)絡(luò)拓?fù)淇刂品椒ㄑ芯縖J].廣西民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，25（3）：80-83.

[6]? 陳功平，王紅.基于鄰近圖拓?fù)錁?gòu)造算法的仿真設(shè)計(jì)[J].綏化學(xué)院學(xué)報(bào)，2020，40（2）：158-160.

[責(zé)任編輯：許立群]