李 娜， 薛建生

(遼寧大學(xué)，遼寧 沈陽(yáng) 110036)

0 引 言

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

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

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

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

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

1.1 通過(guò)鄰接矩陣確定支配集節(jié)點(diǎn)

物聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)可以通過(guò)無(wú)向圖表示，各個(gè)節(jié)點(diǎn)之間的連接情況能夠用鄰接矩陣的方式表示出來(lái)。鄰接矩陣生成具體步驟如下：

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

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

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

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

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

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

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

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

1.2 構(gòu)造支配集

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

1)通過(guò)計(jì)算每行或每列的1的個(gè)數(shù)可以得到節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)。

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

3)計(jì)算每個(gè)非黑色節(jié)點(diǎn)的活躍鄰居節(jié)點(diǎn)個(gè)數(shù)。

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

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

6)算法結(jié)束，輸出結(jié)果，得到一個(gè)支配集。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 感知節(jié)點(diǎn)數(shù)據(jù)傳輸過(guò)程

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

圖1 物聯(lián)網(wǎng)結(jié)構(gòu)圖

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

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

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

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

4)節(jié)點(diǎn)G向A回復(fù)確認(rèn)，路徑G—F—E—D—C—B—A。

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

2 實(shí)驗(yàn)評(píng)估與分析

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

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

表1 設(shè)備個(gè)數(shù)與支配集中節(jié)點(diǎn)個(gè)數(shù)和建立連通所需時(shí)間的關(guān)系

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

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

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

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

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

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

3 結(jié) 論

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

參考文獻(xiàn):

[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)：技術(shù)、應(yīng)用、標(biāo)準(zhǔn)和商業(yè)模式[M].2版.北京：電子工業(yè)出版社，2011.

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

[4] 劉源潮.無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渲羞B通支配集的研究[D].蘇州：蘇州大學(xué)，2013.

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

[6] 唐 勇，周明天.基于極大獨(dú)立集的最小連通支配集的分布式算法[J].電子學(xué)報(bào)，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)絡(luò)可靠性研究[D].成都：電子科技大學(xué)，2012.

[9] 李巧勤，劉 明，楊 梅，等.負(fù)載相似節(jié)點(diǎn)分布解決傳感器網(wǎng)絡(luò)能量漏洞問(wèn)題[J].軟件學(xué)報(bào)，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.