• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    一種智能電網(wǎng)中基于優(yōu)先充電機(jī)制的節(jié)能匯聚路由方案

    2018-08-17 00:27:46
    計(jì)算機(jī)工程 2018年8期
    關(guān)鍵詞:復(fù)雜度優(yōu)先路由

    (南京信息工程大學(xué) 計(jì)算機(jī)與軟件學(xué)院,南京 210044)

    0 概述

    在智能電網(wǎng)中,安全性、可靠性和高效性是電力服務(wù)的目標(biāo),無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)在監(jiān)測(cè)范圍、成本、監(jiān)測(cè)粒度、魯棒性等方面都能很好地滿(mǎn)足需求,但其存在無(wú)線傳感器節(jié)點(diǎn)電池能量受限的問(wèn)題。要將無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用于智能電網(wǎng)中,就需要研究能量效率和能量捕獲的相關(guān)技術(shù)。

    能量捕獲技術(shù)對(duì)智能電網(wǎng)的長(zhǎng)期發(fā)展具有重要意義。但智能電網(wǎng)中的主電源很難直接被無(wú)線傳感器節(jié)點(diǎn)使用。目前有很多文獻(xiàn)針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能問(wèn)題提出了解決方案。在能量捕獲方面的研究包括利用風(fēng)能、太陽(yáng)能、震動(dòng)能量、射頻(Radio Frequency,RF)能量等實(shí)現(xiàn)能量轉(zhuǎn)換[1-4]??紤]到能量轉(zhuǎn)換的便利性和無(wú)線傳感器節(jié)點(diǎn)的特性,RF能量捕獲技術(shù)理論上可以為節(jié)點(diǎn)永久性供能,對(duì)能量捕獲中的溢出情況進(jìn)行監(jiān)測(cè)[5],提高智能電網(wǎng)的自主性并用于對(duì)其進(jìn)行長(zhǎng)期監(jiān)測(cè)[6]。

    在利用RF給無(wú)線傳感器網(wǎng)絡(luò)充電的研究方面,文獻(xiàn)[7]研究了RFID標(biāo)簽充電時(shí)最小化網(wǎng)絡(luò)中的靜態(tài)閱讀器數(shù)量問(wèn)題。文獻(xiàn)[8]論述了在RF充電器訪問(wèn)每個(gè)節(jié)點(diǎn)時(shí),如何實(shí)現(xiàn)該類(lèi)功率發(fā)射器的最優(yōu)路徑問(wèn)題。在文獻(xiàn)[9]研究的移動(dòng)充電器方案中,在有魯棒性充電要求時(shí)實(shí)現(xiàn)了訪問(wèn)移動(dòng)充電器的地標(biāo)數(shù)最小化。以上文獻(xiàn)尚未綜合考慮數(shù)據(jù)傳輸效率和RF能量捕獲的優(yōu)先機(jī)制問(wèn)題。

    在RF能量捕獲技術(shù)中,無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的部署及傳輸中的路由選擇會(huì)影響到能量捕獲及數(shù)據(jù)傳輸效果。在多跳路由拓?fù)渲?每個(gè)中繼節(jié)點(diǎn)都會(huì)因?yàn)樨?fù)載增加而受影響,能量開(kāi)銷(xiāo)將比其源頭節(jié)點(diǎn)更大,因此,需要為其設(shè)計(jì)能量?jī)?yōu)化策略。構(gòu)建數(shù)據(jù)匯聚樹(shù)可以讓無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸更加節(jié)能和高效,尤其是在節(jié)點(diǎn)需要通過(guò)RF捕能方式來(lái)充電的場(chǎng)合,更需要對(duì)路由進(jìn)行優(yōu)化。

    在WSN中利用數(shù)據(jù)匯聚來(lái)延長(zhǎng)網(wǎng)絡(luò)壽命是一種常見(jiàn)的優(yōu)化方法[10],這類(lèi)方法主要分為2類(lèi):基于樹(shù)型結(jié)構(gòu)的方法和基于簇狀結(jié)構(gòu)的方法。前者的典型案例是TAG協(xié)議,后者的典型案例是LEACH或改進(jìn)的LEACH算法[11-12]。另外還可以利用數(shù)據(jù)匯聚樹(shù)來(lái)提升服務(wù)質(zhì)量,如在保持網(wǎng)絡(luò)壽命優(yōu)勢(shì)的同時(shí)減小數(shù)據(jù)延遲[13-14]。如何在能量捕獲過(guò)程中構(gòu)建數(shù)據(jù)匯聚樹(shù),文獻(xiàn)[15]提出了一種提高網(wǎng)絡(luò)生存期的數(shù)據(jù)匯聚樹(shù)構(gòu)造策略,但沒(méi)有考慮數(shù)據(jù)傳輸率和充電的實(shí)際情況。本文在此基礎(chǔ)上,針對(duì)智能電網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)布網(wǎng)特點(diǎn),設(shè)計(jì)一種基于優(yōu)先充電機(jī)制的數(shù)據(jù)匯聚型節(jié)能路由方案,綜合考慮路由優(yōu)化、RF充電與數(shù)據(jù)傳輸率之間的關(guān)系。

    1 網(wǎng)絡(luò)模型

    在無(wú)線能量捕獲的能量轉(zhuǎn)換中,徑損主要取決于信號(hào)頻率。為了簡(jiǎn)化問(wèn)題,本文所討論的智能電網(wǎng)監(jiān)測(cè)網(wǎng)絡(luò)將采用自由空間徑損模型。該模型是無(wú)線電波傳播最簡(jiǎn)單的模型,無(wú)需考慮衰減和多徑等問(wèn)題,比較適合無(wú)線路由建模。在直徑R的圓形范圍內(nèi),相應(yīng)的接收功率為:

    其中,Gr是接收方的線性天線增益,PtGt是發(fā)射功率,λ是波長(zhǎng)。實(shí)際捕獲到的功率是接收功率經(jīng)過(guò)一定的電路損耗之后的函數(shù)。

    從式(1)可以看出功率傳輸范圍很小,僅利用蜂窩基站(在智能電網(wǎng)中是主電源降壓后的設(shè)備)補(bǔ)充能量,將不足以為傳感器節(jié)點(diǎn)充電。因此,除了主供電設(shè)備外,本文將進(jìn)一步利用移動(dòng)式備選供能節(jié)點(diǎn)為匯聚路由中數(shù)據(jù)傳輸任務(wù)較重的捕能節(jié)點(diǎn)提供優(yōu)先充電,這些供能節(jié)點(diǎn)的成本比主設(shè)備(基站)低得多。在本文所提出的支撐樹(shù)節(jié)能路由算法中,這些供能節(jié)點(diǎn)不參與數(shù)據(jù)匯聚樹(shù)的構(gòu)建和數(shù)據(jù)傳輸。

    優(yōu)先充電網(wǎng)絡(luò)模型如圖1所示,網(wǎng)絡(luò)包括一個(gè)主電源(扮演基站B的角色)、能量轉(zhuǎn)換設(shè)備,這里扮演供能節(jié)點(diǎn)(Energy Providing Node,EPN)的角色;傳輸節(jié)點(diǎn)包括捕能節(jié)點(diǎn)(Energy Harvesting Node,EHN)和普通節(jié)點(diǎn)(Ordinary Node,ON),其中供能節(jié)點(diǎn)僅與捕能節(jié)點(diǎn)通信。由于備選供能節(jié)點(diǎn)不需要提前在全網(wǎng)部署且分配靈活,因此在圖1中并未體現(xiàn)。

    圖1 優(yōu)先充電網(wǎng)絡(luò)模型

    每個(gè)EHN至少配置一個(gè)EPN進(jìn)行充電,對(duì)于路由中承擔(dān)更大量數(shù)據(jù)傳輸任務(wù)的EHN,增加PEPN實(shí)現(xiàn)優(yōu)先充電。該P(yáng)EPN為移動(dòng)式工作,可根據(jù)匯聚樹(shù)中的路由變化及數(shù)據(jù)傳輸率情況而做相應(yīng)的位置調(diào)整,實(shí)現(xiàn)基于動(dòng)態(tài)優(yōu)先充電的節(jié)能匯聚路由。本文利用ILP模型實(shí)現(xiàn)全網(wǎng)ON節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)最小化,假設(shè)所有的供能節(jié)點(diǎn)發(fā)射范圍都一樣。

    2 節(jié)能路由方案

    利用上述3類(lèi)節(jié)點(diǎn),即普通節(jié)點(diǎn)(ON)、供能節(jié)點(diǎn)(EPN)和捕能節(jié)點(diǎn)(EHN),首先在網(wǎng)絡(luò)中部署初始的ON和EHN,在EHN周?chē)O(shè)置至少一個(gè)EPN。采用整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)和最小權(quán)重捕獲支撐樹(shù)路由算法實(shí)現(xiàn)節(jié)能的數(shù)據(jù)傳輸。這里的ILP即最小-最大模型,用以實(shí)現(xiàn)普通節(jié)點(diǎn)的下游節(jié)點(diǎn)上限的最小化(數(shù)據(jù)匯聚自下游節(jié)點(diǎn)往上游節(jié)點(diǎn))。最小權(quán)重捕獲支撐樹(shù)路由算法旨在加速匯聚樹(shù)構(gòu)建的速度,并降低其復(fù)雜度。對(duì)構(gòu)建好的匯聚拓樸樹(shù)再進(jìn)行回溯,直至找到最優(yōu)匯聚拓樸樹(shù)。為了實(shí)現(xiàn)優(yōu)化充電,對(duì)其中的重載EHN,通過(guò)增加EPN提高捕能的便利性和有效性。

    2.1 初始模型

    匯聚路由在文獻(xiàn)[15]的基礎(chǔ)上改進(jìn)。本文簡(jiǎn)化了匯聚過(guò)程,并增加優(yōu)先充電環(huán)節(jié)。匯聚路由主要基于圖論方法,構(gòu)建一棵最小權(quán)重支撐樹(shù),要求路由中不含閉合環(huán),因此,需要實(shí)現(xiàn)從帶環(huán)到去環(huán)的過(guò)程。

    構(gòu)建的數(shù)據(jù)匯聚樹(shù)基本模型如圖2所示,其中不包含EPN和PEPN。

    圖2 充電型數(shù)據(jù)匯聚樹(shù)基本模型

    該模型描述為:在網(wǎng)絡(luò)中一共有K個(gè)節(jié)點(diǎn),其中基站為B,整個(gè)樹(shù)中有n個(gè)頂點(diǎn),最多有n-1條邊。而匯聚路由中進(jìn)入B的數(shù)據(jù)流有K-1條(這也要求構(gòu)建的樹(shù)中有向邊的數(shù)量不應(yīng)該小于該數(shù))邊集合M中所有的邊是由2個(gè)能直接通信的節(jié)點(diǎn)之間的連線構(gòu)成。EHN節(jié)點(diǎn)集H?N,ON節(jié)點(diǎn)集O,也即N{H∪S}。為了簡(jiǎn)化問(wèn)題,EPN節(jié)點(diǎn)不在N中體現(xiàn),也即數(shù)據(jù)匯聚樹(shù)中并不出現(xiàn)EPN。

    由于各捕能節(jié)點(diǎn)的傳輸數(shù)據(jù)率不同,對(duì)能量需求不同,因此在構(gòu)建好的匯聚樹(shù)中,在較重傳輸任務(wù)的捕能節(jié)點(diǎn)旁增加一個(gè)備選的供能節(jié)點(diǎn)。該供能節(jié)點(diǎn)僅為捕能節(jié)點(diǎn)提供RF能量,對(duì)匯聚路由不產(chǎn)生影響。構(gòu)建了該拓?fù)錁?shù)后,圖2可以抽象為有向拓?fù)湫问?其中忽略了非直接通信的節(jié)點(diǎn)之間的邊。

    假設(shè)每個(gè)待匯聚拓?fù)錁?shù)中的節(jié)點(diǎn)可以處理從其子節(jié)點(diǎn)接收到的全部數(shù)據(jù)包,在此基礎(chǔ)上再生成一個(gè)自身的數(shù)據(jù)包。為了節(jié)省能量,節(jié)點(diǎn)僅在有數(shù)據(jù)收發(fā)活動(dòng)時(shí)才激活射頻。因此,子節(jié)點(diǎn)的數(shù)量對(duì)網(wǎng)絡(luò)壽命會(huì)產(chǎn)生重要影響。考慮到EHN節(jié)點(diǎn)可以進(jìn)行RF能量補(bǔ)充,網(wǎng)絡(luò)壽命主要受ON節(jié)點(diǎn)的影響,需要在全網(wǎng)中實(shí)現(xiàn)ON節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)最小化。

    基于IPL的匯聚路由(Aggressive Routing-IPL,AR-ILP)旨在減少ON的子節(jié)點(diǎn)數(shù),以增加WSN壽命。AR-ILP模型構(gòu)建如下:模型的有向拓?fù)鋱D源于基站B,每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)重,定義ON權(quán)重為1,其他節(jié)點(diǎn)(EHN節(jié)點(diǎn)和B)權(quán)重為0。設(shè)置一個(gè)決策布爾變量X,若節(jié)點(diǎn)i(不含B)選擇j作為父節(jié)點(diǎn)(即數(shù)據(jù)匯聚的上游節(jié)點(diǎn)),則Xij=1。整型流矩陣Fij表示從i到j(luò)的數(shù)據(jù)流構(gòu)成的矩陣,若Xij為0,則Fij亦為0。通過(guò)Fij進(jìn)行優(yōu)化后將獲得一個(gè)連接拓?fù)?。假定每個(gè)節(jié)點(diǎn)(除B之外)有且僅有一個(gè)父節(jié)點(diǎn),在WSN中所有ON節(jié)點(diǎn)的孩子數(shù)最少可以表示為:

    s.t. ?(i,j)∈M,i∈N-{S},0≤Fij≤K-1

    (2)

    其中,n(j)是節(jié)點(diǎn)i射頻范圍內(nèi)的所有通信節(jié)點(diǎn)。

    假設(shè)到基站B的所有數(shù)據(jù)流有K-1條,從基站B只有流入的數(shù)據(jù)流,沒(méi)有流出的數(shù)據(jù)流,B為整棵樹(shù)的根。每個(gè)數(shù)據(jù)流都有單一的傳輸方向,在樹(shù)中,每個(gè)最下游的葉節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包,中繼節(jié)點(diǎn)在收到的數(shù)據(jù)包基礎(chǔ)上再加一個(gè)包,最終所有數(shù)據(jù)到達(dá)B,WSN的數(shù)據(jù)傳輸基于該匯聚樹(shù)完成路由過(guò)程。

    2.2 基于優(yōu)先充電機(jī)制的節(jié)能路由算法

    為了進(jìn)一步加速該匯聚樹(shù)過(guò)程,可以讓B發(fā)揮更大的作用,基于該匯聚樹(shù)根B構(gòu)建反向支撐樹(shù),數(shù)據(jù)流的方向與數(shù)據(jù)傳輸方向相反,采取從B起始一直到葉節(jié)點(diǎn)的方式。在構(gòu)建反向匯聚支撐樹(shù)的過(guò)程中,利用反向拓?fù)淇刂?、?quán)重控制和破環(huán)法使ON節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)最小化過(guò)程更快。其基本思路為:按照與匯聚樹(shù)中數(shù)據(jù)流相反的方向,從B出發(fā),把進(jìn)入B的邊全部去掉,進(jìn)一步找出其他每個(gè)節(jié)點(diǎn)的入邊和出邊。邊的選擇根據(jù)節(jié)點(diǎn)的權(quán)重進(jìn)行。B和EHN節(jié)點(diǎn)的權(quán)重為0,ON節(jié)點(diǎn)的權(quán)重為1。有向邊的權(quán)重設(shè)為出發(fā)節(jié)點(diǎn)的權(quán)重。每個(gè)節(jié)點(diǎn)選擇最小權(quán)重的入邊來(lái)構(gòu)建樹(shù)(使ON及EHN節(jié)點(diǎn)更多地選擇B和EHN節(jié)點(diǎn)作為父節(jié)點(diǎn))。這樣便構(gòu)建起初始時(shí)的反向匯聚支撐樹(shù),同時(shí)檢查其中是否有環(huán)路(環(huán)主是由NHN節(jié)點(diǎn)造成,因其既有入邊,又有出邊)。若存在環(huán)路,則利用將涉及環(huán)路的EHN節(jié)點(diǎn)合并的方式將環(huán)打破,再重新確定樹(shù)中的邊(規(guī)則與前文一樣)。檢查新圖中的含環(huán)情況,若有環(huán),繼續(xù)用合并EHN節(jié)點(diǎn)的方式破環(huán),直到樹(shù)中無(wú)環(huán)為止。最后把合并節(jié)點(diǎn)拆開(kāi),再次確定樹(shù)中的邊,形成無(wú)環(huán)的反向支撐樹(shù)。將這棵反向匯聚支撐樹(shù)再恢復(fù)成正常數(shù)據(jù)傳輸?shù)膮R聚樹(shù)只要將反向支撐樹(shù)中邊的方向取反即可。

    在上述加速的反向支撐樹(shù)匯聚路由中,個(gè)別ON的子節(jié)點(diǎn)數(shù)可能會(huì)不穩(wěn)定,其原因是在建樹(shù)過(guò)程中最初基于最小權(quán)重選擇邊的過(guò)程不唯一,而破環(huán)過(guò)程中合并節(jié)點(diǎn)時(shí)基于最小權(quán)重選擇邊的過(guò)程也不唯一。因?yàn)樵跈?quán)重相等且存在有向邊時(shí),并沒(méi)有限定必須選擇哪個(gè)ON節(jié)點(diǎn)作為父節(jié)點(diǎn),這就導(dǎo)致了一些ON節(jié)點(diǎn)的孩子數(shù)超過(guò)1。因此,對(duì)這種非最優(yōu)拓?fù)錁?shù)需要反復(fù)進(jìn)行邊的優(yōu)化選擇操作,直至找到最優(yōu)數(shù)據(jù)匯聚路由。該加速過(guò)程是本文的重要?jiǎng)?chuàng)新點(diǎn),能夠給節(jié)能處理帶來(lái)更高的效率。

    反向支撐樹(shù)匯聚路由原始拓?fù)淙鐖D3所示。其中,EHN節(jié)點(diǎn)用雙線圓圈表示,B為基站,其他節(jié)點(diǎn)為ON節(jié)點(diǎn)。

    圖3 反向支撐樹(shù)匯聚路由原始拓?fù)?/p>

    下面結(jié)合圖例給出具體的算法步驟。

    步驟1在所有ON節(jié)點(diǎn)、EHN節(jié)點(diǎn)、B節(jié)點(diǎn)構(gòu)成的無(wú)向圖中構(gòu)造出帶權(quán)有向圖,并在其中找到每個(gè)節(jié)點(diǎn)。權(quán)重設(shè)置為:ON節(jié)點(diǎn)權(quán)重為1,EHN節(jié)點(diǎn)及B節(jié)點(diǎn)權(quán)重為0,若u為ON節(jié)點(diǎn),以u(píng)為起點(diǎn)、連接u和v的有向邊權(quán)重設(shè)置為w[u,v]=1,若u為EHN節(jié)點(diǎn)或B節(jié)點(diǎn),則對(duì)應(yīng)w[u,v]=0。這種設(shè)置保證了從EHN和B節(jié)點(diǎn)出發(fā)的有向邊權(quán)重為0,更有利于ON將其選為入射邊,因?yàn)閿?shù)據(jù)匯聚樹(shù)基于最小權(quán)重選擇有向邊。在構(gòu)建反向支撐匯聚樹(shù)的過(guò)程中,基站B的優(yōu)先級(jí)最高,其他節(jié)點(diǎn)選擇入射邊時(shí)以B作為入射邊首選。作為整棵樹(shù)的根,基站B只有出射邊,其入射邊全部去掉。規(guī)定每個(gè)EHN節(jié)點(diǎn)至少要有一條入射邊,而ON節(jié)點(diǎn)有多條入射邊備選。該過(guò)程所形成的拓?fù)洳晃ㄒ?圖4給出了某次選擇的結(jié)果。

    圖4 初步構(gòu)造的帶權(quán)有向圖

    步驟2檢查上一步結(jié)果中的含環(huán)情況。若無(wú)環(huán),直接得到反向數(shù)據(jù)匯聚拓?fù)錁?shù)。進(jìn)入步驟4。若存在環(huán),對(duì)其進(jìn)行破壞。將包含在環(huán)中的EHN節(jié)點(diǎn)進(jìn)行合并,形成一個(gè)新的合并節(jié)點(diǎn)。再次,基于最小權(quán)重選擇每個(gè)節(jié)點(diǎn)(含合并節(jié)點(diǎn))的入射邊,構(gòu)成一個(gè)新的最小權(quán)重拓?fù)錁?shù)。重復(fù)該步驟的操作,檢查新樹(shù)中包含環(huán)的情況并進(jìn)行相應(yīng)的處理,直至最后的樹(shù)中不含環(huán)。破環(huán)的過(guò)程如圖5、圖6所示。

    圖5 合并節(jié)點(diǎn)基于最小權(quán)重定邊的結(jié)果

    圖6 繼續(xù)合并節(jié)點(diǎn)并基于最小權(quán)重定邊后的最終結(jié)果

    步驟3分離上一步的合并節(jié)點(diǎn),并確定圖中每個(gè)節(jié)點(diǎn)(除B)的入射邊,得到相應(yīng)的反向匯聚拓?fù)錁?shù),如圖7所示。該過(guò)程形成的拓?fù)錁?shù)不唯一。

    圖7 拆分節(jié)點(diǎn)并確定相應(yīng)邊的示意圖

    步驟4將反向支撐匯聚拓?fù)錁?shù)的各邊進(jìn)行反向處理,得到與數(shù)據(jù)傳輸一致的支撐樹(shù)匯聚路由,如圖8所示。

    圖8 反向確定支持匯聚路由的拓?fù)錁?shù)

    步驟5重復(fù)步驟1~步驟4,獲取其他可能的支撐樹(shù)匯聚路由,并進(jìn)行對(duì)比,以期得到最優(yōu)數(shù)據(jù)匯聚路由。

    為了使模型更具可行性,在智能電網(wǎng)的監(jiān)測(cè)網(wǎng)絡(luò)實(shí)際運(yùn)行時(shí),該監(jiān)測(cè)網(wǎng)絡(luò)壽命與傳輸范圍、部署區(qū)域、ON節(jié)點(diǎn)周?chē)墓?jié)點(diǎn)密度、EPN節(jié)點(diǎn)和EHN節(jié)點(diǎn)的部署、RF能量搜集的效率有密切的關(guān)系,并不能按理想方式(比如每個(gè)節(jié)點(diǎn)僅產(chǎn)生一個(gè)數(shù)據(jù)包并將其傳輸給其上游節(jié)點(diǎn))來(lái)傳輸。因此,要區(qū)別對(duì)待EHN,在構(gòu)造的最優(yōu)數(shù)據(jù)匯聚路由中,對(duì)那些傳輸任務(wù)較重的EHN節(jié)點(diǎn)給予更高的優(yōu)先級(jí),利用移動(dòng)式EPN,在這些重載EHN節(jié)點(diǎn)旁設(shè)置一個(gè)PEPN節(jié)點(diǎn)。

    2.3 算法復(fù)雜度分析

    算法復(fù)雜度分析步驟為:

    步驟1確定樹(shù)中的頂點(diǎn)權(quán)重(復(fù)雜度為O|N|)和每條邊的權(quán)重(復(fù)雜度為O|M|),以及在所有有向邊中移除到基站B的邊(復(fù)雜度為O|M|))。

    步驟2分析得到遞歸的破環(huán)過(guò)程復(fù)雜度為O(Nlog|N|+|M|)。

    步驟3合并節(jié)點(diǎn)的分離,因?yàn)槠骗h(huán)和合并節(jié)點(diǎn)的思路與Edmond有向最小支撐樹(shù)算法思路相近,借鑒其有向最小支撐樹(shù)算法所得到的結(jié)果,其復(fù)雜度為O(|N|-1),即O|N|。

    由以上分析得出算法總的復(fù)雜度為O(3|M|+Nlog|N|+2|N|)。

    對(duì)比文獻(xiàn)[14]的APAL算法,本文算法增加了優(yōu)先充電和加速過(guò)程,算法復(fù)雜度沒(méi)有明顯增加,在節(jié)點(diǎn)數(shù)量中等及以下時(shí),可以得到更好的復(fù)雜度性能。

    3 仿真與結(jié)果分析

    為了驗(yàn)證本文算法的性能,本節(jié)進(jìn)行仿真實(shí)驗(yàn)并分析結(jié)果。主要考察網(wǎng)絡(luò)壽命,以第1個(gè)ON節(jié)點(diǎn)耗盡電池的時(shí)間為準(zhǔn),利用Matlab和開(kāi)源的整數(shù)規(guī)劃工具Ipsolve進(jìn)行混合編程,通過(guò)Matlab調(diào)用Ipsolve解決IPL最優(yōu)化問(wèn)題,其求解效率較高。其他IPL求解工具有的是商業(yè)軟件,如GPLEX,有的操作復(fù)雜,如GLPK。

    設(shè)計(jì)3個(gè)仿真過(guò)程。第1個(gè)實(shí)驗(yàn)設(shè)計(jì)為當(dāng)ρ和R不變時(shí)(分別設(shè)置為20和20%),改變K值,觀察網(wǎng)絡(luò)壽命T的變化情況;第2個(gè)實(shí)驗(yàn)設(shè)計(jì)為當(dāng)K和R不變時(shí)(分別設(shè)置為400和20%),改變K值,觀察網(wǎng)絡(luò)壽命T的變化情況;第3個(gè)實(shí)驗(yàn)設(shè)計(jì)為當(dāng)ρ和K不變時(shí)(分別設(shè)置為20和400),改變K值,觀察網(wǎng)絡(luò)壽命T的變化情況。為了研究?jī)?yōu)先充電機(jī)制的性能,增加能耗排在前10%(假設(shè)能耗僅與傳輸連接數(shù)相關(guān))的EHN節(jié)點(diǎn)作為優(yōu)先充電節(jié)點(diǎn)。在以上3種實(shí)驗(yàn)條件下比較具有優(yōu)先充電機(jī)制和沒(méi)有優(yōu)先充電機(jī)制的節(jié)能匯聚路由方案在網(wǎng)絡(luò)壽命方面的性能。

    圖9~圖11分別給出了3個(gè)實(shí)驗(yàn)的仿真結(jié)果,并對(duì)2種方案進(jìn)行了橫向?qū)Ρ取?/p>

    圖9 節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)壽命的關(guān)系

    圖10 網(wǎng)絡(luò)傳輸密度與網(wǎng)絡(luò)壽命的關(guān)系

    圖11 EHN節(jié)點(diǎn)百分比與網(wǎng)絡(luò)壽命的關(guān)系

    仿真結(jié)果表明,網(wǎng)絡(luò)壽命T與K、ρ以及R都有關(guān)系。總體情況為:當(dāng)K增加時(shí),T會(huì)下降;當(dāng)網(wǎng)絡(luò)傳輸密度ρ上升時(shí),T也同步提升。但當(dāng)ρ增長(zhǎng)到一定程度時(shí),T幾乎不再增加;當(dāng)R上升時(shí),T也增長(zhǎng),但R必須達(dá)到足夠的百分比才能體現(xiàn)出其優(yōu)勢(shì)。這說(shuō)明在匯聚路由算法中,隨著傳輸距離增加(對(duì)應(yīng)傳輸密度ρ),網(wǎng)絡(luò)中能夠及時(shí)找到足夠的下游節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸,確保了數(shù)據(jù)傳輸?shù)挠行浴?/p>

    而優(yōu)先充電節(jié)點(diǎn)增加了備用供能節(jié)點(diǎn)后,網(wǎng)絡(luò)性能發(fā)生了一定變化,主要表現(xiàn)為:在第1個(gè)實(shí)驗(yàn)中,網(wǎng)絡(luò)壽命T的下降趨勢(shì)有所緩和,會(huì)更早進(jìn)入T的穩(wěn)定狀態(tài);在第2個(gè)實(shí)驗(yàn)中,備用供能節(jié)點(diǎn)為NHN提供的優(yōu)先充電效果在r較小時(shí)更明顯,此時(shí)ON節(jié)點(diǎn)需要更多的EHN用于中繼,因此,需要消耗更多的能量;在第3個(gè)實(shí)驗(yàn)中,當(dāng)EHN節(jié)點(diǎn)增加時(shí),優(yōu)先充電機(jī)制能夠使其更好地工作,網(wǎng)絡(luò)壽命T的優(yōu)勢(shì)也更明顯。這說(shuō)明具有優(yōu)先充電機(jī)制的匯聚路由算法在節(jié)能和延長(zhǎng)網(wǎng)絡(luò)壽命方面具有更好的性能表現(xiàn)。

    在為智能電網(wǎng)監(jiān)控服務(wù)的無(wú)線傳感器網(wǎng)絡(luò)中,由于監(jiān)控流量變化不大,因此重負(fù)載捕能節(jié)點(diǎn)數(shù)量也相對(duì)較少,其對(duì)優(yōu)先供能節(jié)點(diǎn)的需求保持在一個(gè)較小的范圍,優(yōu)先充電的額外成本可控。各個(gè)節(jié)點(diǎn)的傳輸距離在較小的條件下,可以更好地協(xié)調(diào)好數(shù)據(jù)傳輸效率和網(wǎng)絡(luò)壽命的性能。

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

    為提高智能電網(wǎng)監(jiān)測(cè)網(wǎng)絡(luò)的數(shù)據(jù)傳輸有效性并延長(zhǎng)網(wǎng)絡(luò)壽命,本文提出了一種具有能量捕獲功能的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能匯聚路由數(shù)據(jù)傳輸方案,并設(shè)計(jì)了一種基于優(yōu)先充電機(jī)制的數(shù)據(jù)匯聚樹(shù)路由算法。利用整型線性編碼和最小權(quán)重捕獲支撐樹(shù)路由算法實(shí)現(xiàn)節(jié)能的數(shù)據(jù)傳輸,并對(duì)重載捕能節(jié)點(diǎn)進(jìn)行優(yōu)先充電,從而實(shí)現(xiàn)網(wǎng)絡(luò)壽命延長(zhǎng)和有效數(shù)據(jù)傳輸?shù)哪康?。該路由方案具有較小的算法復(fù)雜度,仿真結(jié)果表明,其能夠提高數(shù)據(jù)傳輸?shù)挠行?優(yōu)先充電機(jī)制也能更合理地提高網(wǎng)絡(luò)壽命。

    在下一步的研究中將重點(diǎn)考慮如何甄選優(yōu)先充電的重載EHN節(jié)點(diǎn),以及提高EHN節(jié)點(diǎn)和優(yōu)先充電節(jié)點(diǎn)在所有節(jié)點(diǎn)中的比例。

    猜你喜歡
    復(fù)雜度優(yōu)先路由
    一種低復(fù)雜度的慣性/GNSS矢量深組合方法
    40年,教育優(yōu)先
    商周刊(2018年25期)2019-01-08 03:31:08
    探究路由與環(huán)路的問(wèn)題
    多端傳播,何者優(yōu)先?
    求圖上廣探樹(shù)的時(shí)間復(fù)雜度
    站在“健康優(yōu)先”的風(fēng)口上
    某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
    出口技術(shù)復(fù)雜度研究回顧與評(píng)述
    PRIME和G3-PLC路由機(jī)制對(duì)比
    優(yōu)先待遇
    江达县| 诏安县| 呼和浩特市| 兰溪市| 紫云| 太白县| 浙江省| 尼勒克县| 乐山市| 增城市| 吉木萨尔县| 筠连县| 黎川县| 武邑县| 湖北省| 巨鹿县| 新疆| 大余县| 林西县| 赣州市| 新竹市| 乡城县| 潼关县| 韶关市| 比如县| 汉阴县| 五大连池市| 浦城县| 万盛区| 青川县| 丹巴县| 利津县| 广饶县| 库伦旗| 新闻| 冕宁县| 涿州市| 永清县| 浦县| 从江县| 徐州市|