劉 海， 馮 勇， 張 彬， 高恩才

(1.昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650504;2.紅云紅河集團(tuán) 紅河卷煙廠，云南 彌勒 652300)

基于可靠連通支配集的高效虛擬骨干網(wǎng)構(gòu)建算法*

劉 海1， 馮 勇1， 張 彬1， 高恩才2

(1.昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南昆明650504;2.紅云紅河集團(tuán)紅河卷煙廠，云南彌勒652300)

在概率性無線傳感器網(wǎng)絡(luò)模型中，提出了一種基于可靠連通支配集的高效虛擬骨干網(wǎng)構(gòu)建算法(EVBP-RCDS)。在刪除網(wǎng)絡(luò)中低于節(jié)點(diǎn)遞交概率閾值的連接基礎(chǔ)上，通過遞減節(jié)點(diǎn)遞交概率和對(duì)比節(jié)點(diǎn)遞交概率有效度(EDDP)之和構(gòu)建出所提出的可靠連通支配集；非支配節(jié)點(diǎn)選取與其相鄰的擁有最高遞交概率的支配節(jié)點(diǎn)傳輸數(shù)據(jù)。仿真實(shí)驗(yàn)表明：與現(xiàn)有文獻(xiàn)中的兩種算法相比，EVBP-RCDS算法能高效擴(kuò)展網(wǎng)絡(luò)生存時(shí)間和降低網(wǎng)絡(luò)延遲。

遞交概率； 遞交概率閾值； 遞交概率有效度； 可靠連通支配集

0 引 言

虛擬骨干網(wǎng)可以使無線傳感器網(wǎng)絡(luò)獲得較好的節(jié)能效果和較高的路由效率[1～4]。處于活躍狀態(tài)的節(jié)點(diǎn)稱為支配(骨干)節(jié)點(diǎn)，負(fù)責(zé)轉(zhuǎn)發(fā)節(jié)點(diǎn)之間的數(shù)據(jù)。處于休眠狀態(tài)的節(jié)點(diǎn)稱為非支配(非骨干)節(jié)點(diǎn)，負(fù)責(zé)發(fā)送本節(jié)點(diǎn)監(jiān)測(cè)數(shù)據(jù)。在減少網(wǎng)絡(luò)吞吐率和通信干擾的情況下，虛擬骨干網(wǎng)亦保證了網(wǎng)絡(luò)的連通性和覆蓋性。

目前，國(guó)內(nèi)外一些經(jīng)典的無線傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)構(gòu)建算法所采用的網(wǎng)絡(luò)模型均基于確定性的網(wǎng)絡(luò)模型(deterministic network model,DNM)，即網(wǎng)絡(luò)中的任何兩個(gè)節(jié)點(diǎn)或者處于連接狀態(tài)，或者處于斷開狀態(tài)。但其忽略了現(xiàn)實(shí)環(huán)境(例如建筑物，植物)以及發(fā)散的信號(hào)強(qiáng)度對(duì)無線傳輸?shù)挠绊慬5]。因此，更現(xiàn)實(shí)的網(wǎng)絡(luò)模型應(yīng)該是概率性網(wǎng)絡(luò)模型(probabilistic network model,PNM)，在這種網(wǎng)絡(luò)模型下，每一對(duì)節(jié)點(diǎn)間均存在著一個(gè)遞交概率(γij)。由于節(jié)點(diǎn)間遞交概率的存在，因此，保證網(wǎng)絡(luò)的可靠性已經(jīng)成為概率性無線傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)構(gòu)建的首要問題。

文獻(xiàn)[6～9]研究中，網(wǎng)絡(luò)可靠性低，在保證概率性無線傳感器網(wǎng)絡(luò)可靠性方面，尤其是保證作為網(wǎng)絡(luò)主要數(shù)據(jù)傳輸通道的支配節(jié)點(diǎn)之間的可靠性方面，并沒有予以論證。

本文提出了一種基于可靠連通支配集的高效虛擬骨干網(wǎng)構(gòu)建算法(efficient virtual backbones network based on reliability connected dominating sets,EVBP-RCDS)。算法的核心思想是優(yōu)先保證作為數(shù)據(jù)傳輸通道的支配節(jié)點(diǎn)之間的可靠性，在此基礎(chǔ)上，最大程度提高非支配節(jié)點(diǎn)與支配節(jié)點(diǎn)之間的可靠性。

1 網(wǎng)絡(luò)模型和EVBP-RCDS算法

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

如圖1,在PNM中，模擬無線傳感器網(wǎng)絡(luò)作為無向圖G(V,E,γ(E))，V為所有n個(gè)節(jié)點(diǎn)vi的集合,0≤i0，γij表明節(jié)點(diǎn)vi和節(jié)點(diǎn)vj間成功傳輸一個(gè)數(shù)據(jù)包的概率，γ(E)={γij|(vi,vj) ∈E,0<γij≤1}。假設(shè)連接時(shí)是無向的，則節(jié)點(diǎn)遞交概率和接收概率均為γij[8]。

圖1 概率性無線傳感器網(wǎng)絡(luò)模型

1.2 EVBP-RCDS算法

EVBP-RCDS算法[10]對(duì)于某些擁有較大遞交概率的邊界節(jié)點(diǎn)對(duì)，不符合支配節(jié)點(diǎn)的構(gòu)建規(guī)則；擁有最大鄰居節(jié)點(diǎn)數(shù)目并且與其鄰居節(jié)點(diǎn)之間的遞交概率過小的節(jié)點(diǎn)同樣不符合構(gòu)建高效骨干網(wǎng)的原則。

因此，本文提出了節(jié)點(diǎn)遞交概率閾值的概念，以解決骨干節(jié)點(diǎn)間遞交概率過小的問題；節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的遞交概率高于或者等于節(jié)點(diǎn)遞交概率閾值的數(shù)目，即節(jié)點(diǎn)遞交概率有效度(effective degree of delivery probability,EDDP)，在此基礎(chǔ)上構(gòu)建了骨干網(wǎng)，解決了邊界節(jié)點(diǎn)的問題。因此，提高骨干節(jié)點(diǎn)之間的可靠性轉(zhuǎn)化為尋找一些擁有最大遞交概率和最大EDDP的節(jié)點(diǎn)作為支配節(jié)點(diǎn)。

1.2.1 遞交概率

文獻(xiàn)[10]可知：節(jié)點(diǎn)接收概率與信號(hào)編碼方式和節(jié)點(diǎn)模塊有著固有的聯(lián)系；隨著現(xiàn)實(shí)條件的變化(例如信噪比，周圍溫度)，節(jié)點(diǎn)接收概率也會(huì)變化；當(dāng)信號(hào)編碼方式和現(xiàn)實(shí)條件固定不變，隨著距離的增大節(jié)點(diǎn)遞交概率以指數(shù)函數(shù)減少。

1.2.2 節(jié)點(diǎn)初始化

為提高支配節(jié)點(diǎn)間的可靠性， EVBP-RCDS算法的第一步是設(shè)置節(jié)點(diǎn)遞交概率閾值，選取高于或等于遞交概率閾值的節(jié)點(diǎn)對(duì)作為候選支配節(jié)點(diǎn)，首先平均節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間的遞交概率如式(1)，然后平均所有節(jié)點(diǎn)的平均遞交概率作為節(jié)點(diǎn)遞交概率閾值如式(2)

(1)

(2)

式(1)中，γi1,γ21,…，γ>0；n為所有節(jié)點(diǎn)的數(shù)目，式(2)中γi1,γ21,…,γij>0；n為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)數(shù)目，根據(jù)圖1和式(2),可以得出

利用式(1)，取保留小數(shù)點(diǎn)后一位的數(shù)字，得出圖1的節(jié)點(diǎn)概率閾值為0.6；刪除低于節(jié)點(diǎn)概率閾值的連接，如果一個(gè)節(jié)點(diǎn)與其所有鄰居節(jié)點(diǎn)的連接均被刪除，則將此節(jié)點(diǎn)涂灰，確定一部分非支配節(jié)點(diǎn)，如圖2(a)所示。

圖2 EVBP-RCDS算法

1.2.3 可靠性連通支配集構(gòu)建

EVBP-RCDS算法的第二步即根據(jù)節(jié)點(diǎn)的遞交概率和節(jié)點(diǎn)EDDP確定支配節(jié)點(diǎn)和剩余非支配節(jié)點(diǎn)。因?yàn)樵谥涔?jié)點(diǎn)的選取過程中，需要用到節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的遞交概率，定義節(jié)點(diǎn)的1跳鄰居如下：

定義1跳鄰居(NP1(vi)),?vi∈V節(jié)點(diǎn)的1跳鄰居為

NP1(vi)={(vj,γij)|vj∈V,γij>0}

(3)

根據(jù)圖2(a)和式(3)，可以得出高于或等于節(jié)點(diǎn)遞交概率閾值的節(jié)點(diǎn)的1跳鄰居。同時(shí)，也可以得出節(jié)點(diǎn)1的EDDP為1，節(jié)點(diǎn)3,6,7,8的EDDP為2，節(jié)點(diǎn)2的EDDP為3，節(jié)點(diǎn)4,5的EDDP為0。

NP1(v1)={(6,0.9)}

NP1(v2)={(3,0.95),(6,0.7),98,0.6}}

NP1(v3)={(2,0.95),(7,0.8)}

NP1(v6)={(1,0.9),(2,0.7)}

NP1(v7)={(3,0.8),(8,0.75)}

NP1(v8)={(7,0.75),(2,0.6)}

為保證支配節(jié)點(diǎn)間的可靠性，首先選取網(wǎng)絡(luò)中連接最大遞交概率的兩個(gè)節(jié)點(diǎn)對(duì)作為初始化的兩個(gè)備選支配節(jié)點(diǎn)，檢測(cè)兩個(gè)備選支配節(jié)點(diǎn)EDDP之和是否最大，是，則確定兩個(gè)備選支配節(jié)點(diǎn)中擁有較大EDDP的為第一個(gè)支配節(jié)點(diǎn)，涂黑此節(jié)點(diǎn)，涂灰其未被遍歷的鄰居節(jié)點(diǎn)；否則，降低為次大遞交概率，繼續(xù)判斷EDDP之和，直至確定第一個(gè)支配節(jié)點(diǎn)。根據(jù)圖2，可知：最大的遞交概率為0.95，連接0.95的節(jié)點(diǎn)2和節(jié)點(diǎn)3又擁有最大的EDDP之和，節(jié)點(diǎn)2的EDDP較節(jié)點(diǎn)3大，因此，確定節(jié)點(diǎn)2為第一個(gè)支配節(jié)點(diǎn)，涂黑節(jié)點(diǎn)2，節(jié)點(diǎn)2的鄰居節(jié)點(diǎn)3，6，8被涂灰，如圖2(b)所示。

在確定第一個(gè)支配節(jié)點(diǎn)后，從支配節(jié)點(diǎn)的未被判斷過的最大遞交概率中，選取下一個(gè)備選支配節(jié)點(diǎn)，然后對(duì)比所有備選支配節(jié)點(diǎn)與支配節(jié)點(diǎn)之間的EDDP和，擁有最大EDDP之和的備選支配節(jié)點(diǎn)確定為下一個(gè)支配節(jié)點(diǎn)，如果最大EDDP之和不止一個(gè)，那么選擇擁有最大遞交概率的備選支配節(jié)點(diǎn)確定為新的支配節(jié)點(diǎn)。如此反復(fù)，直至所有節(jié)點(diǎn)被涂黑或者涂灰。根據(jù)圖2(b)，支配節(jié)點(diǎn)中次大的遞交概率為節(jié)點(diǎn)2與節(jié)點(diǎn)6的0.7，首先確定節(jié)點(diǎn)6為新的備選支配節(jié)點(diǎn)，其EDDP之和為5，而支配節(jié)點(diǎn)2與備選支配節(jié)點(diǎn)3之間的EDDP之和也為5，此時(shí)選擇擁有較大的遞交概率的節(jié)點(diǎn)3作為下一個(gè)支配節(jié)點(diǎn)。節(jié)點(diǎn)3被涂黑，節(jié)點(diǎn)7被涂灰，如圖3(a)所示。圖3(b)所示為構(gòu)建好的可靠性連通支配集。

圖3 EVBP-RCDS算法

1.2.4 非支配節(jié)點(diǎn)與支配節(jié)點(diǎn)的連接

EVBP-RCDS算法的最后一步是非支配節(jié)點(diǎn)選取與其連接的擁有最大遞交概率的支配節(jié)點(diǎn)連接。根據(jù)圖3(b)，非支配節(jié)點(diǎn)1與支配節(jié)點(diǎn)2和6連接，那么非支配節(jié)點(diǎn)1選擇遞交概率較大的節(jié)點(diǎn)6傳輸數(shù)據(jù)，同樣節(jié)點(diǎn)5選擇節(jié)點(diǎn)2，節(jié)點(diǎn)4選擇節(jié)點(diǎn)3，節(jié)點(diǎn)8選擇節(jié)點(diǎn)2，接線7選擇3，結(jié)果如圖4所示。

圖4 可靠性虛擬骨干網(wǎng)

2 仿真結(jié)果及分析

模擬仿真實(shí)驗(yàn)主要是通過與文獻(xiàn)[8]構(gòu)建的LBVBP-MOGA算法和文獻(xiàn)[7]所構(gòu)建的RMCDS-GA進(jìn)行對(duì)比，包括三方面：網(wǎng)絡(luò)生存時(shí)間，網(wǎng)絡(luò)延遲，節(jié)點(diǎn)平均剩余能量。在網(wǎng)絡(luò)生存時(shí)間方面，當(dāng)網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)被認(rèn)為已死亡。

假設(shè)所有的節(jié)點(diǎn)均有相同的傳輸范圍，一致和隨機(jī)性地部署在一個(gè)正方形區(qū)域。對(duì)于每一個(gè)設(shè)定，取100次結(jié)果的平均值。此外，每1個(gè)傳感器節(jié)點(diǎn)在每一個(gè)通信間隔產(chǎn)生尺寸為1的數(shù)據(jù)包，數(shù)據(jù)傳輸過程中，假設(shè)1跳通信時(shí)間為0.1 s，如果數(shù)據(jù)傳輸失敗，那么1 s后繼續(xù)重傳此數(shù)據(jù)包。在能量方面，假定每個(gè)節(jié)點(diǎn)均有1 000單位能量，發(fā)送和接收一個(gè)數(shù)據(jù)包均需要消耗1個(gè)單位的能量。文中變化的參數(shù)為節(jié)點(diǎn)在不同觸發(fā)時(shí)間間隔下的變化情況，假定節(jié)點(diǎn)的觸發(fā)時(shí)間間隔從3 s變化到30 s，每次增加3 s。

1)網(wǎng)絡(luò)生存時(shí)間

圖5為網(wǎng)絡(luò)的生存時(shí)間在不同觸發(fā)間隔下的變化情況。在觸發(fā)間隔大約9 s以前RMCDS-GA算法和EVBP-RCDS算法因?yàn)楸ＷC了支配節(jié)點(diǎn)間的遞交概率，因此，從源節(jié)點(diǎn)接收到的數(shù)據(jù)包能以較短的時(shí)間傳輸?shù)侥康牡兀斐山咏康牡氐年P(guān)鍵路徑節(jié)點(diǎn)過快死亡，縮短了網(wǎng)絡(luò)生存時(shí)間。而LBVBP-MOGA算法支配節(jié)點(diǎn)間的遞交概率普遍偏低，在發(fā)送間隔較短的時(shí)候，大量的數(shù)據(jù)包堵塞在各自傳輸路徑中遞交概率低的節(jié)點(diǎn)處，不會(huì)造成傳輸過程中的關(guān)鍵路徑節(jié)點(diǎn)死亡。隨著觸發(fā)間隔的增大，可靠性低的LBVBP-MOGA算法所引起的網(wǎng)絡(luò)重傳能耗在同等條件下必然降低網(wǎng)絡(luò)的生存時(shí)間。

圖5 網(wǎng)絡(luò)生存時(shí)間

2)網(wǎng)絡(luò)延遲

圖6為網(wǎng)絡(luò)延遲在不同觸發(fā)間隔下的情況。隨著觸發(fā)間隔的增大，最后LBVBP-MOGA算法穩(wěn)定于13 s左右，而RMCDS-GA算法和EVBP-RCDS算法穩(wěn)定在1 s左右。RMCDS-GA算法和EVBP-RCDS算法保證了網(wǎng)絡(luò)的可靠性，減少了數(shù)據(jù)重傳的次數(shù)，進(jìn)而減少了整個(gè)網(wǎng)絡(luò)的延遲。

圖6 網(wǎng)絡(luò)延遲

3)平均剩余能量

圖7為平均剩余能量在不同觸發(fā)間隔下的情況。LBVBP-MOGA算法為對(duì)支配節(jié)點(diǎn)的可靠性予以保證，因此，數(shù)據(jù)包在低概率支配節(jié)點(diǎn)處大量擁塞重傳造成網(wǎng)絡(luò)過快死亡，造成整個(gè)網(wǎng)絡(luò)總體能耗過低。RMCDS-GA算法雖然保證了網(wǎng)絡(luò)的可靠性，但是最小連通支配集導(dǎo)致的擁有多個(gè)非支配節(jié)點(diǎn)連接的單個(gè)支配過早死亡的問題依舊會(huì)發(fā)生。

圖7 平均剩余能量

3 結(jié) 論

本文在概率性無線傳感器網(wǎng)絡(luò)模型中提出了EVBP-RCDS一種基于可靠連通支配集的高效虛擬骨干網(wǎng)構(gòu)建算法。在節(jié)點(diǎn)概率閾值的基礎(chǔ)上，優(yōu)先選擇具有最大遞交概率和最大EDDP的節(jié)點(diǎn)作為支配節(jié)點(diǎn)；在非支配節(jié)點(diǎn)的連接上，選擇與其相鄰的具有最大遞交概率的支配節(jié)點(diǎn)連接。仿真實(shí)驗(yàn)表明：相對(duì)于LBVBP-MOGA算法和RMCDS-GA算法，EVBP-RCDS算法在網(wǎng)絡(luò)性能上高效。

[1] 趙 煜，降愛蓮.一種參考能量的最小連通支配集近似算法[J].傳感器與微系統(tǒng),2015,34(1):145-147.

[2] Schurgers C,Srivastava M B.Energy efficient routing in wireless sensor networks[C]∥Proceedings of the 2001 Military Communications Conference,McLean,Virginia，USA:IEEE,2002:357-361.

[3] Liang X,Li W,Gulliver T A.Energy efficient modulation design for wireless sensor networks[C]∥Proceedings of the 2007 IEEE Pacific Rim Conference on Communications,Computers and Signal Processing,Victoria B C,Canada:IEEE,2007:98-101.

[4] Tseng Yu-Chee,Ni Sze-Yao,Chen Yuh-Shyan,et al.The broadcast storm problem in a mobile Ad Hoc network[J].Wireless Networks,2002,8(2):153-167.

[5] Khalil E A,Ozdemir S.Energy aware evolutionary routing protocol with probabilistic sensing model and wake-up scheduling[C]∥Proceedings of the 2013 IEEE Globecom Workshops(GC Workshops),Atlanta,GA,USA:IEEE,2014:873-878.

[6] Garey M R,Johnson D S.Computers and intractability:A guide to the theory of NP-completeness[M].New York:Wh Freeman & Co,1979.

[7] He J,Cai Z,Ji S,et al.A genetic algorithm for constructing a reliable MCDS in probabilistic wireless networks[J].Ad Hoc & Sensor Wireless Networks,2011,20(3):96-107.

[8] He J,Ji S,Beyah R,et al.A multi-objective genetic algorithm for constructing load-balanced virtual backbones in probabilistic wireless sensor networks[C]∥Proceedings of the 2013 IEEE Global Communications Conference,Atlanta,GA,USA:IEEE,2014:261-266.

[9] Khalil E A,Ozdemir S.CDS-based reliable topology control in WSNs[C]∥Proceedings of the 2015 International Symposium on Networks,Computers and Communications,Hammamet,Tunisia:IEEE,2015:1-5.

[10] Zuniga M,Krishnamachari B.Analyzing the transitional region in low power wireless links[C]∥Proceedings of the 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks,Santa Clara,California，USA:IEEE,2005:517-526.

Algorithmforconstructingefficientvirtualbackbonenetworkbasedonreliableconnecteddominatingsets*

LIU Hai1, FENG Yong1, ZHANG Bin1, GAO En-cai2

(1.YunnanKeyLaboratoryofComputerTechnologyApplication,KunmingUniversityofScienceandTechnology,Kunming650504,China;2.HongheCigaretteFactory,HongyunHongheTobaccoGroup，Mile652300,China)

In probabilistic wireless sensor networks model(PNM),an algorithm for constructing efficient virtual backbones network based on reliability connected dominating sets(EVBP-RCDS) is proposed.On the basis of deleting the links whose delivery probability are lower than the delivery probability threshold,the reliability connected dominating sets are constructed by progressively decreasing the delivery probability and comparing the sum of the effective degree of delivery probability(EDDP).Last,each dominatee selects the neighbor dominators with the maximum delivery probability to transfer data.Through simulations,the EVBP-RCDS can efficiently prolong the network lifetime compared with existing algorithms in literatures and RMCDS-GA algorithm.

delivery probability; delivery probability threshold; effective degree of delivery probability; reliability connected dominating sets

10.13873/J.1000—9787(2017)12—0130—04

TP 212

A

1000—9787(2017)12—0130—04

2016—11—23

國(guó)家自然科學(xué)基金資助項(xiàng)目(61262081,61662042)

劉 海(1990-)，男，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)骨干網(wǎng)構(gòu)建。馮 勇(1975-)，男，通訊作者，博士，副教授， E—mail:seablue2046@163.com。