基于虛連接技術(shù)的信息孤島快速檢測機(jī)制

賴丹丹，陳科明，奚林祥

基于虛連接技術(shù)的信息孤島快速檢測機(jī)制

賴丹丹，陳科明，奚林祥

(杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018)

提出了一種基于虛連接技術(shù)的快速孤島檢測機(jī)制.通過虛連接技術(shù)使相鄰孤島節(jié)點(diǎn)間建立臨時(shí)連接關(guān)系，形成環(huán)形孤島，設(shè)計(jì)了專用手持檢測設(shè)備.在現(xiàn)場勘測中，只要搜索到環(huán)形孤島的任一節(jié)點(diǎn)，即可檢測到環(huán)形孤島中的全部節(jié)點(diǎn)，避免了對(duì)單個(gè)節(jié)點(diǎn)依次搜索.仿真實(shí)驗(yàn)表明，采用虛連接機(jī)制的方法可以快速搜索到孤島節(jié)點(diǎn)，大大減少了搜索的工作量，提高了搜索效率.

無線組網(wǎng)；虛連接；孤島檢測

0 引 言

在無線抄表、智能照明等數(shù)據(jù)采集與監(jiān)控場合，無線mesh組網(wǎng)技術(shù)得到了廣泛應(yīng)用[1].在使用無線組網(wǎng)技術(shù)進(jìn)行搜索的實(shí)際應(yīng)用中，由于無線節(jié)點(diǎn)間距離過遠(yuǎn)、障礙物阻擋等原因，現(xiàn)場的無線節(jié)點(diǎn)會(huì)形成通信孤島[2]，從而給現(xiàn)場搜索工作帶來困難.

目前，采用無線組網(wǎng)技術(shù)發(fā)現(xiàn)并解決孤島問題的方法主要有基于節(jié)點(diǎn)幀的孤島節(jié)點(diǎn)處理方法[3]、基于優(yōu)化鄰居集合的改進(jìn)DAODV路由算法[4].基于優(yōu)化鄰居集合的改進(jìn)DAODV路由算法，通過動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的發(fā)射功率以改進(jìn)節(jié)點(diǎn)有效傳輸距離，從而達(dá)到節(jié)能和降低孤島效應(yīng)的目的[5].這些方法主要是通過路由算法解決孤島問題，當(dāng)節(jié)點(diǎn)增大致使發(fā)射功率無法與鄰居節(jié)點(diǎn)通信或即使多跳也無法到達(dá)網(wǎng)關(guān)時(shí)，上述方法將不適用.本文針對(duì)孤島節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間不存在通路，或雖然與鄰居節(jié)點(diǎn)之間存在通路但無法通過多跳到達(dá)無線網(wǎng)關(guān)的情況，引入了虛連接技術(shù)，使孤島之間相互建立連接，設(shè)計(jì)了手持檢測設(shè)備，可在現(xiàn)場快速發(fā)現(xiàn)孤島.

1 虛連接快速搜索孤點(diǎn)機(jī)制

無線節(jié)點(diǎn)在初始化過程中，需要找到一條最終能到達(dá)無線網(wǎng)關(guān)的無線網(wǎng)絡(luò)通路[6]，進(jìn)而與網(wǎng)管服務(wù)器通信，完成設(shè)備認(rèn)證，如圖1所示.認(rèn)證之后，此節(jié)點(diǎn)才是網(wǎng)絡(luò)中的合法設(shè)備.在完成設(shè)備認(rèn)證之前，稱節(jié)點(diǎn)與網(wǎng)關(guān)之間建立的連接為虛連接，如圖1(b)所示.虛連接在鄰居節(jié)點(diǎn)之間逐跳建立.在網(wǎng)管系統(tǒng)完成對(duì)無線節(jié)點(diǎn)的設(shè)備認(rèn)證之后，從被認(rèn)證節(jié)點(diǎn)到網(wǎng)關(guān)之間的虛連接轉(zhuǎn)變?yōu)閷?shí)連接，如圖1(c)所示.

圖1 虛連接與實(shí)連接示意圖

1.1 虛連接自發(fā)的建立

無線節(jié)點(diǎn)A(以下簡稱A)上電之后，還未與網(wǎng)關(guān)之間建立任何連接，此時(shí)距離網(wǎng)關(guān)的跳數(shù)為無窮大.

每隔一段時(shí)間，A就以廣播方式發(fā)送探測信息并等待鄰居節(jié)點(diǎn)的應(yīng)答.鄰居節(jié)點(diǎn)B收到此探測信息之后，將會(huì)把自身的MAC地址，接收的信號(hào)強(qiáng)度指示(Received Signal Strength Indication，RSSI)，距離網(wǎng)關(guān)的跳數(shù)作為應(yīng)答信息以單播的方式發(fā)給A.A收到此應(yīng)答信息之后就與鄰居節(jié)點(diǎn)B建立了虛連接.

圖2 路徑發(fā)現(xiàn)算法流程圖

當(dāng)存在多個(gè)鄰居節(jié)點(diǎn)時(shí)，A可以與多個(gè)鄰居節(jié)點(diǎn)建立虛連接，并把鄰居節(jié)點(diǎn)信息保存在鄰居節(jié)點(diǎn)列表中.

A為了與網(wǎng)管服務(wù)器通信完成設(shè)備認(rèn)證，需要找到一條能夠到達(dá)無線網(wǎng)關(guān)的路徑.在保證RSSI大于閾值且跳數(shù)小于閾值的情況下，通過了路徑發(fā)現(xiàn)算法在整個(gè)網(wǎng)絡(luò)中遞歸地發(fā)現(xiàn)這條路徑，其流程如圖2所示，步驟如下：

1)遍歷A的鄰居節(jié)點(diǎn)列表，標(biāo)記所有RSSI大于設(shè)定閾值的鄰居節(jié)點(diǎn)；

2)在上述標(biāo)記的節(jié)點(diǎn)中找出距離網(wǎng)關(guān)跳數(shù)最少的節(jié)點(diǎn)，若其跳數(shù)小于設(shè)定閾值，則將此節(jié)點(diǎn)設(shè)為A的上一跳節(jié)點(diǎn)；

3)更新A的跳數(shù)為上一跳節(jié)點(diǎn)的跳數(shù)加1；

4)若在步驟1中無法找到RSSI大于設(shè)定閾值的鄰居節(jié)點(diǎn)，或在步驟2中無法找到距離網(wǎng)關(guān)跳數(shù)小于設(shè)定閾值的鄰居節(jié)點(diǎn)，則本次路徑發(fā)現(xiàn)失敗.

1.2 虛連接的輔助建立

圖3 孤島節(jié)點(diǎn)搜索算法

由于孤島節(jié)點(diǎn)沒有到達(dá)無線網(wǎng)關(guān)的路徑，網(wǎng)管人員無法通過網(wǎng)管服務(wù)器發(fā)現(xiàn)孤島節(jié)點(diǎn).這時(shí)，就需要現(xiàn)場技術(shù)人員攜帶手持無線設(shè)備到安裝現(xiàn)場探測孤島節(jié)點(diǎn).手持無線設(shè)備作為一個(gè)跳數(shù)為1的特殊節(jié)點(diǎn)，其包含必要的人機(jī)交互界面，可以與鄰居節(jié)點(diǎn)建立虛連接.

在手持無線設(shè)備的移動(dòng)過程中，手持無線設(shè)備會(huì)標(biāo)記出跳數(shù)為無窮大的鄰居節(jié)點(diǎn)，這些鄰居節(jié)點(diǎn)就是孤島節(jié)點(diǎn).一旦與一個(gè)孤島節(jié)點(diǎn)B(以下簡稱B)建立虛連接，手持無線設(shè)備就會(huì)通過虛連接獲取B的鄰居節(jié)點(diǎn)列表.因此，只要遍歷以B和其鄰居節(jié)點(diǎn)為頂點(diǎn)，虛連接為邊形成的連通圖，就可以搜索到所有的孤島節(jié)點(diǎn).

為了在連通圖中盡可能多地搜索到孤島節(jié)點(diǎn)，采用廣度優(yōu)先搜索(Breadth First Search，BFS)算法，流程如圖3所示，步驟如下：

1)遍歷B的鄰居節(jié)點(diǎn)列表，記錄所有新發(fā)現(xiàn)的節(jié)點(diǎn)；

2)標(biāo)記所有RSSI大于設(shè)定閾值的新發(fā)現(xiàn)節(jié)點(diǎn)；

3)在上述標(biāo)記的節(jié)點(diǎn)中依次獲取其鄰居節(jié)點(diǎn)列表并記錄所有新發(fā)現(xiàn)的節(jié)點(diǎn)；

4)重復(fù)執(zhí)行步驟2、步驟3直到無法再發(fā)現(xiàn)新的節(jié)點(diǎn).

搜索結(jié)束之后，手持無線設(shè)備記錄的所有新發(fā)現(xiàn)的節(jié)點(diǎn)都為孤島節(jié)點(diǎn).孤島節(jié)點(diǎn)的發(fā)現(xiàn)過程如圖4所示.圖4(a)為初始狀態(tài)，圖4(b-d)表示分別發(fā)現(xiàn)了1個(gè)、3個(gè)和6個(gè)孤島節(jié)點(diǎn).

圖4 孤島節(jié)點(diǎn)發(fā)現(xiàn)過程

2 理論分析

在虛連接自發(fā)建立的過程中，每個(gè)節(jié)點(diǎn)把鄰居節(jié)點(diǎn)信息保存在鄰居節(jié)點(diǎn)列表中.節(jié)點(diǎn)信息包括Mac地址、RSSI值、距離網(wǎng)關(guān)的跳數(shù).此時(shí)每個(gè)節(jié)點(diǎn)所需的空間大小如表1所示.

表1 節(jié)點(diǎn)所需內(nèi)存表 Byte

在虛連接輔助建立的過程中，使用搜索算法遍歷孤點(diǎn).假設(shè)此時(shí)所形成的連通圖有m個(gè)，每個(gè)連通圖有節(jié)點(diǎn)數(shù)為n；即孤點(diǎn)B的鄰居節(jié)點(diǎn)列表有n節(jié)點(diǎn).搜索中“最好情況”是指遍歷所有的節(jié)點(diǎn)的情況.“最壞情況”則是只能遍歷到B的鄰居節(jié)點(diǎn).搜索過程中主要是標(biāo)記RSSI值.孤島節(jié)點(diǎn)搜索算法所占用的內(nèi)存與時(shí)間復(fù)雜度如表2所示.

表2 算法所占用的內(nèi)存與時(shí)間復(fù)雜度

3 仿真分析

圖5 孤島搜索方法仿真結(jié)果

在區(qū)域?yàn)?0 m×50 m的平面區(qū)域，隨機(jī)布置無線節(jié)點(diǎn)50個(gè)，假設(shè)無線節(jié)點(diǎn)的通信半徑為8 m.利用本文的孤島搜索方法，可快速得到的仿真結(jié)果如圖5所示.可以看到，手持設(shè)備在B點(diǎn)搜索到了2個(gè)孤島節(jié)點(diǎn)(節(jié)點(diǎn)24和25)，并分別與其建立了虛連接.手持設(shè)備在A點(diǎn)首先搜索到23號(hào)節(jié)點(diǎn)，并與之建立虛連接.接著，手持設(shè)備通過23號(hào)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)建立的虛連接逐跳擴(kuò)大搜索范圍.

通過圖5的仿真結(jié)果，得出各類節(jié)點(diǎn)個(gè)數(shù)及編號(hào)如表3所示.一類節(jié)點(diǎn)是指形成單個(gè)孤點(diǎn)的節(jié)點(diǎn)；二類節(jié)點(diǎn)是指形成連通圖結(jié)構(gòu)的孤點(diǎn)；其余節(jié)點(diǎn)則指已經(jīng)連接上網(wǎng)關(guān)的節(jié)點(diǎn).

表3 各類節(jié)點(diǎn)個(gè)數(shù)及編號(hào)

文獻(xiàn)[4]提出的基于節(jié)點(diǎn)幀的孤島節(jié)點(diǎn)處理方法主要是通過篩選父節(jié)點(diǎn)來尋找孤點(diǎn)，不能快速解決二類節(jié)點(diǎn)，不能有效保證孤島節(jié)點(diǎn)搜索的效率；傳統(tǒng)的基于廣度的搜索方法需要通過對(duì)單個(gè)孤點(diǎn)進(jìn)行依次搜索，耗時(shí)時(shí)間長，耗費(fèi)資源大；本文提出的基于虛連接技術(shù)配合手持檢測設(shè)備的搜索方法，在A點(diǎn)B點(diǎn)只要搜索到任意孤點(diǎn)即可遍歷到所有二類孤點(diǎn).所以只需要搜索2次.

在本文仿真環(huán)境中，分別采用文獻(xiàn)[4]方法和基于廣度優(yōu)先搜索算法進(jìn)行實(shí)驗(yàn)，3種方法的所需遍歷孤點(diǎn)數(shù)如表4所示.

表4 幾大搜索方法對(duì)比表

文獻(xiàn)[4]中給出了孤島節(jié)點(diǎn)處理效率(準(zhǔn)確率與耗時(shí)的比值)：

(1)

式中，Q為搜索算法總計(jì)算量，n為網(wǎng)絡(luò)中的孤點(diǎn)數(shù)量，H{·}為算法復(fù)雜度，P為孤島節(jié)點(diǎn)處理效率，λ(α)為對(duì)搜索出的孤島節(jié)點(diǎn)進(jìn)行減免處理的耗時(shí).

文獻(xiàn)[7]通過對(duì)式(1)的證明可得，孤島節(jié)點(diǎn)的處理效率與所需遍歷的孤島節(jié)點(diǎn)數(shù)成反比.因此，通過表4的比較可知，3種方法中，本文方法中所需遍歷的孤點(diǎn)最少，處理效率最高.

4 結(jié)束語

本文提出了基于虛連接技術(shù)配合手持檢測設(shè)備的搜索，解決了通過調(diào)節(jié)節(jié)點(diǎn)發(fā)射功率和使用路由算法無法修復(fù)孤島節(jié)點(diǎn)的問題.本文僅提出了在網(wǎng)絡(luò)中建立虛連接，并通過手持無線檢測設(shè)備檢測孤島節(jié)點(diǎn)的方案，具體硬件設(shè)備的設(shè)計(jì)和軟件實(shí)現(xiàn)還有待進(jìn)一步研究.

[1]SGORAA,VERGADOSDD,CHATZIMISIOSP.AsurveyonsecurityandprivacyissuesinWirelessMeshNetworks[J].Security&CommunicationNetworks, 2016,9(13):1877-1889.

[2]TANIMOTOJ.Amulti-communityhomogeneoussmall-worldnetworkanditsfundamentalcharacteristics[J].PhysicaAStatisticalMechanics&ItsApplications, 2016,460:88-97.

[3]胡穎輝,于義科.ZigBee網(wǎng)絡(luò)中孤島節(jié)點(diǎn)快速處理算法研究[J].計(jì)算機(jī)仿真,2012(4):165-168.

[4]高峰.改進(jìn)孤島效應(yīng)的無線MESH網(wǎng)絡(luò)路由算法研究[D].長沙:湖南大學(xué),2013.

[5]張朝陽.無線網(wǎng)狀網(wǎng)中基于認(rèn)知無線電的頻譜分配研究[D].沈陽:東北大學(xué),2011.

[6]MOGAIBELHA,OTHMANM,SUBRAMANIAMS,etal.ReviewofChannelAssignmentApproachesinMulti-radioMulti-channelWirelessMeshNetwork[J].JournalofNetwork&ComputerApplications, 2016,72:113-139.

[7]LIX,FANGK,GUJ,etal.AnimprovedZigBeeroutingstrategyformonitoringsystem[C]//IntelligentNetworksandIntelligentSystems, 2008.ICINIS'08.FirstInternationalConferenceon.IEEE, 2008:255-258.

Mechanism of Quickly Detecting Information Island Base on Virtual Connection Technology

LAI Dandan, CHEN Keming, XI Linxiang

(SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

It is difficult to find information islands quickly in wireless mesh network. This paper proposes a mechanism to quickly find information islands based on virtual connection technology. Adjacent information islands connect each other with virtual connection technology. A dedicated handheld detecting instrument is designed. With this instrument, all information islands can be detected as long as one island node is found. Less time is spent than searching one by one. Simulation results show that virtual connection mechanism can detect information islands quickly.

wireless networking; virtual connection; information island

10.13954/j.cnki.hdu.2017.02.004

2016-09-13

賴丹丹(1992-)，女，江西撫州人，碩士研究生，物聯(lián)網(wǎng)技術(shù).通信作者:陳科明副教授，E-mail:keming106@163.com.

TN925

A

1001-9146(2017)02-0015-04