基于物聯(lián)網(wǎng)感知層的節(jié)點連通算法*

李 娜， 薛建生

(遼寧大學，遼寧 沈陽 110036)

0 引 言

在目前的物聯(lián)網(wǎng)(IoT)的三層結構中，對數(shù)據(jù)的處理過程是：感知層感知獲取信息，網(wǎng)絡層通過網(wǎng)關與互聯(lián)網(wǎng)等連接[1]，將感知到的數(shù)據(jù)送到云端進行處理，進而為不同的應用提供服務[2]。由于有些設備功能簡單，不能單獨完成全部處理工作，所以,數(shù)據(jù)都需要傳送到網(wǎng)關[3]。由于物聯(lián)網(wǎng)中擁有海量數(shù)據(jù)，用傳統(tǒng)的數(shù)據(jù)處理模式會造成網(wǎng)絡負載加重，影響傳輸速率甚至造成網(wǎng)絡擁堵，因此,有必要改進數(shù)據(jù)上傳的模式，將數(shù)據(jù)分類分層傳輸，將物聯(lián)網(wǎng)中實時性要求高，處理上要求相對比較簡單的任務，由感知層設備協(xié)同處理，以節(jié)省網(wǎng)絡帶寬，提高處理速度。

本文提出一種基于物聯(lián)網(wǎng)感知層的設備連通算法，為感知節(jié)點的協(xié)同工作提供必要的理論基礎。

1 基于感知層的節(jié)點連通算法

將感知層獲取到的數(shù)據(jù)分為兩類進行處理：對于處理上較復雜的數(shù)據(jù)，仍然通過網(wǎng)關上傳云端處理；而對于實時性要求嚴格且處理上比較簡單的數(shù)據(jù)，不再傳輸?shù)骄W(wǎng)關，而是在有處理能力的設備上進行數(shù)據(jù)處理、融合、去除臟數(shù)據(jù)。這樣不但可以減少向上層傳輸?shù)臄?shù)據(jù)量，同時能夠提高對于實時數(shù)據(jù)的處理速度[4]。為了實現(xiàn)對實時任務的快速協(xié)同處理，感知層眾多設備必須快速建立連通關系。嵌入式中間件能夠屏蔽掉各個異構網(wǎng)絡之間的差異，方便異構設備之間協(xié)同工作和數(shù)據(jù)交互，加強感知節(jié)點的互聯(lián)互操作能力。

將物聯(lián)網(wǎng)抽象為無向圖，運用連通支配集構建節(jié)點連通通道傳遞信息。運用連通支配集不但降低所需維護的路由信息量[5]，還可以優(yōu)化路由路徑[6]，節(jié)省連通建立所需時間。對實時數(shù)據(jù)及時處理，減少因上傳數(shù)據(jù)造成的網(wǎng)絡擁塞。

1.1 通過鄰接矩陣確定支配集節(jié)點

物聯(lián)網(wǎng)的拓撲結構可以通過無向圖表示，各個節(jié)點之間的連接情況能夠用鄰接矩陣的方式表示出來。鄰接矩陣生成具體步驟如下：

1)首先選取10個設備作為基礎網(wǎng)絡，建立其的鄰接矩陣，令N=10。

2)將矩陣初始化為元素全為2的矩陣，初始元素下標都賦值為0。

3)判斷該矩陣元素下標，若是對角線元素,則轉(zhuǎn)到步驟(4);否則,轉(zhuǎn)到(5)。

4)給對角線上元素賦值為0。

5)給非對角線上元素賦值，根據(jù)設備之間是否有連接賦值為1或者0。

6)判斷元素下標是否都為N-1，若是，則轉(zhuǎn)到(7);否則,下標加1，轉(zhuǎn)到(3)。

7)向基礎網(wǎng)絡中添加新設備，令N=物聯(lián)網(wǎng)系統(tǒng)中節(jié)點的個數(shù)，轉(zhuǎn)到(3)。

8)算法結束，得到物聯(lián)網(wǎng)的鄰接矩陣。

1.2 構造支配集

如果將物聯(lián)網(wǎng)的拓撲結構用無向圖表示，那么提取關鍵節(jié)點的問題就等同于在圖結構中求支配集問題[7]。求支配集的算法的具體步驟如下：

1)通過計算每行或每列的1的個數(shù)可以得到節(jié)點的鄰居節(jié)點個數(shù)。

2)給所有節(jié)點著色為白色。

3)計算每個非黑色節(jié)點的活躍鄰居節(jié)點個數(shù)。

4)選取其中個數(shù)最大的節(jié)點，給其著色為黑色，其鄰居節(jié)點中的白色節(jié)點著色為灰色。

5)判斷是否所有節(jié)點都為黑色或者灰色，若是,則轉(zhuǎn)到(6);否則,轉(zhuǎn)到(3)。

6)算法結束，輸出結果，得到一個支配集。

1.3 檢查與實現(xiàn)連通

上一節(jié)中得到的支配集節(jié)點，連接了所有非支配集節(jié)點，但是由于支配集中的節(jié)點之間不一定連通，還需要進行檢查。具體步驟如下：

1)將得到的鄰接矩陣，賦值求冪矩陣和冪次與矩陣，設初始值i=0。

2)判斷i是否小于等于N，(N為節(jié)點總數(shù)目)，若是，則轉(zhuǎn)到(3)；否則，轉(zhuǎn)到(7)。

3)當前用求冪矩陣與最初的矩陣相乘，將得到的新矩陣值賦給求冪矩陣。

4)將求冪矩陣和冪次與矩陣中的元素進行或運算，并賦值給冪次和矩陣。

5)判斷中每個元素是否都是非零元素，若是，則轉(zhuǎn)到(6)；否則，i++，轉(zhuǎn)到(2)。

6)該物聯(lián)網(wǎng)節(jié)點間是連通的，算法結束。

7)該物聯(lián)網(wǎng)節(jié)點間是非聯(lián)通的，算法結束。

如果支配集為非連通的，則需要通過向非連通支配集中加入盡量少的節(jié)點使支配集成為連通支配集。具體步驟如下：

1)判斷所構造的支配集是否是連通的。

2)計算每個非支配集內(nèi)的節(jié)點與支配集內(nèi)節(jié)點相連的度數(shù)。

3)選擇其中度數(shù)最大的節(jié)點并加入到支配集中。

4)判斷新構成的支配集是否連通，若連通，轉(zhuǎn)到(5)；否則，轉(zhuǎn)到(2)。

5)得到了連通支配集，算法結束。

1.4 感知節(jié)點數(shù)據(jù)傳輸過程

假設物聯(lián)網(wǎng)結構如圖1所示，其中節(jié)點A和G要協(xié)同進行數(shù)據(jù)處理工作。其中圓圈代表節(jié)點，節(jié)點之間的直線代表節(jié)點之間能夠通信。

圖1 物聯(lián)網(wǎng)結構圖

1)通過將物聯(lián)網(wǎng)抽象為鄰居矩陣，根據(jù)度數(shù)大小的比較選出物聯(lián)網(wǎng)中的支配集節(jié)點，涂為黑色，如圖2所示。

圖2 選出支配集節(jié)點

2)根據(jù)基于矩陣冪次和的連通性判斷算法，得出本物聯(lián)網(wǎng)不連通，將節(jié)點C，E移到支配集中，此時各節(jié)點之間實現(xiàn)連通。

3)如圖3，節(jié)點A向節(jié)點G發(fā)送連接消息，路徑為A—B—C—D—E—F—G。

4)節(jié)點G向A回復確認，路徑G—F—E—D—C—B—A。

圖3 節(jié)點A和G之間數(shù)據(jù)傳輸路徑

2 實驗評估與分析

通過在VC++6.0上運用連通算法，對于物聯(lián)網(wǎng)中的設備個數(shù)與生成的支配集中節(jié)點個數(shù)和建立連通所需時間的關系統(tǒng)計如表1所示。

通過表1可以看出：支配集中節(jié)點的個數(shù)和建立連通所需時間都隨著系統(tǒng)中設備的個數(shù)增多而線性增大。根據(jù)以上數(shù)據(jù)，測試環(huán)境中設備個數(shù)為1 000，對于不同的節(jié)點之間，通過中間件屏蔽異構特性，采用統(tǒng)一字符模式。假設節(jié)點每次發(fā)送數(shù)據(jù)量為1 kbps，通信帶寬256 kbps ，以文獻[9]中相關資料為基礎，通過統(tǒng)計物聯(lián)網(wǎng)中實時數(shù)據(jù)傳輸總量與兩種處理策略中傳輸總時間的關系，對兩者進行比較，結果如圖4。

表1 設備個數(shù)與支配集中節(jié)點個數(shù)和建立連通所需時間的關系

圖4 目前的物聯(lián)網(wǎng)和節(jié)點連通后對實時數(shù)據(jù)傳輸總時間比較

無線傳輸技術以Zig Bee為例，具有16條信道。假設物聯(lián)網(wǎng)中感知層設備能夠協(xié)同處理的數(shù)據(jù)占總數(shù)據(jù)量的1/10。以文獻[9]中關于擁堵發(fā)生概率分析為依據(jù)，對感知層設備連通前后的擁堵情況進行比較，結果如圖5。

圖5 感知層設備連通前后發(fā)生擁堵的概率比較

假設節(jié)點的初始能力為1 J[9]，采用文獻[10]中，接收1位數(shù)據(jù)所消耗的能量為Eelec=50 nJ/bit，空閑偵聽時節(jié)點消耗能量為0.88 mJ/s[10]，對建立連通前后節(jié)點剩余能量情況進行比較，結果圖6。

圖6 感知層設備連通前后節(jié)點能耗的比較

實驗證明:隨著物聯(lián)網(wǎng)規(guī)模和傳輸數(shù)據(jù)量的增加，通過連通算法將感知層設備連通，協(xié)同處理操作上不太復雜的實時數(shù)據(jù)，在連通建立過程中消耗了一定的時間和能量，但是連通建立之后，時間和能力的開銷都減小，總體上來看,通過犧牲少量的能耗節(jié)省了大量數(shù)據(jù)傳輸時間，有效減低了網(wǎng)絡擁堵。

3 結 論

本文將連通算法運用到物聯(lián)網(wǎng)感知層節(jié)點，使設備之間能夠協(xié)同工作，共同處理簡單的實時性任務。選取連通支配集節(jié)點，使所要經(jīng)過的節(jié)點數(shù)目盡量的少，節(jié)省了連通建立所需時間。在網(wǎng)絡中信息量增加的情況下，感知層節(jié)點連通，減少了數(shù)據(jù)傳輸?shù)臅r間和向網(wǎng)關傳輸?shù)臄?shù)據(jù)量，降低網(wǎng)絡負載，提高網(wǎng)絡效率。

參考文獻:

[1] Gustavorg,Mario Mo,Carlos D K.Early infrastructure of an Internet of things in spaces for learning[C]∥Eighth IEEE Internatio-nal Conference on Advanced Learning Technologies,2008:381-383.

[2] 周洪波.物聯(lián)網(wǎng)：技術、應用、標準和商業(yè)模式[M].2版.北京：電子工業(yè)出版社，2011.

[3] 姜 申.基于物聯(lián)網(wǎng)的智能電冰箱信息化設計[J].物聯(lián)網(wǎng)技術,2011(10)：36-40.

[4] 劉源潮.無線傳感器網(wǎng)絡拓撲中連通支配集的研究[D].蘇州：蘇州大學，2013.

[5] 張 軍.關于無線傳感器網(wǎng)絡的虛擬骨干網(wǎng)構造算法的研究[D].成都：電子科技大學,2011.

[6] 唐 勇，周明天.基于極大獨立集的最小連通支配集的分布式算法[J].電子學報，2007,35(5):868-874.

[7] Gao B,Yang Y,Ma H.A new distributed approximation algorithm for constructing minimum connected dominating set in wireless Ad Hoc networks[J].International Journal of Communication Systems,2005,18(8):743-762.

[8] 李宏波.物聯(lián)網(wǎng)傳輸及網(wǎng)絡可靠性研究[D].成都：電子科技大學，2012.

[9] 李巧勤，劉 明，楊 梅，等.負載相似節(jié)點分布解決傳感器網(wǎng)絡能量漏洞問題[J].軟件學報，2011,22(3):451-465.

[10] Medidi M,Zhou Y.Extending lifetime with differential duty cycles in wireless sensor networks[C]∥Proc of the IEEE Global Telecommunications Conf(GLOBECOM),2007:1033-1037.