一種低能耗與高精確度的WSN數(shù)據(jù)融合算法

宋 蕾,任秀麗

(遼寧大學(xué) 信息學(xué)院,沈陽 110036)

0 概述

無線傳感網(wǎng)中數(shù)據(jù)融合[1]是指將同一目標(biāo)的多個觀測數(shù)據(jù)相互融合,以減少數(shù)據(jù)冗余并提高系統(tǒng)可靠性[2],進(jìn)而延長網(wǎng)絡(luò)生命周期。傳感器節(jié)點(diǎn)在數(shù)據(jù)采集、傳輸與統(tǒng)計(jì)過程中,隨著網(wǎng)絡(luò)時(shí)延增加、通信量增多和節(jié)點(diǎn)生命周期縮短等問題[3],致使數(shù)據(jù)精確度下降,且節(jié)點(diǎn)能耗隨之增加。

針對節(jié)點(diǎn)能耗和數(shù)據(jù)精確度問題,文獻(xiàn)[4]提出低能耗的E-CPDA算法,在提高數(shù)據(jù)精確度的同時(shí)增加了簇結(jié)構(gòu)動態(tài)變化的能耗。文獻(xiàn)[5]提出面向車組網(wǎng)的MGDAA算法,通過綜合數(shù)據(jù)的冗余和互補(bǔ)信息來提高融合精確度,但會增加節(jié)點(diǎn)能耗。文獻(xiàn)[6]提出基于車輛檢測器數(shù)據(jù)壓縮重構(gòu)和交通流特征的Megrez算法,提高了數(shù)據(jù)精確度,但也增加了節(jié)點(diǎn)能耗。針對上述算法存在的問題,本文提出一種基于博弈論的數(shù)據(jù)融合算法(Data Fusion Algorithm Based on Game Theory,DFABGT)。該算法分為基于博弈論[7]的節(jié)點(diǎn)選取和基于貝葉斯理論[8]的數(shù)據(jù)融合兩部分,簇內(nèi)節(jié)點(diǎn)通過收益和能耗確定效益函數(shù)選取低能耗節(jié)點(diǎn),再將效益函數(shù)的最大值作為權(quán)重代入置信距離得到可靠數(shù)據(jù)。

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

在無線傳感網(wǎng)中,n個節(jié)點(diǎn)構(gòu)成m個簇結(jié)構(gòu)。簇頭收集簇內(nèi)節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù),Sink節(jié)點(diǎn)融合數(shù)據(jù),以保證全局最優(yōu)[9]。1)傳感器節(jié)點(diǎn)同構(gòu)且位置固定,感知半徑、通信能力和初始能量相等,每個節(jié)點(diǎn)具有唯一ID,且周期性地向簇頭傳輸數(shù)據(jù);2)節(jié)點(diǎn)非均勻分布,簇頭能感知簇內(nèi)節(jié)點(diǎn)的位置與剩余能量,簇內(nèi)節(jié)點(diǎn)能感知自身剩余能量;3)不論剩余能量是否有限,能耗控制均需在節(jié)點(diǎn)承受的能量范圍內(nèi);4)節(jié)點(diǎn)自感知且主動收集數(shù)據(jù),Sink節(jié)點(diǎn)沒有能量限制。網(wǎng)絡(luò)模型[10]如圖1所示。

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

2 DFABGT算法

DFABGT算法分為基于博弈論的節(jié)點(diǎn)選取和基于貝葉斯理論的數(shù)據(jù)融合兩部分。基于博弈論的節(jié)點(diǎn)選取以降低能耗為目標(biāo),簇內(nèi)節(jié)點(diǎn)通過效益函數(shù)最大值選取最佳策略。基于貝葉斯理論的數(shù)據(jù)融合以提高數(shù)據(jù)精確度為目標(biāo),簇頭通過置信距離選取有效數(shù)據(jù)傳輸給Sink節(jié)點(diǎn),并采用貝葉斯融合數(shù)據(jù)。

2.1 基于博弈論的節(jié)點(diǎn)選取

簇內(nèi)節(jié)點(diǎn)通過收益和能耗相互博弈選取最佳策略得到低能耗節(jié)點(diǎn)。博弈論[11]的基本要素為參與者、策略和效益函數(shù)。參與者指需要決策的個體,即簇內(nèi)節(jié)點(diǎn)。策略指具體規(guī)則,令節(jié)點(diǎn)具有選擇善意融合(Good Fusion,GF)、惡意融合(Bad Fusion,BF)與不融合(Not Fusion,NF)的能力,記為S={GF,BF,NF}。效益函數(shù)指行動函數(shù),以判斷不同策略的期望值。效益函數(shù)由收益和能耗構(gòu)成,具有如下要素:

要素1收益(α)用于判斷節(jié)點(diǎn)是否參與數(shù)據(jù)融合處理,其中,αi=1表示第i個節(jié)點(diǎn)參與融合處理,αi=0為不參與融合處理,收益集合記為{α1,α2,…,αn}。

要素2善意融合能耗WG表示節(jié)點(diǎn)融合數(shù)據(jù)包的能耗。

要素3惡意融合能耗WB表示由于鏈路信道、節(jié)點(diǎn)或數(shù)據(jù)包遭受網(wǎng)絡(luò)攻擊導(dǎo)致融合呈現(xiàn)惡意結(jié)果,其能耗值為融合數(shù)據(jù)包的能耗與網(wǎng)絡(luò)攻擊的能耗(WA)。

要素4不融合能耗WN表示任意兩個節(jié)點(diǎn)中若有一個節(jié)點(diǎn)不參與融合,則另一個節(jié)點(diǎn)有融合能耗但沒有收益;若兩個節(jié)點(diǎn)均不參與融合,則節(jié)點(diǎn)均沒有收益或能耗。

不同策略組合形成的效益值構(gòu)成博弈策略(如表1所示),說明如下:

1)假設(shè)節(jié)點(diǎn)i與節(jié)點(diǎn)j均選擇融合策略時(shí),節(jié)點(diǎn)i與節(jié)點(diǎn)j均有收益(αi=αj=1)且為對方付出相應(yīng)的融合能耗;當(dāng)節(jié)點(diǎn)i選擇融合策略、節(jié)點(diǎn)j選擇不融合策略時(shí),節(jié)點(diǎn)i與節(jié)點(diǎn)j均沒有收益(αi=αj=0),節(jié)點(diǎn)j付出不融合能耗但節(jié)點(diǎn)i付出相應(yīng)的融合能耗。

2)假設(shè)節(jié)點(diǎn)i選擇不融合策略、節(jié)點(diǎn)j選擇融合策略時(shí),節(jié)點(diǎn)i與節(jié)點(diǎn)j均沒有收益(αi=αj=0),節(jié)點(diǎn)j付出不融合能耗但節(jié)點(diǎn)i付出相應(yīng)的融合能耗;當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j選擇不融合策略時(shí),節(jié)點(diǎn)i與節(jié)點(diǎn)j均沒有收益(αi=αj=0)或能耗。

表1 博弈策略

參與融合的任意兩個節(jié)點(diǎn)中一個節(jié)點(diǎn)選擇善意融合、惡意融合與不融合的概率為β1、β2、β3,且β1+β2+β3=1表示全部的決策內(nèi)容;另一個節(jié)點(diǎn)選擇善意融合、惡意融合與不融合的效益函數(shù)記為p(GF)、p(BF)、p(NF),計(jì)算公式如下:

p(GF)=β1×(1-WG)+β2×(1-WG)+β3×WG

(1)

p(BF)=β1×(1-WB)+β2×(1-WB)+β3×WB

(2)

p(NF)=(β1+β2+β3)×WN=WN

(3)

因?yàn)閃B=WG+WA,所以WB>WG恒成立,通常令WN=0,不論βi(i=1,2,3)取何值,總存在p(GF)>p(BF)>p(NF)。簇內(nèi)節(jié)點(diǎn)通過多輪博弈剔除不融合節(jié)點(diǎn),降低節(jié)點(diǎn)能耗。

2.2 基于貝葉斯理論的數(shù)據(jù)融合

通過博弈論選取低能耗節(jié)點(diǎn)的方式不能保證采集數(shù)據(jù)均可靠,因此簇頭需通過置信距離篩選可靠數(shù)據(jù),提高精確度。置信距離[12]基于預(yù)判測量數(shù)據(jù)與實(shí)際數(shù)值的緊密程度,確保采集數(shù)據(jù)接近實(shí)際結(jié)果。令xi、xj為一次測量中第i個和第j個節(jié)點(diǎn)的輸出,且i

(4)

其中,分母用作歸一化處理,分子中的概率密度函數(shù)定義如下:

(5)

效益函數(shù)最大值p(GF)作為權(quán)重代入概率密度函數(shù),確保節(jié)點(diǎn)在善意融合的前提下得到有效數(shù)據(jù)。當(dāng)xi=xj時(shí),dij=0;當(dāng)xi≠xj時(shí),dij∈(0,1)。定義二值變量rij為第i個節(jié)點(diǎn)輸出數(shù)據(jù)對第j個節(jié)點(diǎn)輸出數(shù)據(jù)的支持程度,通過融合結(jié)果確定閾值α與rij,具體公式如下:

(6)

其中,1表示第i個節(jié)點(diǎn)的輸出數(shù)據(jù)支持第j個節(jié)點(diǎn)的輸出數(shù)據(jù);0表示第i個節(jié)點(diǎn)的輸出數(shù)據(jù)不支持第j個節(jié)點(diǎn)的輸出數(shù)據(jù)。

假設(shè)節(jié)點(diǎn)的臨界數(shù)為m,對n個節(jié)點(diǎn)中任意兩個節(jié)點(diǎn)采集的數(shù)據(jù)計(jì)算置信距離得到m×m的二值關(guān)系矩陣,表示節(jié)點(diǎn)輸出數(shù)據(jù)間的相互支持程度,篩選出l個有效數(shù)據(jù)。

(7)

(8)

2.3 DFABGT算法實(shí)現(xiàn)

DFABGT算法流程如圖2所示,具體步驟如下:

步驟1在一輪博弈中,節(jié)點(diǎn)從善意融合、惡意融合與不融合中選擇一個策略,依據(jù)能耗與收益計(jì)算效益函數(shù)。

步驟2通過效益函數(shù)值剔除不融合節(jié)點(diǎn)降低能耗。

步驟3將效益函數(shù)最大值作為權(quán)重代入置信距離公式,確保參與融合的節(jié)點(diǎn)均是善意融合且相互支持度最高。

步驟4依據(jù)融合結(jié)果確定閾值,將置信距離向量和閾值進(jìn)行比較得到二值關(guān)系向量,構(gòu)成二值關(guān)系矩陣。

步驟5由二值關(guān)系變量剔除小于閾值的置信距離值并且篩選有效數(shù)據(jù),簇頭節(jié)點(diǎn)將有效數(shù)據(jù)傳輸給Sink節(jié)點(diǎn)。

步驟6Sink節(jié)點(diǎn)采用貝葉斯理論融合數(shù)據(jù)得到融合結(jié)果。

步驟7為避免篩選善意或惡意融合節(jié)點(diǎn),需要重復(fù)上述步驟完成多輪博弈,直至剩余節(jié)點(diǎn)均不融合時(shí)為止。

圖2 DFABGT算法流程

3 算法仿真與性能分析

將100個節(jié)點(diǎn)隨機(jī)分布在200 m×200 m中,Sink節(jié)點(diǎn)部署在(100 m,100 m)處,處于集群中心且剩余能量最大的節(jié)點(diǎn)設(shè)置為簇頭[14]。在OPNET仿真環(huán)境[15]下對DFABGT算法與E-CPDA算法、MGDAA算法及Megrez算法進(jìn)行對比,仿真參數(shù)如表2所示。

表2 仿真參數(shù)設(shè)置

3.1 數(shù)據(jù)精確度

依據(jù)文獻(xiàn)[16]中數(shù)據(jù)精確度定義,數(shù)據(jù)精確度等于融合前后的數(shù)據(jù)累和之比。考慮到貝葉斯理論,本文采用均值與方差作為判斷融合結(jié)果精確度k的依據(jù),具體計(jì)算如下:

(9)

圖3 數(shù)據(jù)融合算法的融合結(jié)果精確度比較

由圖3可知,DFABGT算法、E-CPDA算法、MGDAA算法與Megrez算法的融合精確度隨著節(jié)點(diǎn)數(shù)的增多均呈上升趨勢。在傳感器節(jié)點(diǎn)數(shù)為10～90時(shí),DFABGT算法相比E-CPDA算法、MGDAA算法與Megrez算法精確度上升均值為3.9%、21.2%和12.1%。E-CPDA算法通過降低節(jié)點(diǎn)在通信過程中的碰撞幾率提高精確度,但其未篩選數(shù)據(jù);MGDAA算法通過改變簇結(jié)構(gòu)冗余度和結(jié)構(gòu)變化度從而破壞原始數(shù)據(jù);Megrez算法中的壓縮和重構(gòu)過程破壞了原始數(shù)據(jù);DFABGT算法在篩選原始數(shù)據(jù)時(shí)并沒有破壞和構(gòu)造數(shù)據(jù),因此其精確度高于其他算法。

3.2 節(jié)點(diǎn)能耗

本文在無線傳感網(wǎng)中采用簡單的能耗模型[17],忽略節(jié)點(diǎn)在計(jì)算、存儲等過程中的能耗,僅計(jì)算節(jié)點(diǎn)隨著通信時(shí)間增加所消耗的能量。假設(shè)節(jié)點(diǎn)傳輸lbit數(shù)據(jù)經(jīng)過的距離為d(20≤d≤25),數(shù)據(jù)融合過程中的節(jié)點(diǎn)能耗公式如下:

(10)

ERx_elec(l)=lEelec

(11)

其中,ETx(l,d)為發(fā)送端經(jīng)過距離d發(fā)送lbit數(shù)據(jù)的能耗,ERx_elec(l)為接收端接收lbit數(shù)據(jù)的能耗,d0=25 m為閾值,Eelec為節(jié)點(diǎn)收發(fā)每比特?cái)?shù)據(jù)的能耗,εfsd2與εmpd4為信號自由空間模型和多徑衰減模型中信號放大器的能耗參數(shù)[18]。當(dāng)發(fā)送端與接收端的距離小于閾值時(shí),采用自由空間的通信方式,發(fā)送端能耗與距離的平方成正比;否則采用多徑衰減的通信方式,發(fā)送端能耗與距離的4次方成正比。

假設(shè)融合單位比特?cái)?shù)據(jù)的能耗為EDA,由此可知EDA的取值范圍為(0,ETx(l,d)+ERx_elec(l))[19],那么善意融合的能耗取值范圍為(0,lEDA),惡意融合的能耗總是大于善意融合的能耗,而不融合的能耗為0。節(jié)點(diǎn)能耗的變化曲線,如圖4所示。

圖4 數(shù)據(jù)融合算法的節(jié)點(diǎn)能耗比較

由圖4可知,DFABGT算法與E-CPDA算法、MGDAA算法和Megrez算法比較,節(jié)點(diǎn)能耗分別降低28%、22%和19%。E-CPDA算法通過減少通信傳輸量降低能耗,導(dǎo)致存在額外簇結(jié)構(gòu)的能耗;MGDAA算法與Megrez算法以節(jié)點(diǎn)能耗為代價(jià)換取數(shù)據(jù)精確度,但卻未兼顧節(jié)點(diǎn)能耗問題,而DFABGT算法通過融合能耗進(jìn)行博弈來降低節(jié)點(diǎn)能耗,且未產(chǎn)生額外能耗。綜上,DFABGT算法的能耗低于其他算法。

3.3 網(wǎng)絡(luò)生命周期

網(wǎng)絡(luò)生命周期用于衡量負(fù)載均衡情況,本文采用文獻(xiàn)[20]的定義,認(rèn)為網(wǎng)絡(luò)生命周期為首個節(jié)點(diǎn)的失效時(shí)間。網(wǎng)絡(luò)中節(jié)點(diǎn)存活率的變化情況如圖5所示。

圖5 數(shù)據(jù)融合算法的網(wǎng)絡(luò)生命周期比較

由圖5可知,DFABGT算法與E-CPDA算法、MGDAA算法和Megrez算法進(jìn)行比較,網(wǎng)絡(luò)生命周期分別延長5%、3.1%和4.8%。E-CPDA算法、MGDAA算法和Megrez算法未篩選節(jié)點(diǎn)與數(shù)據(jù),因此增加了能耗,且E-CPDA算法增加了簇結(jié)構(gòu)的能耗,而DFBAGT算法通過選取節(jié)點(diǎn)、篩選數(shù)據(jù),大幅度降低節(jié)點(diǎn)能量的消耗,使得節(jié)點(diǎn)存活率下降幅度低于其他算法。綜上,DFABGT算法的網(wǎng)絡(luò)生命周期更長。

4 結(jié)束語

本文從提高數(shù)據(jù)精確度和降低節(jié)點(diǎn)能耗兩方面著手,提出基于博弈論的數(shù)據(jù)融合算法,簇內(nèi)節(jié)點(diǎn)以收益和能耗為效益函數(shù)的輸入?yún)?shù)進(jìn)行博弈。通過效益函數(shù)最大值選取低能耗節(jié)點(diǎn),對這些節(jié)點(diǎn)進(jìn)行置信距離的計(jì)算來篩選有效數(shù)據(jù)參與融合處理。簇頭將有效數(shù)據(jù)傳輸?shù)絊ink節(jié)點(diǎn),由Sink節(jié)點(diǎn)采用貝葉斯理論融合數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明,本文算法能有效提高數(shù)據(jù)精確度,降低節(jié)點(diǎn)能耗,延長網(wǎng)絡(luò)生命周期。下一步將考慮數(shù)據(jù)的安全隱私特性,在實(shí)現(xiàn)數(shù)據(jù)精確融合的同時(shí)保障數(shù)據(jù)安全。