最小開(kāi)銷(xiāo)啟發(fā)式算法在物聯(lián)網(wǎng)數(shù)據(jù)采集的研究*

康志輝

(廈門(mén)軟件職業(yè)技術(shù)學(xué)院)

0 引言

物聯(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é)果.

1 物聯(lián)網(wǎng)數(shù)據(jù)采集設(shè)備及過(guò)程

物聯(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布局

2 最小開(kāi)銷(xiāo)啟發(fā)式算法

啟發(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ì)任意成員)

3 仿真研究

該文的仿真平臺(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ì)比

4 結(jié)束語(yǔ)

基于物聯(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.