辛強(qiáng)偉

西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710127

1 引言

無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)是指當(dāng)部分節(jié)點(diǎn)失效時(shí)，網(wǎng)絡(luò)仍可繼續(xù)工作的能力。容錯(cuò)在無(wú)線傳感器網(wǎng)絡(luò)中是一個(gè)重要問(wèn)題。無(wú)線傳感器網(wǎng)絡(luò)需要具備一定的容錯(cuò)功能，以確保網(wǎng)絡(luò)能夠應(yīng)對(duì)故障并且長(zhǎng)時(shí)間正常工作，特別是對(duì)于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)。由于傳感節(jié)點(diǎn)以多跳的方式轉(zhuǎn)發(fā)數(shù)據(jù)包，而轉(zhuǎn)發(fā)過(guò)程中有可能會(huì)出現(xiàn)數(shù)據(jù)丟包，轉(zhuǎn)發(fā)次數(shù)越多數(shù)據(jù)丟包越嚴(yán)重。一次數(shù)據(jù)轉(zhuǎn)發(fā)所用時(shí)間往往很短，多次轉(zhuǎn)發(fā)累積的時(shí)間則可能較長(zhǎng)。過(guò)多的跳數(shù)可以導(dǎo)致數(shù)據(jù)丟包率上升、時(shí)延增大，也會(huì)使無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)變差，因而需要減少跳數(shù)。

目前無(wú)線傳感器網(wǎng)絡(luò)中關(guān)于容錯(cuò)包括進(jìn)行故障邊的檢測(cè)[1]，對(duì)數(shù)據(jù)丟失進(jìn)行恢復(fù)[2]以及對(duì)空洞進(jìn)行修正[3]等，然而這些是出現(xiàn)問(wèn)題后的補(bǔ)救辦法，對(duì)于可能出現(xiàn)的故障和問(wèn)題首先需要建立預(yù)防機(jī)制。例如文獻(xiàn)[4]提出了分布式的節(jié)點(diǎn)部署算法以形成具有良好連接的無(wú)線傳感器網(wǎng)絡(luò)，但如何在現(xiàn)有的部署之后提高容錯(cuò)則是更為普遍和重要的問(wèn)題。最小連通支配集（Minimum Connected Dominating Set，MCDS）是一個(gè)圖論概念。在無(wú)線傳感器網(wǎng)絡(luò)中最小連通支配集的應(yīng)用主要集中在減小能耗以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，方法是構(gòu)建支配集作為虛擬骨干網(wǎng)[5]。關(guān)于構(gòu)建支配集的方法有旨在降低網(wǎng)絡(luò)能耗減少支配點(diǎn)的數(shù)目[6]，基于能量代價(jià)的最小權(quán)和支配集[7]以及旨在延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間用馬爾科夫模型優(yōu)化最小連通支配集[8]等。

采用最小連通支配集方法研究容錯(cuò)比較少。這方面主要的研究有：采用最小連通支配集方法以減少冗余轉(zhuǎn)發(fā)節(jié)點(diǎn)[9]；對(duì)最小連通支配集中故障或失效節(jié)點(diǎn)進(jìn)行修復(fù)[10]；用加權(quán)的方法來(lái)分析最小連通支配集，根據(jù)節(jié)點(diǎn)能量以及節(jié)點(diǎn)之間的距離來(lái)定義邊的權(quán)值[11]。這些方法都涉及用最小連通支配集來(lái)解決容錯(cuò)問(wèn)題，還存在著進(jìn)一步優(yōu)化的空間。

此外，近年來(lái)新出現(xiàn)了一些比較重要的關(guān)于無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)的研究。文獻(xiàn)[12]通過(guò)功率控制改變拓?fù)涫姑總€(gè)節(jié)點(diǎn)能耗平衡，從而改善無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)。文獻(xiàn)[13]通過(guò)可替換的路徑來(lái)解決節(jié)點(diǎn)失效的問(wèn)題。容錯(cuò)不僅包括物理連接的可靠性，而且包括路由協(xié)議設(shè)計(jì)的魯棒性。例如文獻(xiàn)[14]設(shè)計(jì)了關(guān)于三維分簇?zé)o線傳感器網(wǎng)絡(luò)的路由，使用動(dòng)態(tài)多層分簇實(shí)現(xiàn)容錯(cuò)。文獻(xiàn)[15]通過(guò)對(duì)大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)包傳輸情況進(jìn)行分析和檢測(cè)，以達(dá)到減少數(shù)據(jù)包丟失以及優(yōu)化大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)部署的目的。

本文與以往研究的不同：一是本文討論了當(dāng)傳感節(jié)點(diǎn)隨機(jī)部署時(shí)無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)，二是從網(wǎng)絡(luò)跳數(shù)的角度（包括平均跳數(shù)和最大跳數(shù)）研究無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)。此外，本文將度與最小連通支配集相結(jié)合以討論容錯(cuò)問(wèn)題，提出了結(jié)合度的最小連通支配集（D-MCDS）容錯(cuò)算法，D-MCDS算法可以提高無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)。

2 基于度構(gòu)建最小連通支配集及相關(guān)分析

2.1 相關(guān)概念

連通率：無(wú)線傳感器網(wǎng)絡(luò)中可以連接通信到最大子網(wǎng)絡(luò)的節(jié)點(diǎn)的個(gè)數(shù)如果是S，則連通率為S/N，連通率記為C。

平均跳數(shù)：用H表示，為任意兩個(gè)節(jié)點(diǎn)之間的跳數(shù)的平均值，若hij為連接兩個(gè)節(jié)點(diǎn)的最短路徑上的邊數(shù)，則

最大跳數(shù)：用Hmax表示，為無(wú)線傳感器網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的距離的最大跳數(shù)。

2.2 基于度構(gòu)建最小連通支配集的分析

在實(shí)際應(yīng)用中發(fā)現(xiàn)：相同條件下，隨著跳數(shù)的增加，丟包率會(huì)呈現(xiàn)上升的趨勢(shì)。因此在無(wú)線傳感器網(wǎng)絡(luò)中減少跳數(shù)對(duì)于容錯(cuò)很重要。本文通過(guò)把最小連通支配集中的節(jié)點(diǎn)及其連接作為骨干網(wǎng)絡(luò)，并通過(guò)節(jié)點(diǎn)隨機(jī)部署時(shí)的特點(diǎn)，尋求一種可以顯著減少無(wú)線傳感器網(wǎng)絡(luò)跳數(shù)的最小連通支配集構(gòu)建方法，以此增強(qiáng)網(wǎng)絡(luò)容錯(cuò)。

節(jié)點(diǎn)數(shù)為N，節(jié)點(diǎn)的通信半徑為R，當(dāng)傳感節(jié)點(diǎn)隨機(jī)部署時(shí)，無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)密度加大，會(huì)使連通率增大。根據(jù)式（2），當(dāng)連通率C達(dá)到100%時(shí)，S就等于N，此時(shí)平均跳數(shù)如式（1）。

當(dāng)傳感節(jié)點(diǎn)隨機(jī)部署時(shí)，按照統(tǒng)計(jì)，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目（即度）會(huì)以某一概率在一定的區(qū)間，如式（5）所示。

假設(shè)置信水平是1-α，則

因此，E(X)的置信區(qū)間為：

由于節(jié)點(diǎn)是隨機(jī)部署，若k和n為部署節(jié)點(diǎn)的數(shù)目，k＜n，Cn為當(dāng)節(jié)點(diǎn)數(shù)目為n時(shí)的連通率：

故Cn的置信區(qū)間為：

根據(jù)以上分析，連通率與無(wú)線傳感器網(wǎng)絡(luò)的平均度成正比，且平均跳數(shù)也與連通率相關(guān)。一條鏈路中含有過(guò)多的跳數(shù)會(huì)導(dǎo)致這條鏈路魯棒性降低。隨機(jī)部署在一區(qū)域內(nèi)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的度受節(jié)點(diǎn)通信距離的限制，如果隨機(jī)部署的節(jié)點(diǎn)較多時(shí)會(huì)造成多數(shù)節(jié)點(diǎn)的度相近，這時(shí)網(wǎng)絡(luò)屬于均勻網(wǎng)絡(luò)。當(dāng)隨機(jī)部署的節(jié)點(diǎn)達(dá)到一定數(shù)量后，即當(dāng)網(wǎng)絡(luò)的平均度達(dá)到一定程度后，再繼續(xù)增加節(jié)點(diǎn)數(shù)目，連通率會(huì)保持為1。

2.3 基于度構(gòu)建最小連通支配集

網(wǎng)絡(luò)的跳數(shù)與度之間存在著某種關(guān)聯(lián)。網(wǎng)絡(luò)的平均度越大，網(wǎng)絡(luò)的跳數(shù)越小。一個(gè)節(jié)點(diǎn)的度（degree）越大即這個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)越多，那么這個(gè)節(jié)點(diǎn)可以支配的節(jié)點(diǎn)越多。綜上考慮，本文基于度構(gòu)建最小連通支配集，具體步驟如下：

步驟1 從集合G中選擇節(jié)點(diǎn){N1，N2，…，Nm}，degree(N1)≥degree(N2)≥…≥degree(Nm)。

步驟2 如果 ? 集合J={N1，N2，…}， 集合J的點(diǎn)與集合M=G-J中的?Ni都存在邊，則進(jìn)行步驟3，否則繼續(xù)往集合J中按度添加節(jié)點(diǎn)。

步驟3選擇集合J={N1，N2，…}中的節(jié)點(diǎn)之間的連接點(diǎn)，集合J的點(diǎn)都可以通信。

步驟4 檢查集合J，如果同時(shí) ? 邊{Nx，Ny}，? 邊{Nx，Nz}，? 邊{Ny，Nz}， 且去除Ny后集合J的點(diǎn)與集合M=G-J中的?Ni都存在邊，則去除Ny。

將提出的算法稱(chēng)為基于度的最小連通支配集（D-MCDS）算法。最小連通支配集目的是讓盡量多的節(jié)點(diǎn)處于休眠狀態(tài)，最大限度地減少中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。此算法的創(chuàng)新點(diǎn)是根據(jù)節(jié)點(diǎn)隨機(jī)部署時(shí)所體現(xiàn)的特點(diǎn)，將度作為構(gòu)建最小連通支配集的依據(jù)，從而較好地減少網(wǎng)絡(luò)跳數(shù)，從而提升了網(wǎng)絡(luò)的容錯(cuò)能力。在拓?fù)淇刂浦袘?yīng)用基于度構(gòu)建的最小連通支配集可以減少冗余轉(zhuǎn)發(fā)節(jié)點(diǎn)，為增強(qiáng)無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)提供了便利。

3 仿真驗(yàn)證

本文模擬了100個(gè)節(jié)點(diǎn)在200×200的平面上隨機(jī)部署，每個(gè)節(jié)點(diǎn)的通信半徑為40，每次隨機(jī)部署10個(gè)節(jié)點(diǎn)，即分10次完成100個(gè)節(jié)點(diǎn)的隨機(jī)部署。

當(dāng)節(jié)點(diǎn)密度偏低時(shí)，會(huì)有一些節(jié)點(diǎn)不能連通。隨著節(jié)點(diǎn)密度的增大，無(wú)線傳感器網(wǎng)絡(luò)的連通情況逐步增強(qiáng)。因此可通過(guò)節(jié)點(diǎn)密度的變化來(lái)分析網(wǎng)絡(luò)跳數(shù)和連通率之間的關(guān)系。

由圖1可發(fā)現(xiàn)，當(dāng)隨機(jī)部署節(jié)點(diǎn)時(shí)，若節(jié)點(diǎn)密度小時(shí)（如圖1（a）所示），網(wǎng)絡(luò)的連通較差，出現(xiàn)了數(shù)個(gè)獨(dú)立的連通分支。隨著節(jié)點(diǎn)密度的增大，網(wǎng)絡(luò)逐漸成為一個(gè)連通圖。節(jié)點(diǎn)密集部署時(shí)（如圖1（b）所示），可以看出節(jié)點(diǎn)之間連接緊密，節(jié)點(diǎn)之間的連接不再單一，而是有多條路徑可供選擇。

從圖2中可以看出，隨著節(jié)點(diǎn)數(shù)目的增加，最小連通支配集的規(guī)模變大。當(dāng)節(jié)點(diǎn)密度達(dá)到一定水平時(shí)，最小連通支配集的大小趨于穩(wěn)定。這是由于節(jié)點(diǎn)密度小時(shí)，網(wǎng)絡(luò)分割為若干個(gè)獨(dú)立的連通分支。

本文在討論無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)中，使用了最大跳數(shù)和平均跳數(shù)兩個(gè)概念。最大跳數(shù)的意義在于可被視為最壞情況，平均跳數(shù)的意義在于可被視為一般情況。設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)時(shí)如對(duì)系統(tǒng)有很高容錯(cuò)要求，應(yīng)準(zhǔn)備最壞情況的發(fā)生，即準(zhǔn)備應(yīng)對(duì)最大跳數(shù)的出現(xiàn)。

將提出的基于度的D-MCDS算法和GAF（Geographic Adaptive Fidelity）算法進(jìn)行比較。GAF算法把監(jiān)測(cè)區(qū)域劃分為若干虛擬單元格，根據(jù)節(jié)點(diǎn)的位置信息將節(jié)點(diǎn)劃歸到相應(yīng)的單元格，每個(gè)單元格按一定周期選舉一個(gè)簇頭節(jié)點(diǎn)。比較的情況如圖3所示。隨著節(jié)點(diǎn)數(shù)目的增加，最大跳數(shù)變大。當(dāng)節(jié)點(diǎn)密度達(dá)到一定水平時(shí)，最大跳數(shù)趨于穩(wěn)定。D-MCDS算法和GAF算法的最大跳數(shù)的最大值都出現(xiàn)在網(wǎng)絡(luò)連通率達(dá)到1之后。

圖1 隨機(jī)部署時(shí)節(jié)點(diǎn)密度增大對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響

圖2 最小連通支配集大小

圖3 網(wǎng)絡(luò)最大跳數(shù)

采用D-MCDS算法的仿真結(jié)果有兩種情況：（1）當(dāng)連通率在隨機(jī)部署40個(gè)節(jié)點(diǎn)達(dá)到1時(shí)，最大跳數(shù)和平均跳數(shù)基本都達(dá)到最大值；（2）當(dāng)連通率在部署40個(gè)節(jié)點(diǎn)達(dá)到1后，隨著節(jié)點(diǎn)密度的增大，平均跳數(shù)逐漸出現(xiàn)小幅下降的趨勢(shì)。當(dāng)節(jié)點(diǎn)相對(duì)稀疏時(shí)，會(huì)有一些節(jié)點(diǎn)相互之間不能連通。在全面連通之后繼續(xù)增加節(jié)點(diǎn)，會(huì)產(chǎn)生冗余節(jié)點(diǎn)，使得網(wǎng)絡(luò)具備一定的容錯(cuò)性，因而一定數(shù)量的冗余節(jié)點(diǎn)是必要的。

仿真結(jié)果揭示了隨機(jī)部署節(jié)點(diǎn)達(dá)到一定的密度時(shí)（即當(dāng)隨機(jī)部署節(jié)點(diǎn)的連通率剛達(dá)到1時(shí)），此刻無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)是最弱的。而當(dāng)達(dá)到一定的密度后（即當(dāng)隨機(jī)部署節(jié)點(diǎn)的連通率達(dá)到1后），再增大節(jié)點(diǎn)的密度會(huì)對(duì)無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)起到增強(qiáng)作用。

從圖4可見(jiàn)，當(dāng)節(jié)點(diǎn)密度較低時(shí)，隨著節(jié)點(diǎn)數(shù)目的增大，平均跳數(shù)較快增大。當(dāng)節(jié)點(diǎn)密度達(dá)到一定水平后，平均跳數(shù)逐漸小幅減小。當(dāng)實(shí)現(xiàn)節(jié)點(diǎn)隨機(jī)密集部署后，D-MCDS算法所形成的網(wǎng)絡(luò)最大跳數(shù)和平均跳數(shù)都要小于GAF算法。

圖4 網(wǎng)絡(luò)平均跳數(shù)

4 結(jié)論

由于多跳會(huì)對(duì)無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)帶來(lái)影響，因而減少無(wú)線傳感器網(wǎng)絡(luò)的跳數(shù)具有現(xiàn)實(shí)意義。本文探討基于度構(gòu)建的最小連通支配集對(duì)跳數(shù)的影響以及網(wǎng)絡(luò)跳數(shù)和連通率之間的關(guān)系。若節(jié)點(diǎn)隨機(jī)部署，當(dāng)節(jié)點(diǎn)密度較大時(shí)，使用基于度的最小連通支配集算法可以有效地減小網(wǎng)絡(luò)的最大跳數(shù)和平均跳數(shù)，從而建立具有一定容錯(cuò)能力的無(wú)線傳感器網(wǎng)絡(luò)。

[1]Ma Qiang，Liu Kebin，Xiao Xiangrong，et al.Link scanner：faulty link detection for wireless sensor network[C]//Proc of International Conference on Computer Communications，Turin，Italy，2013：2788-2796.

[2]Kong Linghe，Xia Mingyuan，Liu Xiaoyang，et al.Data Loss and reconstruction in sensor networks[C]//Proc of International Conference on Computer Communications，Turin，Italy，2013：1702-1710.

[3]Shen Yilin，Nguyen D T，et al.Adaptive approximation algorithms for hole healing in hybrid wireless sensor networks[C]//Proc of International Conference on Computer Communications，Turin，Italy，2013：1202-1210.

[4]Friend A J，Manshadi V H，Saberi A.Distributed node placement algorithms for constructing well-connected sensor networks[C]//Proc of International Conference on Computer Communications，Orlando，America，2012：810-818.

[5]Du Hongwei，Ye Qiang，Wu Weili，et al.Constant approximation for virtual backbone construction with guaranteed routing cost in wireless sensor networks[C]//Proc ofInternationalConferenceonComputerCommunications，Shanghai，China，2011：1737-1744.

[6]Navid N，Christian B.Topology management for improving routing and network performancesin mobilead hoc networks[J].MobileNetworksand Applications，2004，9（6）：583-594.

[7]孫超，尹榮榮，郝曉辰，等.WSNs中基于能量代價(jià)的最小權(quán)和支配集拓?fù)淇刂扑惴╗J].電子與信息學(xué)報(bào)，2010，32（4）：857-863.

[8]汪文勇，向渝，董傳坤，等.用馬爾科夫模型優(yōu)化分布式最小連通支配集算法[J].電子學(xué)報(bào)，2010，38（10）：2441-2446.

[9]唐勇，周明天.基于極大獨(dú)立集的最小連通支配集的分布式算法[J].電子學(xué)報(bào)，2007，35（5）：868-874.

[10]Rai M，Verma S，Tapaswi S.A heuristic for minimum connected dominating set with local repair for wireless sensornetworks[C]//8th InternationalConference on Networks，2009：106-111.

[11]Shaikot S H，Sarangan V.Energy aware routing in high capacity overlays in wireless sensor networks[C]//Proc ofComputerSystemsand Applications，Doha，Qatar，2008：276-283.

[12]Kumar K V，Karthikeyan S.Multihop energy efficient reliable and fault tolerant routing protocol for wireless sensor networks[J].International Journal of Emerging Technology and Advanced Engineering，2013，3（2）：395-409.

[13]Chanak P，Samanta T，Banerjee I.Fault-tolerant multipath routing scheme for energy efficient wireless sensor networks[J].InternationalJournalof Wireless &Mobile Networks，2013，5（2）：33-45.

[14]Hasannejad M，Mehrani M，Hoodgar M.Fault tolerant dynamic multi level coverage for clustered three dimensional wireless sensor networks[J].Journal of Academic and Applied Studies，2013，3（6）：18-30.

[15]Dong Wei，Liu Yunhao，He Yuan，etal.Measurement and analysis on the packet delivery performance in a large-scale sensornetwork[J].IEEE/ACM Transactions on Networking，2014，22（6）：1952-1963.