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

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

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

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

1.2 EVBP-RCDS算法

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

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

1.2.1 遞交概率

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

1.2.2 節(jié)點初始化

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

(1)

(2)

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

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

圖2 EVBP-RCDS算法

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

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

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

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

(3)

根據(jù)圖2(a)和式(3)，可以得出高于或等于節(jié)點遞交概率閾值的節(jié)點的1跳鄰居。同時，也可以得出節(jié)點1的EDDP為1，節(jié)點3,6,7,8的EDDP為2，節(jié)點2的EDDP為3，節(jié)點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é)點間的可靠性，首先選取網(wǎng)絡(luò)中連接最大遞交概率的兩個節(jié)點對作為初始化的兩個備選支配節(jié)點，檢測兩個備選支配節(jié)點EDDP之和是否最大，是，則確定兩個備選支配節(jié)點中擁有較大EDDP的為第一個支配節(jié)點，涂黑此節(jié)點，涂灰其未被遍歷的鄰居節(jié)點；否則，降低為次大遞交概率，繼續(xù)判斷EDDP之和，直至確定第一個支配節(jié)點。根據(jù)圖2，可知：最大的遞交概率為0.95，連接0.95的節(jié)點2和節(jié)點3又擁有最大的EDDP之和，節(jié)點2的EDDP較節(jié)點3大，因此，確定節(jié)點2為第一個支配節(jié)點，涂黑節(jié)點2，節(jié)點2的鄰居節(jié)點3，6，8被涂灰，如圖2(b)所示。

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

圖3 EVBP-RCDS算法

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

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

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

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

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

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

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

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

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

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)而減少了整個網(wǎng)絡(luò)的延遲。

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

3)平均剩余能量

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

圖7 平均剩余能量

3 結(jié) 論

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

國家自然科學(xué)基金資助項目(61262081,61662042)

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