基于證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法

李 蕾, 方明科

(信陽(yáng)師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院, 河南 信陽(yáng) 464000)

無(wú)線傳感器網(wǎng)絡(luò)在軍事、 航天、 森林火災(zāi)預(yù)警、 醫(yī)療衛(wèi)生、 空氣污染監(jiān)控等領(lǐng)域應(yīng)用廣泛[1-3]. 無(wú)線傳感器網(wǎng)絡(luò)由大量具有通信功能的傳感器節(jié)點(diǎn)組成, 這些節(jié)點(diǎn)可對(duì)相關(guān)信息進(jìn)行感知和監(jiān)測(cè), 然后將信息發(fā)給相應(yīng)的簇首, 最后由簇首發(fā)送給基站, 該過(guò)程組成了無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆酚蒣4-5]. 由于選擇不同的無(wú)線傳感器節(jié)點(diǎn)可組成不同性能的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸路由, 因此如何建立最優(yōu)的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸路由算法具有重要意義[6].

目前, 無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆酚伤惴蓜澐譃閮深悾?一類是平面結(jié)構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆酚伤惴ǎ?另一類是層次結(jié)構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆酚伤惴? 平面結(jié)構(gòu)的算法由于假設(shè)無(wú)線傳感器網(wǎng)絡(luò)結(jié)構(gòu)固定, 不僅節(jié)點(diǎn)之間采集的信息量較大, 且節(jié)點(diǎn)之間采用單跳方式進(jìn)行通信, 而現(xiàn)代無(wú)線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜多變, 因此該類算法已不再適用[7-9]. 層次結(jié)構(gòu)的算法是將整個(gè)無(wú)線傳感器網(wǎng)絡(luò)劃分為多個(gè)簇, 可適合現(xiàn)代無(wú)線傳感器網(wǎng)絡(luò)復(fù)雜多變的結(jié)構(gòu), 已成為該領(lǐng)域目前的主要研究方向[10]. LEACH(low energy adaptive clustering hierarchy)是一種典型的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)穆酚伤惴? 但LEACH算法有一定的缺陷, 因此目前已提出了許多改進(jìn)的LEACH算法[11-13]. 在實(shí)際實(shí)用中, 改進(jìn)的LEACH算法仍存在不足, 如簇劃分不合理、 易選擇剩余能量較小的傳感器節(jié)點(diǎn)作為簇首, 節(jié)點(diǎn)之間的能耗不均衡, 使無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸成功率低等[14-15].

為解決當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)路由算法存在的不足, 提高數(shù)據(jù)傳輸成功率, 本文提出一種基于證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法, 并與經(jīng)典傳感器網(wǎng)絡(luò)路由算法進(jìn)行對(duì)比測(cè)試. 測(cè)試結(jié)果表明, 本文無(wú)線傳感器網(wǎng)絡(luò)路由算法的各項(xiàng)指標(biāo)均優(yōu)于對(duì)比算法, 驗(yàn)證了該路由算法的優(yōu)勢(shì).

1 算法設(shè)計(jì)

圖1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署模型Fig.1 Node deployment model of wireless sensor network

1.1 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署模型 無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)可劃分為基站節(jié)點(diǎn)和普通節(jié)點(diǎn). 其中: 基站節(jié)點(diǎn)的能量是無(wú)限的, 位置也固定, 主要負(fù)責(zé)收集無(wú)線傳感器網(wǎng)絡(luò)所有節(jié)點(diǎn)的監(jiān)測(cè)數(shù)據(jù), 并對(duì)其處理, 最后將監(jiān)測(cè)數(shù)據(jù)發(fā)送到用戶端, 一個(gè)無(wú)線傳感器網(wǎng)絡(luò)只有一個(gè)基站節(jié)點(diǎn); 普通節(jié)點(diǎn)包括簇首節(jié)點(diǎn)和簇內(nèi)節(jié)點(diǎn), 其位置隨機(jī), 初始化能量相同, 主要負(fù)責(zé)對(duì)監(jiān)測(cè)區(qū)的對(duì)象數(shù)據(jù)進(jìn)行收集, 可根據(jù)傳輸距離調(diào)整傳輸功率. 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署模型[16]如圖1所示.

1.2 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能耗模型 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能耗模型采用無(wú)線電模型, 當(dāng)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)要進(jìn)行數(shù)據(jù)發(fā)送時(shí), 首先通過(guò)無(wú)線電路對(duì)數(shù)據(jù)進(jìn)行發(fā)送, 并對(duì)數(shù)據(jù)進(jìn)行信號(hào)轉(zhuǎn)換, 然后采用無(wú)線電發(fā)射放大電路對(duì)信號(hào)進(jìn)行放大處理, 最后通過(guò)無(wú)線電接收電路接收數(shù)據(jù), 其工作原理[17-18]如圖2所示.

圖2 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能耗模型Fig.2 Energy consumption model of wireless sensor network nodes

設(shè)Eelec為電路能耗,εfs,εmp分別為自由傳播能耗和多徑衰減能耗, 當(dāng)傳感器節(jié)點(diǎn)發(fā)送數(shù)據(jù)大小為kbit, 發(fā)送距離為d時(shí), 能耗計(jì)算公式為

(1)

其中d0為門(mén)限距離, 計(jì)算公式為

(2)

對(duì)于相同距離, 接收同樣大小數(shù)據(jù)的能耗計(jì)算公式為

ERx(k)=kEelec.

(3)

簇首節(jié)點(diǎn)融合kbit數(shù)據(jù)的能耗為

Ef(k)=kEda,

(4)

其中Eda為融合數(shù)據(jù)能耗.

1.3 模糊聚類算法的無(wú)線傳感器網(wǎng)絡(luò)分簇 當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)的簇劃分采用隨機(jī)方式, 存在產(chǎn)生簇首過(guò)于集中、 簇成員節(jié)點(diǎn)分配不合理的弊端, 因此, 本文采用模糊聚類算法進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)分簇, 即將整個(gè)無(wú)線傳感器網(wǎng)絡(luò)劃分為多個(gè)子區(qū)域. 設(shè)無(wú)線傳感器網(wǎng)絡(luò)共有N個(gè)節(jié)點(diǎn), 其位置集合為X={x1,x2,…,xn}, 利用模糊聚類算法將每個(gè)節(jié)點(diǎn)劃分到相應(yīng)簇中. 用vi表示第i個(gè)聚類中心,uij表示第i個(gè)傳感器節(jié)點(diǎn)相對(duì)于第j個(gè)簇隸屬度值,U表示隸屬度矩陣,V表示聚類中心矩陣, 則無(wú)線傳感器網(wǎng)絡(luò)分簇的目標(biāo)函數(shù)為

(5)

其中：K表示聚類中心的數(shù)量, 即無(wú)線傳感器網(wǎng)絡(luò)的簇?cái)?shù)；m表示模糊加權(quán)指數(shù). 式(5)的約束條件為

(6)

在模糊聚類算法中,uij和vi的更新公式為

模糊聚類算法進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)分簇思想： 先隨機(jī)在無(wú)線傳感器網(wǎng)絡(luò)中選擇多個(gè)聚類中心, 然后以聚類中心為基礎(chǔ), 對(duì)全部無(wú)線傳感器網(wǎng)絡(luò)傳感器節(jié)點(diǎn)進(jìn)行初步聚類, 并根據(jù)式(8)得到每個(gè)傳感器節(jié)點(diǎn)的最終隸屬度值, 最后每個(gè)傳感器節(jié)點(diǎn)根據(jù)隸屬度值劃分到無(wú)線傳感器網(wǎng)絡(luò)子區(qū)域內(nèi), 于是整個(gè)無(wú)線傳感器網(wǎng)絡(luò)被劃分為K個(gè)簇.

1.4 基于證據(jù)理論選擇簇首節(jié)點(diǎn) 當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)的簇首根據(jù)傳感器節(jié)點(diǎn)剩余能量進(jìn)行選擇, 使得整個(gè)網(wǎng)絡(luò)的傳感器節(jié)點(diǎn)能耗不均勻, 因此本文引入證據(jù)理論對(duì)每個(gè)簇的傳感器節(jié)點(diǎn)性能進(jìn)行綜合評(píng)價(jià), 再根據(jù)評(píng)價(jià)結(jié)果選擇每個(gè)簇的簇首. 證據(jù)理論是不確定性數(shù)學(xué)的一個(gè)重要分支, 設(shè)一個(gè)事件或命題為xi(i=1,2,…,n), 則表示Θ識(shí)別框架, 即Θ={x1,x2,…,xn}.Θ所有子集組成一個(gè)集合2Θ, 即

2Θ={φ,{x1},…,{xn},{x1∪x2},{x1∪x3},…,Θ}.

(9)

如果函數(shù)M: 2Θ→[0,1]滿足如下條件：

(10)

則稱為Θ的基本概率分配函數(shù)， 其中M(A)表示事件A的基本可信度.

對(duì)于n個(gè)不同的證據(jù), 對(duì)其概率分配函數(shù)M1,M2,…,Mn, 通過(guò)證據(jù)理論進(jìn)行融合, 可得新的概率分配函數(shù)為

(11)

本文采用傳感器節(jié)點(diǎn)剩余能量、 與下一簇首間的通信距離、 數(shù)據(jù)通信能耗、 路由距離作為評(píng)價(jià)指標(biāo), 評(píng)價(jià)簇首選擇的優(yōu)劣. 首先采用證據(jù)理論分別確定傳感器節(jié)點(diǎn)剩余能量、 與下一簇首間的通信距離、 數(shù)據(jù)通信能耗、 路由距離的權(quán)值, 然后根據(jù)權(quán)值得到所有傳感器節(jié)點(diǎn)性能的綜合評(píng)價(jià)結(jié)果, 并根據(jù)綜合結(jié)果對(duì)傳感器節(jié)點(diǎn)進(jìn)行排序, 最后根據(jù)排序結(jié)果選擇最優(yōu)的傳感器節(jié)點(diǎn)作為簇首節(jié)點(diǎn).

1.5 證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法工作原理 為解決當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)路由構(gòu)建過(guò)程中, 由于簇的劃分、 簇首選擇等不足導(dǎo)致的無(wú)線傳感器網(wǎng)絡(luò)生命周期過(guò)短、 數(shù)據(jù)傳輸?shù)腻e(cuò)誤率高、 數(shù)據(jù)傳輸時(shí)延長(zhǎng)、 無(wú)線傳感器網(wǎng)絡(luò)的不可靠性等缺陷, 本文提出一種基于證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法, 其基本原理為： 首先通過(guò)引入模糊聚類算法進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)分簇, 使網(wǎng)絡(luò)的簇?cái)?shù)及簇內(nèi)的傳感器節(jié)點(diǎn)數(shù)更合理, 然后采用多個(gè)指標(biāo)對(duì)每個(gè)傳感器節(jié)點(diǎn)的性能進(jìn)行評(píng)價(jià), 并引入證據(jù)理論根據(jù)評(píng)價(jià)指標(biāo)進(jìn)行加權(quán), 選擇綜合性能最優(yōu)的傳感器節(jié)點(diǎn)作為一個(gè)簇的簇首, 防止一些性能差的傳感器節(jié)點(diǎn)被選擇為簇首, 最后簇內(nèi)節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)之間的距離進(jìn)行單跳或多跳相結(jié)合的方式進(jìn)行通信, 構(gòu)建一條最優(yōu)的數(shù)據(jù)傳輸路由.

2 仿真測(cè)試

2.1 無(wú)線傳感器網(wǎng)絡(luò)參數(shù)設(shè)置 為測(cè)試證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法性能, 采用MATLAB 2017實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)路由算法仿真, 選擇文獻(xiàn)[14]和文獻(xiàn)[15]中的無(wú)線傳感器網(wǎng)絡(luò)路由算法進(jìn)行對(duì)比實(shí)驗(yàn). 無(wú)線傳感器網(wǎng)絡(luò)仿真參數(shù)列于表1.

表1 無(wú)線傳感器網(wǎng)絡(luò)仿真參數(shù)設(shè)置

圖3 不同無(wú)線傳感器網(wǎng)絡(luò)路由算法的數(shù)據(jù)傳輸時(shí)延對(duì)比Fig.3 Comparison of data transmission delay of different wireless sensor network routing algorithms

2.2 無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)延分析 3種對(duì)比無(wú)線傳感器網(wǎng)絡(luò)路由算法的數(shù)據(jù)傳輸時(shí)延變化如圖3所示. 由圖3可見(jiàn), 隨著仿真時(shí)間的不斷增加, 無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸時(shí)延均增加, 這是由于隨著數(shù)據(jù)傳輸量的不斷增加, 使數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù)增多, 但在相同的仿真時(shí)間內(nèi), 證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)路由算法的數(shù)據(jù)傳輸時(shí)延少于文獻(xiàn)[14]和文獻(xiàn)[15]算法的數(shù)據(jù)傳輸時(shí)延, 表明證據(jù)理論加權(quán)融合算法的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸速度更快, 提高了無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)吞吐量.

2.3 無(wú)線傳感器網(wǎng)絡(luò)丟包率分析 3種對(duì)比無(wú)線傳感器網(wǎng)絡(luò)路由算法的丟包率變化曲線如圖4所示. 由圖4可見(jiàn), 由于無(wú)線傳感器網(wǎng)絡(luò)工作時(shí)間延長(zhǎng), 數(shù)據(jù)丟包率不斷上升, 這是由于隨著工作時(shí)間的延長(zhǎng), 一些傳感器節(jié)點(diǎn)由于能量耗盡而失效, 無(wú)線傳感器網(wǎng)絡(luò)需要?jiǎng)討B(tài)調(diào)整數(shù)據(jù)傳輸?shù)穆酚? 使數(shù)據(jù)丟包次數(shù)不斷增多, 但本文算法的丟包率一直低于文獻(xiàn)[14]和文獻(xiàn)[15]算法的丟包率, 表明本文算法的無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸成功率更高, 減少了無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)腻e(cuò)誤次數(shù), 使無(wú)線傳感器網(wǎng)絡(luò)的通信質(zhì)量更高.

2.4 無(wú)線傳感器網(wǎng)絡(luò)生存周期分析 3種對(duì)比無(wú)線傳感器網(wǎng)絡(luò)路由算法的傳感器節(jié)點(diǎn)死亡數(shù)量曲線如圖5所示. 由圖5可見(jiàn), 在無(wú)線傳感器網(wǎng)絡(luò)工作初期, 傳感器節(jié)點(diǎn)死亡數(shù)量較少, 隨著工作時(shí)間的增加, 傳感器節(jié)點(diǎn)死亡數(shù)量呈上升趨勢(shì), 到一定時(shí)間, 無(wú)線傳感器網(wǎng)絡(luò)中多數(shù)傳感器節(jié)點(diǎn)死亡, 此時(shí)無(wú)線傳感器網(wǎng)絡(luò)處于無(wú)法正常工作狀態(tài), 已經(jīng)失效, 生存周期完結(jié), 但證據(jù)理論加權(quán)融合算法的無(wú)線傳感器網(wǎng)絡(luò)生存周期明顯優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[15]算法, 延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)的壽命.

圖4 不同無(wú)線傳感器網(wǎng)絡(luò)路由算法的丟包率對(duì)比Fig.4 Comparison of packet loss rates of different wireless sensor network routing algorithms

圖5 不同無(wú)線傳感器網(wǎng)絡(luò)路由算法的生存周期對(duì)比Fig.5 Comparison of life cycle of different wireless sensor network routing algorithms

綜上所述, 本文針對(duì)無(wú)線傳感器網(wǎng)絡(luò)路由算法存在的數(shù)據(jù)傳輸可靠性差, 網(wǎng)絡(luò)易失效等問(wèn)題, 提出了一種基于證據(jù)理論加權(quán)融合的無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)路由算法, 通過(guò)引入模糊聚類分析算法解決簇劃分不合理的問(wèn)題, 并引入證據(jù)理論對(duì)傳感器節(jié)點(diǎn)的性能進(jìn)行加權(quán), 解決了簇首選擇問(wèn)題. 仿真測(cè)試結(jié)果表明, 本文算法使無(wú)線傳感器網(wǎng)絡(luò)各節(jié)點(diǎn)能耗更均衡, 減少了網(wǎng)絡(luò)丟包率, 延長(zhǎng)了通信的生命周期, 有一定的實(shí)際應(yīng)用價(jià)值.