基于物聯網感知層的節點連通算法*

李 娜， 薛建生

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

0 引 言

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

本文提出一種基于物聯網感知層的設備連通算法，為感知節點的協同工作提供必要的理論基礎。

1 基于感知層的節點連通算法

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

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

1.1 通過鄰接矩陣確定支配集節點

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

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

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

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

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

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

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

7)向基礎網絡中添加新設備，令N=物聯網系統中節點的個數，轉到(3)。

8)算法結束，得到物聯網的鄰接矩陣。

1.2 構造支配集

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

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

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

3)計算每個非黑色節點的活躍鄰居節點個數。

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

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

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

1.3 檢查與實現連通

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

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

2)判斷i是否小于等于N，(N為節點總數目)，若是，則轉到(3)；否則，轉到(7)。

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

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

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

6)該物聯網節點間是連通的，算法結束。

7)該物聯網節點間是非聯通的，算法結束。

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

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

2)計算每個非支配集內的節點與支配集內節點相連的度數。

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

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

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

1.4 感知節點數據傳輸過程

假設物聯網結構如圖1所示，其中節點A和G要協同進行數據處理工作。其中圓圈代表節點，節點之間的直線代表節點之間能夠通信。

圖1 物聯網結構圖

1)通過將物聯網抽象為鄰居矩陣，根據度數大小的比較選出物聯網中的支配集節點，涂為黑色，如圖2所示。

圖2 選出支配集節點

2)根據基于矩陣冪次和的連通性判斷算法，得出本物聯網不連通，將節點C，E移到支配集中，此時各節點之間實現連通。

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

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

圖3 節點A和G之間數據傳輸路徑

2 實驗評估與分析

通過在VC++6.0上運用連通算法，對于物聯網中的設備個數與生成的支配集中節點個數和建立連通所需時間的關系統計如表1所示。

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

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

圖4 目前的物聯網和節點連通后對實時數據傳輸總時間比較

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

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

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

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

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

3 結 論

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

參考文獻:

[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] 周洪波.物聯網：技術、應用、標準和商業模式[M].2版.北京：電子工業出版社，2011.

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

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

[5] 張 軍.關于無線傳感器網絡的虛擬骨干網構造算法的研究[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] 李宏波.物聯網傳輸及網絡可靠性研究[D].成都：電子科技大學，2012.

[9] 李巧勤，劉 明，楊 梅，等.負載相似節點分布解決傳感器網絡能量漏洞問題[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.