基于鄰近圖拓?fù)錁?gòu)造算法的仿真設(shè)計(jì)

陳功平 王 紅

（六安職業(yè)技術(shù)學(xué)院信息與電子工程學(xué)院 安徽六安 237000）

無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）由大量微型傳感器節(jié)點(diǎn)組成，這類節(jié)點(diǎn)的主要工作是通過(guò)無(wú)線電傳輸模式構(gòu)建多跳自組網(wǎng)絡(luò)，從而達(dá)到擴(kuò)大監(jiān)測(cè)區(qū)域的目的。在監(jiān)測(cè)區(qū)域內(nèi)的工作包括其協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中感知對(duì)象的信息，并發(fā)送給觀察者。網(wǎng)絡(luò)拓補(bǔ)控制與無(wú)線傳感網(wǎng)絡(luò)相結(jié)合可以在保障網(wǎng)絡(luò)連通度和覆蓋率的基礎(chǔ)上，進(jìn)一步形成更加密閉的網(wǎng)絡(luò)環(huán)境，可以通過(guò)合理利用網(wǎng)絡(luò)拓補(bǔ)結(jié)控制構(gòu)，減少節(jié)點(diǎn)能耗和網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。由此可以看出拓?fù)淇刂圃跓o(wú)線傳感器網(wǎng)絡(luò)研究中的占有極其重要的地位，將其與無(wú)線網(wǎng)絡(luò)結(jié)合，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)研究來(lái)說(shuō)意義重大。林亭君等人（2018）提出利用風(fēng)光拓補(bǔ)算法可以提高變電站的運(yùn)輸效率以及提高光伏輸出功率的穩(wěn)定性[1]。謝宜婷等人（2017）提出為了提高圖像匹配度，可以利用特征描述算法檢測(cè)匹配關(guān)系，提高運(yùn)算性能[2]。鄒蕾等人（2017）提出通過(guò)對(duì)空間的層次劃分來(lái)構(gòu)建近鄰圖，能夠進(jìn)一步提高算法準(zhǔn)確度[3]?；诖?，可以看出，建立一種高效的拓?fù)淇刂颇軌虼蠓?jié)約節(jié)點(diǎn)能耗，能夠延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期，提高網(wǎng)絡(luò)連通的穩(wěn)定性，還能降低相互間信號(hào)的干擾，提高M(jìn)AC協(xié)議和路由協(xié)議的效率。

一、基于鄰近圖的拓?fù)淇刂平Ｑ芯?/h2>

（一）臨近圖。臨近圖分為相對(duì)臨近圖（RNG）以及伽布里圖（GG）兩種類型。相對(duì)臨近圖(Relative Neighborhood Graph)的定義十分簡(jiǎn)單：對(duì)?u，v∈V，如果(u,v)∈RNG，則不存在點(diǎn)w，使得max{d(u,w),d(v,w)}＜d(u,v)。該定義等價(jià)于圖2-1所示以u(píng)，v 為圓心的圓的相交區(qū)域內(nèi)不含有其他點(diǎn)。RNG唯一可平面。如果按照定義構(gòu)造RNG，需要O(N3)時(shí)間復(fù)雜度。如圖1、2所示：

圖1 RNG中的邊

圖2 GG中的邊

伽布里圖(Gabriel Gravh)屬于幾何鄰近圖。含義為：?u，v∈V，如果邊(u,v)∈GG，則不存在點(diǎn)w，使得d2(u,w)+d2(v,w)≤d2(u,v)。該定義等價(jià)于圖2-2中以u(píng)，v為直徑的圓中不含第三點(diǎn)w。GG唯一并且可平面。根據(jù)定義構(gòu)造算法時(shí)間復(fù)雜度為O(N3)[4]。

（二）DRNG和DLSS算法。DRNG和DLSS算法主要由信息收集、拓?fù)錁?gòu)建以及雙向連接的拓?fù)錁?gòu)建三個(gè)步驟組成[20]。兩者第一、三階段類似，主要區(qū)別在第二階段。

為了使算法更加便于理解，首先作如下定義：

1.(u,v)表示從點(diǎn)u至點(diǎn)v的有向邊，與(v,u)方向相反；

2.d(u,v)表示點(diǎn)u和點(diǎn)v之間的距離。ru表是節(jié)點(diǎn)u的通信半徑?？蛇_(dá)鄰居集合Nu表示節(jié)點(diǎn)以最大功率發(fā)射所能到達(dá)的節(jié)點(diǎn)集合。

DRNG算法是基于RNG鄰近圖的拓?fù)淇刂扑惴?。算法流程如圖3所示：

圖3 DRNG算法流程圖

在上面的階段完成之后將發(fā)射功率調(diào)整為與最遠(yuǎn)鄰居節(jié)點(diǎn)通信所需要的功率。在無(wú)線網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)必須是雙向連通的才能夠在拓?fù)鋱D中形成邊。因此還需要將拓?fù)鋱D進(jìn)一步的修改，刪去只能單邊通信的邊。與DRNG 算法類似，首先每個(gè)節(jié)點(diǎn)以自己的最大發(fā)射功率周期性的廣播Hello消息，通過(guò)接收到其他節(jié)點(diǎn)的Hello消息確定自己的可達(dá)鄰居節(jié)點(diǎn)集合N。在得到鄰居節(jié)點(diǎn)集合N之后，DLSS算法通過(guò)以下標(biāo)準(zhǔn)確定鄰居節(jié)點(diǎn)：假設(shè)己知節(jié)點(diǎn)u以及它的可達(dá)鄰居子圖Gu，當(dāng)節(jié)點(diǎn)v在節(jié)點(diǎn)u的直接局部生成圖Su上，其中Su是DLSS(u)的輸出，并且與節(jié)點(diǎn)u只相隔一跳距離時(shí)，節(jié)點(diǎn)v是節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)，記為DLSS(u-＞v)[5]。

（三）OMNET++模型架構(gòu)。OMNET++是一款基于組建的模塊化的開(kāi)放網(wǎng)絡(luò)仿真平臺(tái)。所以用戶可以通過(guò)OMNET++簡(jiǎn)便的描述實(shí)際系統(tǒng)結(jié)構(gòu)。OMNET++的模塊以分層次的嵌入式模塊為主。模塊結(jié)構(gòu)在程序中使用NED語(yǔ)言描述。這些模塊可以相互間傳遞消息，也可以多個(gè)簡(jiǎn)單模塊（simple modules）組成一個(gè)復(fù)合模塊（compound modules），如圖4所示：

圖4 簡(jiǎn)單模塊和復(fù)合模塊

當(dāng)然為了使這些混合模塊能夠與簡(jiǎn)單模塊一樣使用，在這些混合模塊的定義中必須要設(shè)定它的“門(mén)”，也就是與其他模塊相連接的接口。每個(gè)模塊都是通過(guò)輸出門(mén)發(fā)送消息，通過(guò)輸入門(mén)接收消息。而門(mén)到門(mén)的對(duì)應(yīng)關(guān)系就構(gòu)成了鏈接，如圖5所示。

圖5 模塊之間的接口與門(mén)

二、基于鄰近圖的仿真實(shí)現(xiàn)

（一）通信協(xié)議架構(gòu)。在本文所建立的網(wǎng)絡(luò)模型中，使用的是CSMA MAC 協(xié)議，每個(gè)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)幀之前，首先要進(jìn)行載波監(jiān)聽(tīng)，只有介質(zhì)空閑時(shí)，才允許發(fā)送幀。然后隨機(jī)延時(shí)一段時(shí)間后，再重新?tīng)?zhēng)用介質(zhì)，重發(fā)送幀[6]。

在節(jié)點(diǎn)收到信號(hào)的時(shí)候一層層上傳，最后在appl層通過(guò)handleLowerMsg(cMessage*msg)判斷消息的類型，如果是廣播信息，則發(fā)送一個(gè)reply信息，如果是一個(gè)對(duì)應(yīng)自己發(fā)送的廣播信息的reply 則輸出“Received reply from host……”然后刪除該消息，否則報(bào)錯(cuò)。協(xié)議層次圖如下圖6所示：

圖6 協(xié)議層次圖

（二）功率與通信距離仿真分析。為了觀察節(jié)點(diǎn)距離與發(fā)射功率的關(guān)系，實(shí)驗(yàn)分別按照功率調(diào)整和距離調(diào)節(jié)，通過(guò)多次實(shí)驗(yàn)之后得出如下表1與圖7所示：

表1 間距與發(fā)射功率的關(guān)系

圖7 間距與發(fā)射功率的關(guān)系

由圖7 可知，兩點(diǎn)間間距與發(fā)射功率呈正相關(guān)，在兩點(diǎn)間距離達(dá)到60時(shí)，發(fā)射功率迅速上升。

（三）鄰近圖算法控制與網(wǎng)絡(luò)生命周期分析。實(shí)驗(yàn)中，設(shè)置10個(gè)節(jié)點(diǎn)隨機(jī)分布在200m*200m 的范圍內(nèi)，節(jié)點(diǎn)的最大發(fā)射功率為100mw，節(jié)點(diǎn)的最大發(fā)射距離為99m，網(wǎng)絡(luò)允許的最大發(fā)射功率為100mw。按照DRNG算法，經(jīng)計(jì)算得到節(jié)點(diǎn)對(duì)應(yīng)的發(fā)射功率如表2所示：

表2 DRNG算法功率表

按照DLSS算法，經(jīng)計(jì)算得到節(jié)點(diǎn)對(duì)應(yīng)的發(fā)射功率如表3所示：

表3 DLSS算法功率表

由表2與3比較可得，0號(hào)節(jié)點(diǎn)在DLSS算法中發(fā)射功率較小。DRNG算法和DLSS算法的執(zhí)行結(jié)果表明，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)相對(duì)于原始拓?fù)鋱D有了明顯的簡(jiǎn)化，簡(jiǎn)化的通信鏈路將使網(wǎng)絡(luò)能耗大大節(jié)省，網(wǎng)絡(luò)的生存時(shí)間自然而然的得到延長(zhǎng)。

相比而言，DLSS算法要比DRNG算法復(fù)雜得多。同時(shí)由于DLSS算法是在LMST的基礎(chǔ)上產(chǎn)生的，通過(guò)拓?fù)浣Y(jié)構(gòu)圖也可以看出通過(guò)DLSS算法得到的網(wǎng)絡(luò)結(jié)構(gòu)圖的魯棒性明顯弱于DRNG圖。所以DLSS算法在節(jié)能的方面確實(shí)占有一定的優(yōu)勢(shì)，但是在實(shí)際應(yīng)用中，DRNG算法顯然更加具有實(shí)用性。

三、結(jié)論

本文分析了已有的經(jīng)典DRNG 和DLSS 拓?fù)淇刂扑惴?，并且進(jìn)一步的提出了改進(jìn)，并且對(duì)算法進(jìn)行了仿真。通過(guò)仿真之后以直觀的結(jié)果顯示了拓?fù)淇刂扑惴▽?duì)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化作用，明顯地節(jié)約了網(wǎng)絡(luò)的節(jié)點(diǎn)能量，延長(zhǎng)了網(wǎng)絡(luò)的生存周期。無(wú)線傳感器網(wǎng)絡(luò)是一門(mén)面向應(yīng)用的學(xué)科，也只有在實(shí)際應(yīng)用進(jìn)行研究，它才能得到發(fā)展。拓?fù)淇刂萍夹g(shù)的研究是整個(gè)無(wú)線傳感網(wǎng)絡(luò)研究中第一個(gè)十分重要的方面。它影響著整個(gè)網(wǎng)絡(luò)的性能，效率，生存時(shí)間。針對(duì)拓?fù)淇刂萍夹g(shù)研究可以從以綜合應(yīng)用功率控制、層次性拓?fù)淇刂坪蛦l(fā)機(jī)制這個(gè)方面進(jìn)行。綜合考慮無(wú)線傳感網(wǎng)路的魯棒性、能耗、高效路由協(xié)議和MAC協(xié)議，在他們之間找到一個(gè)平衡點(diǎn)。