陳功平 王 紅

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

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

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

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

圖1 RNG中的邊

圖2 GG中的邊

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

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

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

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

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

DRNG算法是基于RNG鄰近圖的拓?fù)淇刂扑惴āＫ惴鞒倘鐖D3所示：

圖3 DRNG算法流程圖

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

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

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

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

圖5 模塊之間的接口與門

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

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

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

圖6 協(xié)議層次圖

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

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

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

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

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

表2 DRNG算法功率表

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

表3 DLSS算法功率表

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

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

三、結(jié)論

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