康志輝
(廈門(mén)軟件職業(yè)技術(shù)學(xué)院)
物聯(lián)網(wǎng)(Internet of things,IOT)是目前新興的研究熱點(diǎn),已作為一種重要技術(shù)出現(xiàn)在許多領(lǐng)域中,如交通、醫(yī)院、天氣檢測(cè)、大型商場(chǎng)等.同時(shí),隨著無(wú)線(xiàn)傳感網(wǎng)絡(luò)的改進(jìn),使得無(wú)線(xiàn)移動(dòng)設(shè)備如智能手機(jī)、平板電腦的銷(xiāo)量得到迅速增長(zhǎng),智能手機(jī)、平板電腦的數(shù)據(jù)交換和移動(dòng)性支持已能夠滿(mǎn)足WSN在這些領(lǐng)域下的集成和拓展.物聯(lián)網(wǎng)中的數(shù)據(jù)采集是通過(guò)無(wú)線(xiàn)傳感網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)進(jìn)行的.傳感器、執(zhí)行器、控制器和通信裝置共同構(gòu)成了無(wú)線(xiàn)傳感網(wǎng)絡(luò),該網(wǎng)絡(luò)集傳感與驅(qū)動(dòng)控制能力、計(jì)算能力、通信能力于一身,實(shí)現(xiàn)對(duì)物聯(lián)網(wǎng)中數(shù)據(jù)資源的獲取、計(jì)算和存儲(chǔ)[1].由這些微型傳感器構(gòu)成的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能夠?qū)崟r(shí)監(jiān)測(cè)、感知和采集物聯(lián)網(wǎng)中分布在各個(gè)區(qū)域中的監(jiān)測(cè)對(duì)象信息,實(shí)現(xiàn)對(duì)這些信息的加工與處理,并將其傳送給需要這些信息的用戶(hù).
對(duì)于物聯(lián)網(wǎng)中數(shù)據(jù)的采集,文獻(xiàn)[2]用多接收器在WSN中對(duì)數(shù)據(jù)采集進(jìn)行了研究.它們定義了一種近似模型嘗試最小化數(shù)據(jù)采集延遲,同時(shí)保證擁有常數(shù)因子的性能.文獻(xiàn)[3]將WSN中的數(shù)據(jù)采集階段歸為3類(lèi):部署階段、控制消息傳播階段和數(shù)據(jù)傳輸階段.每個(gè)階段都有它自己的特征和挑戰(zhàn).文獻(xiàn)[4]研究WSN數(shù)據(jù)采集中由不同種類(lèi)采集場(chǎng)景引起的容量挑戰(zhàn),其提出了一種可以控制該問(wèn)題的漸近上界方法.文獻(xiàn)[5]提出的方法采用網(wǎng)絡(luò)建模,預(yù)測(cè)網(wǎng)絡(luò)內(nèi)的能耗并嘗試優(yōu)化它.文獻(xiàn)[6-7]中嘗試解決數(shù)據(jù)采集的挑戰(zhàn).在極大程度上,該工作已經(jīng)聚焦于傳感器間的最大化數(shù)據(jù)采集量、最小化數(shù)據(jù)延遲或最小化能耗.但是,目前還沒(méi)有研究嘗試結(jié)合這些目標(biāo)來(lái)平衡這些沖突目標(biāo)的結(jié)果.
物聯(lián)網(wǎng)中數(shù)據(jù)采集過(guò)程中WSN的生存期與它的傳感器的生存期成正比關(guān)系.如果一個(gè)傳感器在電量耗盡時(shí)是一個(gè)關(guān)鍵節(jié)點(diǎn),即處于任何到達(dá)目的節(jié)點(diǎn)(數(shù)據(jù)接收器)的路由中心,它的損失會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)的損失.因此,對(duì)于任何動(dòng)態(tài)WSN,在保存或平衡傳感器的能量消耗時(shí),以一種可靠的方式來(lái)收集數(shù)據(jù)是很重要的.傳感器節(jié)點(diǎn)一般由傳感單元、數(shù)據(jù)處理單元、數(shù)據(jù)收發(fā)單元、電源單元等功能模塊組成,如圖1所示.
圖1 WSN節(jié)點(diǎn)構(gòu)成
通常,WSN由大量電池驅(qū)動(dòng)的傳感器組成,它們以隨機(jī)或受控制的方式在區(qū)域進(jìn)行部署[8].每個(gè)傳感器只需要尋找位于它通信范圍內(nèi)的相鄰節(jié)點(diǎn).所提數(shù)據(jù)接收器將會(huì)是一個(gè)接收感應(yīng)數(shù)據(jù)的移動(dòng)手持設(shè)備.該設(shè)備可以是一個(gè)便攜式設(shè)備(如手機(jī)、平板電腦等),可攜帶用來(lái)在感應(yīng)區(qū)周?chē)杉瘮?shù)據(jù).該設(shè)備可稱(chēng)為傳感器數(shù)據(jù)管理器(Sensor Data Manager,SDM).傳感器數(shù)據(jù)管理器具有需要的軟件和接口,以使得它表現(xiàn)為一個(gè)網(wǎng)絡(luò)調(diào)節(jié)器、數(shù)據(jù)接收管理器和傳感器分配協(xié)調(diào)器.該架構(gòu)的思想是它以最小的設(shè)備需求在需求環(huán)境下設(shè)置.這樣的動(dòng)態(tài)/移動(dòng)數(shù)據(jù)接收器的出現(xiàn),將會(huì)消除在不受控部署域下建立或完成特定傳感器的必要.WSN下的節(jié)點(diǎn)從它周?chē)?jié)點(diǎn)感應(yīng)數(shù)據(jù),將數(shù)據(jù)傳輸?shù)侥芰扛鼜?qiáng)的稱(chēng)為數(shù)據(jù)接收器的節(jié)點(diǎn),并聚合和分析感應(yīng)接收到的數(shù)據(jù).圖2展示了物聯(lián)網(wǎng)中的一種部署示例,SDM訂閱了WSN以及來(lái)自網(wǎng)絡(luò)的傳感器S1提供數(shù)據(jù)的請(qǐng)求.
圖2 WSN布局
啟發(fā)式算法(Heuristic Algorithm)是相對(duì)于最優(yōu)化算法提出的.啟發(fā)式算法定義如下:一個(gè)基于直觀(guān)或經(jīng)驗(yàn)構(gòu)造的算法,在可接受的花費(fèi)(指計(jì)算時(shí)間和空間)下給出待解決組合優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解,該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)[9].
該文設(shè)計(jì)了支持物聯(lián)網(wǎng)數(shù)據(jù)采集通信協(xié)議的最小開(kāi)銷(xiāo)啟發(fā)式算法進(jìn)行相關(guān)數(shù)據(jù)的采集.在該通信協(xié)議中,初始化階段是通過(guò)移動(dòng)Sink經(jīng)過(guò)執(zhí)行三輪移動(dòng)完成的.盡管絕大部分的耗時(shí)耗能任務(wù)都是由移動(dòng)Sink完成的,但過(guò)長(zhǎng)的初始化操作依然會(huì)給物聯(lián)網(wǎng)的數(shù)據(jù)采集帶來(lái)低效率.為此,本節(jié)給出一種最小開(kāi)銷(xiāo)啟發(fā)式算法,通過(guò)該算法實(shí)現(xiàn)物聯(lián)網(wǎng)中各個(gè)成員節(jié)點(diǎn)通過(guò)分布式的方式獨(dú)立進(jìn)行目的Sub-sink的選擇,通過(guò)目的Sub-sink的選擇實(shí)現(xiàn)物聯(lián)網(wǎng)中各個(gè)成員和Sub-shik之間的優(yōu)化匹配,進(jìn)而降低整個(gè)網(wǎng)絡(luò)的能量消耗.最小開(kāi)銷(xiāo)啟發(fā)式算法的具體過(guò)程如下:
Step1:在移動(dòng)Sink的第一輪移動(dòng)過(guò)程中,首先選中靠近軌道的傳感器節(jié)點(diǎn).
Step2:整個(gè)物聯(lián)網(wǎng)范圍內(nèi)最短路徑樹(shù)的建立由Sub-sink發(fā)起;
Step3:各Sub-sink之間通信的起止時(shí)間通過(guò)移動(dòng)Sink進(jìn)行記錄.該起止時(shí)間用于計(jì)算物聯(lián)網(wǎng)中各Subsink點(diǎn)之間的有效的通信時(shí)間以及各個(gè)成員對(duì)數(shù)據(jù)量的需求;
Step4:在移動(dòng)Sink的第二輪移動(dòng)過(guò)程中,移動(dòng)Sink將各個(gè)成員對(duì)數(shù)據(jù)量需求的計(jì)算結(jié)果進(jìn)行物聯(lián)網(wǎng)中相應(yīng)監(jiān)測(cè)區(qū)域的擴(kuò)散;
Step5:物聯(lián)網(wǎng)中每個(gè)成員節(jié)點(diǎn)通過(guò)計(jì)算獲得到達(dá)所有Sub-sink點(diǎn)的最短跳數(shù);
Step6:根據(jù)最短跳數(shù)獲得各個(gè)Sub-sink點(diǎn)的成員數(shù)量需求;
Step7:各個(gè)成員節(jié)點(diǎn)通過(guò)運(yùn)行最小開(kāi)銷(xiāo)分布式算法進(jìn)行合適的Sub-sink的選擇;
Step8:通過(guò)確定的Sub-sink實(shí)現(xiàn)物聯(lián)網(wǎng)中數(shù)據(jù)的采集與傳輸;
Step9:數(shù)據(jù)采集是否結(jié)束,若是,轉(zhuǎn)Step 10,否則,轉(zhuǎn)Step 3;
Step10:算法結(jié)束.
在最小開(kāi)銷(xiāo)分布式算法中,通過(guò)引入權(quán)重值α來(lái)計(jì)算各個(gè)Sub-sink的優(yōu)先級(jí),該優(yōu)先級(jí)體現(xiàn)了各個(gè)Sub-sink被選作為最終目的地的概率大小.若α值較小,則說(shuō)明跳數(shù)信息比成員數(shù)量需求信息的優(yōu)先級(jí)高.具體的最小開(kāi)銷(xiāo)分布式算法見(jiàn)表1.
該文的最小開(kāi)銷(xiāo)啟發(fā)式算法僅需要兩輪Sink移動(dòng)周期即可完成數(shù)據(jù)采集的初始化操作,而且與集中式算法相比,其協(xié)議效率更好.除此之外,該文最小開(kāi)銷(xiāo)啟發(fā)式算法中目的Subsink的選擇算法較遺傳算法更為簡(jiǎn)單.通過(guò)該文算法,為了適應(yīng)物聯(lián)網(wǎng)數(shù)據(jù)采集節(jié)點(diǎn)的失效或新增的數(shù)據(jù)采集節(jié)點(diǎn)帶來(lái)的無(wú)線(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變,可以通過(guò)讓部分成員節(jié)點(diǎn)獨(dú)立運(yùn)行,該文的最小開(kāi)銷(xiāo)啟發(fā)式算法方式來(lái)獲取臨時(shí)可用的Sub-sink.
表1 最小開(kāi)銷(xiāo)分布式算法(對(duì)任意成員)
該文的仿真平臺(tái)是通過(guò)SimJava開(kāi)發(fā)的,相應(yīng)的仿真實(shí)驗(yàn)是通過(guò)該平臺(tái)完成的[10].通過(guò)該仿真平臺(tái)進(jìn)行了該文提出的最小開(kāi)銷(xiāo)數(shù)據(jù)采集方法與兩種基準(zhǔn)方法:隨機(jī)法和貪心能量感知法進(jìn)行了對(duì)比與評(píng)估,證明了該文方法的有效性.
隨機(jī)法是一種遍歷和聚合來(lái)自物聯(lián)網(wǎng)中WSN數(shù)據(jù)的簡(jiǎn)單隨機(jī)數(shù)據(jù)采集協(xié)議,該種方式是一種簡(jiǎn)單的基準(zhǔn)方法,它無(wú)需任何的數(shù)據(jù)交換或者信息共享.該文的最小開(kāi)銷(xiāo)啟發(fā)式算法與隨機(jī)法相比,更有助于計(jì)算所提方法的額外開(kāi)銷(xiāo).第二種比較的數(shù)據(jù)采集方法是貪心能量感知算法,該算法嘗試使用最短路徑算法來(lái)收集物聯(lián)網(wǎng)中的感應(yīng)數(shù)據(jù).在該方法中,該協(xié)議將會(huì)確保遍歷路徑中擁有最高電池電量的節(jié)點(diǎn),以選擇到達(dá)SDM的最短路徑.該方法也被稱(chēng)之為貪心能量感知(Greedy Power Aware,GPA)數(shù)據(jù)采集器.該貪心算法將會(huì)提供整個(gè)物聯(lián)網(wǎng)中WSN可能能耗的最大值,因?yàn)樗ǔL試選擇擁有最大功率級(jí)的路徑.
圖3展示了針對(duì)數(shù)據(jù)采集成功率三種方法的仿真結(jié)果.通過(guò)圖3可以看出,在三種方法中貪心能量感知方法表現(xiàn)最好,作為一種純粹的數(shù)據(jù)采集方法,貪心能量感知法通過(guò)能找到最短路徑(最小延遲).該文所提出的最小開(kāi)銷(xiāo)啟發(fā)式算法比貪心能量感知法稍差(特別當(dāng)?shù)屯ㄐ帕亢蜆O端通信量時(shí))但是優(yōu)于隨機(jī)方法.
圖3 三種方法針對(duì)物聯(lián)網(wǎng)數(shù)據(jù)采集成功率的仿真對(duì)比
圖4顯示了針對(duì)網(wǎng)絡(luò)中每個(gè)傳感器節(jié)點(diǎn)的平均能耗以及能量消耗速率三種方法的仿真實(shí)驗(yàn)結(jié)果.通過(guò)圖4可以看出,貪心能量感知模型優(yōu)于嘗試選擇擁有最高能量級(jí)的最短路徑來(lái)最大化物聯(lián)網(wǎng)中傳感器電池在數(shù)據(jù)采集中的使用期限,因此,其能力消耗速率是比較高的,但是優(yōu)于隨機(jī)的方法.該文所提的基于最小開(kāi)銷(xiāo)啟發(fā)式算法在三種方法中是表現(xiàn)最好的.該文方法是通過(guò)一種受控啟發(fā)式算法進(jìn)行執(zhí)行的,因此在WSN上不會(huì)產(chǎn)生額外開(kāi)銷(xiāo).另外需要注意的是,貪心能量感知法在任何時(shí)間節(jié)點(diǎn)都需要WSN的一個(gè)全局視圖.這表示拓展性和執(zhí)行開(kāi)銷(xiāo)將會(huì)是該方法的一個(gè)主要問(wèn)題.
圖4 三種方法針對(duì)能量消耗速率的仿真對(duì)比
圖5顯示了三種方法針對(duì)物聯(lián)網(wǎng)中數(shù)據(jù)采集時(shí)的通信負(fù)載的仿真實(shí)驗(yàn)對(duì)比.該仿真對(duì)每次數(shù)據(jù)采集所需要的通信和執(zhí)行開(kāi)銷(xiāo)進(jìn)行對(duì)比.該測(cè)量值包括了物聯(lián)網(wǎng)數(shù)據(jù)采集傳感器節(jié)點(diǎn)間為了更新WSN關(guān)于每個(gè)節(jié)點(diǎn)的統(tǒng)計(jì)信息的數(shù)據(jù)交換,以及在每個(gè)節(jié)點(diǎn)間執(zhí)行路由選擇算法的開(kāi)銷(xiāo)總和.與貪心能量感知方法相比,該文所提出的最小開(kāi)銷(xiāo)啟發(fā)式算法在數(shù)據(jù)采集時(shí)的通信開(kāi)銷(xiāo)隨著數(shù)據(jù)采集頻率的增長(zhǎng)是有彈性的.而,貪心能量感知的通信開(kāi)銷(xiāo)隨著通信量增長(zhǎng)而呈指數(shù)增長(zhǎng),因此其能量消耗是巨大的.隨機(jī)法的能量消耗介于兩種方法之間.該仿真顯示了所提啟發(fā)式算法的真實(shí)優(yōu)點(diǎn).
圖5 三種方法針對(duì)數(shù)據(jù)采集節(jié)點(diǎn)的通信開(kāi)銷(xiāo)的仿真對(duì)比
基于物聯(lián)網(wǎng)的數(shù)據(jù)采集使得設(shè)備的位置通過(guò)網(wǎng)絡(luò)以一種動(dòng)態(tài)的方式進(jìn)行數(shù)據(jù)分享.物聯(lián)網(wǎng)中無(wú)線(xiàn)網(wǎng)絡(luò)的不穩(wěn)定無(wú)線(xiàn)連接和有限的能量資源,帶來(lái)了數(shù)據(jù)采集的新的挑戰(zhàn).物聯(lián)網(wǎng)中的數(shù)據(jù)采集是挑戰(zhàn)的核心,需要將采集到的各種數(shù)據(jù)信息進(jìn)行聚集、融合并經(jīng)過(guò)路由器傳送到最終的目的節(jié)點(diǎn).數(shù)據(jù)感應(yīng)和數(shù)據(jù)路由的活動(dòng)會(huì)對(duì)傳感器的電池能量造成損失,這將導(dǎo)致WSN的重新組合.該文所提出的最小開(kāi)銷(xiāo)啟發(fā)式算法是一種適應(yīng)性數(shù)據(jù)采集方法,僅需要兩輪Sink移動(dòng)周期即可完成數(shù)據(jù)采集的初始化操作,而且與集中式算法相比,其協(xié)議效率更好.該方法相對(duì)于傳統(tǒng)的隨機(jī)法和貪心能量感知法具有更低的開(kāi)銷(xiāo).下一步將圍著這網(wǎng)絡(luò)傳感網(wǎng)中的感應(yīng)、處理、通信和行動(dòng)的合作和協(xié)同展開(kāi)研究.
[1]蔣凌云,孫力娟,王汝傳,等.移動(dòng)無(wú)線(xiàn)傳感網(wǎng)能量時(shí)延約束的自適應(yīng)路由及性能評(píng)估[J].電子學(xué)報(bào),2013,40(12):2495-2500.
[2]Chen Sixia,et al.Data collection with multiple sinks in wireless sensor networks[J].Wireless Algorithms,Systems,and Applications.Springer Berlin Heidelberg,2009,5682(13):284-294.
[3]Mainetti L,Patrono,Vilei A.Evolution of wireless sensor networks towards the internet of things:A survey[J].Software,Telecommunications and Computer Networks,2011,19(15):1-6.
[4]Fan Xiuwei,Lei Jianshu.一種輕量級(jí)的 WSN認(rèn)證和密鑰協(xié)商方案[J].計(jì)算機(jī)工程,2013,39(3):146-151.
[5]Del Cid P J,Matthys N,Hughes D,et al.Resource management middleware to support self managing wireless sensor networks[J].2010 Fourth IEEE International Conference on,2010,10(4):251–255.
[6]Awan A,Jagannathan S,Grama A Y.Scalable Data Collection in Dense Wireless Sensor Networks[J].2007,7(18):1-9.
[7]Liang Zhang,Ye Qiang,Cheng Jie,et al.Fault- tolerant scheduling for data collection in wireless sensor networks[J].In GlobalCommunicationsConference(GLOBECOM),2012,10(3):5345–5349.
[8]王翥,呂翠翠,陳建輝.基于貪婪算法無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中繼節(jié)點(diǎn)布局的研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(2):485-487.
[9]王景存,張曉彤,陳彬,等.一種基于 Dijkstra算法的啟發(fā)式最優(yōu)路徑搜索算法[J].北京科技大學(xué)學(xué)報(bào),2007,29(3):346-350.
[10]Kreutzer W,Hopkins J,Van Mierlo M.SimJAVA-a framework for modeling queueing networks in Java[C]//Proceedings of the 29th conference on Winter simulation.IEEE Computer Society,1997.483–488.