基于可信度的無線傳感器網(wǎng)絡(luò)高集聚性構(gòu)造

傅霞玲

(黎明職業(yè)大學(xué) 教學(xué)診斷與質(zhì)量保證中心,福建 泉州 362000)

因“無所不在”的感知技術(shù)以及現(xiàn)代科學(xué)技術(shù)在微處理傳感器性能及體積等方面的進(jìn)步,無線傳感器網(wǎng)絡(luò)被廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療、家庭及工業(yè)商業(yè)等領(lǐng)域。然而，由于無線傳感器網(wǎng)絡(luò)采用無線信道及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化，使其容易遭受竊聽、干擾、入侵等攻擊，再加上傳感器節(jié)點(diǎn)元器件故障、自身能量有限及惡意節(jié)點(diǎn)加入等不穩(wěn)定因素的存在，網(wǎng)絡(luò)的安全性較差。如何對網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)及鏈路的可信度進(jìn)行評價(jià)，建立從節(jié)點(diǎn)到基站的可信連通鏈路,保證信息安全可靠地傳輸?shù)侥康墓?jié)點(diǎn)，提高網(wǎng)絡(luò)的可靠性和健壯性,是網(wǎng)絡(luò)設(shè)計(jì)必須面對的問題。

對此，眾多學(xué)者進(jìn)行了相關(guān)的研究。鄧瑋[1]針對無線傳感器網(wǎng)絡(luò)因計(jì)算能力差、易被攻擊和篡改等問題,提出一種綜合考慮影響網(wǎng)絡(luò)因素的可信路由算法。劉小久等[2]提出了一種基于BP(神經(jīng))網(wǎng)絡(luò)判斷節(jié)點(diǎn)信息可信度的方法，該方法對采集的多特征值數(shù)據(jù)進(jìn)行訓(xùn)練，然后用訓(xùn)練所得結(jié)果判斷節(jié)點(diǎn)可信度，進(jìn)而篩選出數(shù)據(jù)。陳蕾等[3]提出采用加密的方式對無線傳感器節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)進(jìn)行保護(hù)。葉秀彩等[4-6]從提高集聚系數(shù)、構(gòu)造小世界特性這一目的入手構(gòu)造無線傳感器網(wǎng)絡(luò)，達(dá)到節(jié)能及延長網(wǎng)絡(luò)生命周期的目的。本文在這些研究的基礎(chǔ)上，綜合考慮網(wǎng)絡(luò)的集聚系數(shù)、邊的介數(shù)和邊的連通概率等三方面因素，提出基于可信度的虛擬刪邊算法，構(gòu)造基于可信度的高集聚性的無線傳感器網(wǎng)絡(luò)。

1 相關(guān)概念

1.1 網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)

許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)，即社團(tuán)結(jié)構(gòu)。具有社團(tuán)結(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)，由若干個(gè)“群”或“簇”構(gòu)成，每個(gè)群或簇內(nèi)部的節(jié)點(diǎn)之間連接相對比較緊密，而網(wǎng)絡(luò)中簇與簇之間的連接卻相對比較稀疏，如圖1所示。

對于隨機(jī)撒灑于監(jiān)測區(qū)域的大量傳感器節(jié)點(diǎn)所構(gòu)成的網(wǎng)絡(luò)，同樣具有這樣的性質(zhì)，即有的節(jié)點(diǎn)連接相對非常緊密，有的連接相對比較稀疏。連接相對緊密的那部分節(jié)點(diǎn)，構(gòu)成網(wǎng)絡(luò)中的群或簇；連接比較稀疏的，一般是簇間的連接。

圖1 網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)示意圖

1.2 集聚系數(shù)

集聚系數(shù)是網(wǎng)絡(luò)集團(tuán)化程度的表現(xiàn)，是網(wǎng)絡(luò)的一種聚類特性，考察連接在一起的頂點(diǎn)的所有近鄰之中有多少是共同的近鄰。節(jié)點(diǎn)i的集聚系數(shù)Ci表示與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)之間的連接關(guān)系，即與該節(jié)點(diǎn)一跳鄰居的節(jié)點(diǎn)間實(shí)際存在的邊數(shù)目和總的可能存在邊數(shù)的比例。

1.3 介數(shù)

介數(shù)分為節(jié)點(diǎn)介數(shù)和邊介數(shù)兩種。本文使用邊介數(shù)概念，網(wǎng)絡(luò)中的邊介數(shù)表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)對的最短路徑中經(jīng)過該邊的數(shù)目。正則化表示，假設(shè)網(wǎng)絡(luò)中共有N條不同的最短路徑，其中有n條經(jīng)過該邊，則這條邊的介數(shù)為n/N。介數(shù)高的邊在網(wǎng)絡(luò)中體現(xiàn)出較高的重要性和影響力，有較多的最短路徑經(jīng)過該邊。

1.4 可信度

可信度又稱為聲譽(yù)評價(jià),廣泛應(yīng)用于電子商務(wù)中。交易的雙方通過交易后的反饋信息來對雙方進(jìn)行可信度評價(jià)，這個(gè)可信度評價(jià)又將影響以后的交易行為。同樣的情況，無線傳感網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)、邊或鏈路同樣具有不同的可信度，必須進(jìn)行綜合考慮及評價(jià)。影響網(wǎng)絡(luò)可信度有多方面的因素，本文用具體的連通概率值來進(jìn)行衡量，主要是考慮邊的連通概率。

1.5 虛擬刪邊的含義

虛擬刪邊指的是，在滿足網(wǎng)絡(luò)覆蓋度和連通度的前提下，通過功率控制，控制并切斷部分符合虛擬刪除條件的傳感器節(jié)點(diǎn)之間的通信鏈路，節(jié)省節(jié)點(diǎn)間不必要的通信開銷，以達(dá)到節(jié)能及增強(qiáng)集聚性的目的。

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

2.1 模型描述

在節(jié)點(diǎn)隨機(jī)分布的無線傳感器網(wǎng)絡(luò)，節(jié)點(diǎn)可以隨機(jī)分布于規(guī)則或不規(guī)則的區(qū)域中，為研究方便起見，考慮節(jié)點(diǎn)隨機(jī)分布于正方形區(qū)域中的情形，并假設(shè)：

(1)節(jié)點(diǎn)信號傳輸滿足對稱性；

(2)無線傳感器網(wǎng)絡(luò)為同構(gòu)網(wǎng)絡(luò)，節(jié)點(diǎn)的信號傳輸半徑為r，節(jié)點(diǎn)具有相同的性能和傳輸半徑。并設(shè)e,f為網(wǎng)絡(luò)中的兩個(gè)傳感器節(jié)點(diǎn)，def表示兩點(diǎn)間的距離，當(dāng)def≤r時(shí)，節(jié)點(diǎn)e,f可以直接通信，則認(rèn)為e,f節(jié)點(diǎn)之間存在一條邊；否則，不連邊。按照這一原則，對網(wǎng)絡(luò)進(jìn)行連邊處理，即信號覆蓋的范圍內(nèi)兩點(diǎn)連邊，從而生成網(wǎng)絡(luò)拓?fù)鋱D。

2.2 模型分析

初始網(wǎng)絡(luò)和虛擬刪邊后的網(wǎng)絡(luò)拓?fù)涫疽鈭D見圖2和圖3。

圖2為傳感器節(jié)點(diǎn)隨機(jī)分布的局部拓?fù)鋱D，網(wǎng)絡(luò)中信息傳輸覆蓋的范圍內(nèi)兩點(diǎn)連線構(gòu)成網(wǎng)絡(luò)拓?fù)鋱D，圖中共14個(gè)節(jié)點(diǎn)，分別用a,b,…，n表示。圖3為虛擬刪邊后網(wǎng)絡(luò)局部拓?fù)涫疽鈭D,其中的節(jié)點(diǎn)e,f之間的連邊lef、節(jié)點(diǎn)h,j之間連邊lhj及節(jié)點(diǎn)j,k之間連邊ljk虛擬刪除后的網(wǎng)絡(luò)拓?fù)鋱D。刪邊前及刪邊后各個(gè)節(jié)點(diǎn)的集聚系數(shù)分別標(biāo)注于圖2、圖3上。刪邊前及刪邊后平均集聚系數(shù)計(jì)算如表1所示。

表1 刪邊前及刪邊后平均集聚系數(shù)比較

由表1知，刪邊后，網(wǎng)絡(luò)的集聚系數(shù)平均值增大，集聚性增強(qiáng)。并且，由圖3可直觀地看出，網(wǎng)絡(luò)更加簡化，簇結(jié)構(gòu)更加明顯。

3 虛擬刪邊算法

虛擬刪邊算法綜合考慮集聚系數(shù)、邊的介數(shù)和邊的連通概率三方面因素，當(dāng)一條邊符合三方面的條件時(shí)，邊刪除，否則不刪除。

3.1 考慮集聚系數(shù)

判斷一條邊是否為候選刪除邊的方法為，分別判斷該邊的兩個(gè)節(jié)點(diǎn)是否為候選刪除節(jié)點(diǎn)，若兩點(diǎn)均為候選刪除節(jié)點(diǎn)，則該邊作為候選刪除邊，等待進(jìn)行下一步的判斷。只要其中一個(gè)節(jié)點(diǎn)不符合，則該邊不是候選刪除邊。孤立的邊不刪除，以免產(chǎn)生孤點(diǎn)，造成網(wǎng)絡(luò)不連通。判斷候選刪除節(jié)點(diǎn)的方法如下。

(1)判斷該邊一個(gè)頂點(diǎn)刪除后，集聚系數(shù)是否變大。若不變或變小，不刪除；若變大，則作為候選刪除節(jié)點(diǎn)，等待進(jìn)一步判斷。

對于連邊lef的兩個(gè)節(jié)點(diǎn)e,f，其中的節(jié)點(diǎn)e集聚系數(shù)Ce為：

(1)

式中Ee表示節(jié)點(diǎn)e的鄰節(jié)點(diǎn)之間實(shí)際相連的邊數(shù)，Ke表示節(jié)點(diǎn)e的度。

設(shè)，邊lef刪除前節(jié)點(diǎn)e的集聚系數(shù)為Ce，刪邊后集聚系數(shù)為Ce′ ，則：

當(dāng)Ce′>Ce，節(jié)點(diǎn)e為候選刪除節(jié)點(diǎn)；Ce′≤Ce，不刪除。

(2)以同樣的方法判斷邊的另一節(jié)點(diǎn)f是否為候選刪除節(jié)點(diǎn)。

3.2 考慮邊的介數(shù)大小

若邊的局部介數(shù)低于某一閾值，例如，低于平均局部介數(shù)的n倍，則考慮刪邊，否則不刪邊。以邊lef為例：

設(shè)邊lef的局部介數(shù)為Blef；兩跳鄰居范圍內(nèi)平均局部介數(shù)為Bav。則：

當(dāng)Blef≤nBav，考慮刪邊；Blef>nBav，不刪邊。

設(shè)某條邊兩端節(jié)點(diǎn)各兩跳鄰居所圍成的區(qū)域內(nèi)節(jié)點(diǎn)數(shù)為m，則計(jì)算復(fù)雜度為O(m2)。

3.3 考慮邊的連通概率

設(shè)邊lef的連通概率為CPlef，網(wǎng)絡(luò)的平均連通概率為CPav，則：

當(dāng)CPlef≤CPav，考慮刪邊；CPlef>CPav，不刪邊。

4 仿真及性能分析

仿真采用Visual C++ 開發(fā)，500個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布于800 m×800 m正方形區(qū)域內(nèi)，節(jié)點(diǎn)通信半徑r=80 m，在信號覆蓋范圍內(nèi)的節(jié)點(diǎn)間連邊生成網(wǎng)絡(luò)拓?fù)鋱D。以下的數(shù)據(jù)為50次運(yùn)行結(jié)果的平均值，仿真結(jié)果及實(shí)驗(yàn)數(shù)據(jù)分析如下。

4.1 網(wǎng)絡(luò)平均集聚系數(shù)的比較

圖4 為算法作用下，不同的局部介數(shù)取值時(shí)平均集聚系數(shù)增長情況。

圖4 不同局部介數(shù)取值時(shí)網(wǎng)絡(luò)平均集聚系數(shù)增長比率

從圖4中可以看出，算法作用下的網(wǎng)絡(luò)平均集聚系數(shù)得到較大幅度的提高，在局部介數(shù)取平均局部介數(shù)的3倍時(shí)，網(wǎng)絡(luò)的集聚系數(shù)增長比率接近32%。在網(wǎng)絡(luò)得到較好的簡化的同時(shí)，表現(xiàn)出較高的集聚性。但是，當(dāng)局部介數(shù)取值為平均局部介數(shù)的5倍時(shí)，此時(shí)網(wǎng)絡(luò)出現(xiàn)不連通的簇。因此，實(shí)際應(yīng)用中對局部介數(shù)的取值，需在連通性和平均集聚系數(shù)增長比率兩者中綜合考量，在保證網(wǎng)絡(luò)連通性的同時(shí)使網(wǎng)絡(luò)平均集聚系數(shù)增長比率達(dá)到理想值。

4.2 網(wǎng)絡(luò)平均連通概率的比較

圖5為不同平均局部介數(shù)取值下，原始網(wǎng)絡(luò)及算法作用下兩種網(wǎng)絡(luò)平均連通概率的比較。

圖5 網(wǎng)絡(luò)連通概率增長比率比較

由圖5可見，在算法作用下，網(wǎng)絡(luò)的平均連通概率大大提高，和原始網(wǎng)絡(luò)相比，提高近20%。

4.3 原始拓?fù)鋱D與刪邊后的拓?fù)鋱D比較

圖6、圖7為原始網(wǎng)絡(luò)拓?fù)鋱D及局部介數(shù)取平均局部介數(shù)3倍時(shí)，算法作用下所得拓?fù)鋱D的部分截圖。

圖6 原始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖 圖7 算法作用下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

將圖6和圖7進(jìn)行比較可知，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)大大簡化，簇結(jié)構(gòu)明顯，并且能保持全網(wǎng)連通。

5 結(jié) 論

理論分析和仿真實(shí)驗(yàn)表明，通過本文的算法進(jìn)行刪邊后，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)得到簡化，簇結(jié)構(gòu)更加明顯，網(wǎng)絡(luò)平均集聚系數(shù)得到大幅度提高，表現(xiàn)出更高的集聚性。同時(shí)，網(wǎng)絡(luò)的平均連通概率增幅較大，全網(wǎng)的連通性能更好，網(wǎng)絡(luò)獲得更好的通信質(zhì)量。