異構(gòu)多跳無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/h1>
2015-05-25 00:32:19劉興川吳振鋒趙克儉
系統(tǒng)工程與電子技術(shù) 2015年8期
劉興川，吳振鋒，趙克儉
（中國(guó)電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)多跳無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/p>
劉興川，吳振鋒，趙克儉
（中國(guó)電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)（heterogeneous wireless sensor works，HWSN）能有效降低數(shù)據(jù)轉(zhuǎn)發(fā)延遲、網(wǎng)絡(luò)能量消耗，是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，基于HWSN的k容錯(cuò)性拓?fù)淇刂剖且活怤P-難問(wèn)題。在綜合分析HWSN網(wǎng)絡(luò)模型的基礎(chǔ)上，本文設(shè)計(jì)了簡(jiǎn)化網(wǎng)絡(luò)圖構(gòu)建方法，通過(guò)構(gòu)造有序鄰集來(lái)約束節(jié)點(diǎn)的最大發(fā)射功率，以網(wǎng)絡(luò)總功耗與容錯(cuò)性雙優(yōu)化為目標(biāo)，實(shí)現(xiàn)了一個(gè)k容錯(cuò)性分布式拓?fù)淇刂扑惴ǎ╧-fault-tolerant distributed topology control，k-FTDTC）。實(shí)驗(yàn)結(jié)果表明，相比分布式拓?fù)淇刂疲╠istributed adaptive topology control，DATC）方法，k-FTDTC算法有效降低了網(wǎng)絡(luò)總功耗和最大發(fā)射功率，且具有較好的容錯(cuò)性和較低算法復(fù)雜度。
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；有序鄰集；容錯(cuò)性
0 引 言
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)（heterogeneous wireless sensor networks，HWSN）是指由多種不同類型的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，傳感器節(jié)點(diǎn)的異構(gòu)性主要表現(xiàn)在：計(jì)算能力異構(gòu)、通信能力異構(gòu)以及節(jié)點(diǎn)能量異構(gòu)［1－2］。無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）早期的拓?fù)淇刂蒲芯恐饕性谕瑯?gòu)WSN，即網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有相同的軟硬件能力，被隨機(jī)部署在監(jiān)測(cè)區(qū)域，地位平等，開(kāi)展能量最優(yōu)化研究［3－5］。然而在實(shí)際環(huán)境中，傳感器節(jié)點(diǎn)通常承擔(dān)不同的角色功能，甚至具有不同的資源配置以適應(yīng)多樣化的應(yīng)用需求。此外，即使是同構(gòu)的WSN，由于節(jié)點(diǎn)感知任務(wù)的不同所造成的能耗不同，也促使初始能量相同的網(wǎng)絡(luò)逐漸演變成多級(jí)能量異構(gòu)網(wǎng)絡(luò)。可見(jiàn)，HWSN是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，最近的研究成果［6－8］也表明，相比同構(gòu)網(wǎng)絡(luò)架構(gòu)，HWSN有效降低了監(jiān)測(cè)數(shù)據(jù)轉(zhuǎn)發(fā)延遲、網(wǎng)絡(luò)能量消耗，具有更優(yōu)的網(wǎng)絡(luò)性能。
本文研究的HWSN是由兩類傳感器節(jié)點(diǎn)組成：一類是資源受限隨機(jī)部署的傳感器節(jié)點(diǎn)，稱為普通節(jié)點(diǎn)（common node，CN），用于感知監(jiān)測(cè)異常事件；一類是高能力定點(diǎn)部署的超級(jí)節(jié)點(diǎn)（super node，SN），組成骨干網(wǎng)絡(luò)，完成數(shù)據(jù)融合和快速轉(zhuǎn)發(fā)等任務(wù)，如圖1所示。CN節(jié)點(diǎn)通過(guò)多跳方式與SN節(jié)點(diǎn)進(jìn)行通信，由于復(fù)雜惡劣環(huán)境的影響，經(jīng)常導(dǎo)致CN節(jié)點(diǎn)間通信鏈路失效，再加上CN節(jié)點(diǎn)能量受限，如何在保證網(wǎng)絡(luò)具有容錯(cuò)性的基礎(chǔ)上最優(yōu)化網(wǎng)絡(luò)能量消耗成為HWSN拓?fù)淇刂曝叫杞鉀Q的一個(gè)難題。
圖1 異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)模型
針對(duì)上述問(wèn)題，文獻(xiàn)［9－11］利用同構(gòu)網(wǎng)絡(luò)中已有的研究成果，提出了通過(guò)構(gòu)造網(wǎng)絡(luò)的k點(diǎn)連通圖建立容錯(cuò)性拓?fù)洌淳W(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間都至少存在k條不相交的路徑，當(dāng)任意k－1個(gè)節(jié)點(diǎn)或鏈路發(fā)生故障時(shí)，網(wǎng)絡(luò)仍然保持連通，該方法可有效提高網(wǎng)絡(luò)容錯(cuò)性，但是由于任意節(jié)點(diǎn)都要保持k條不相交的路徑，因此導(dǎo)致整個(gè)網(wǎng)絡(luò)能耗隨其容錯(cuò)能力的提升成倍增加。文獻(xiàn)［12－13］證明了k點(diǎn)連通圖構(gòu)建是一個(gè)NP-難問(wèn)題，需要對(duì)該問(wèn)題進(jìn)行簡(jiǎn)化，求其次優(yōu)解，同時(shí)分別提出了兩種集中式近似求解算法，但是對(duì)于節(jié)點(diǎn)數(shù)據(jù)眾多的WSN而言，集中式拓?fù)淇刂扑惴ú⒉焕诰W(wǎng)絡(luò)規(guī)模的擴(kuò)展。隨后，文獻(xiàn)［14－15］針對(duì)HWSN容錯(cuò)性拓?fù)淇刂?，基于?jié)點(diǎn)剩余能量，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，提出k點(diǎn)連通圖的分布式近似求解算法。但是在多跳網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量多少并不能準(zhǔn)確反映節(jié)點(diǎn)剩余生命周期的長(zhǎng)短，需要綜合考慮節(jié)點(diǎn)的剩余能量和能量消耗速度，同時(shí)這些方法也沒(méi)有對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行控制，因此導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗不均衡。
綜上所述，文獻(xiàn)［9－15］研究的問(wèn)題與本文相似，目標(biāo)都是在保證網(wǎng)絡(luò)具有k容錯(cuò)性的基礎(chǔ)上，最小化網(wǎng)絡(luò)總功耗。本文與上述工作的不同之處主要體現(xiàn)在：①在HWSN中，感知數(shù)據(jù)從CN節(jié)點(diǎn)發(fā)送到SN節(jié)點(diǎn)，因此在任意兩個(gè)節(jié)點(diǎn)之間都保持k條不相交的路徑是沒(méi)有必要的，重要的是使每一個(gè)CN節(jié)點(diǎn)存在k條不相交的路徑可達(dá)SN節(jié)點(diǎn)?；谏鲜鏊枷?，本文設(shè)計(jì)的目標(biāo)函數(shù)是保證任意CN節(jié)點(diǎn)與SN節(jié)點(diǎn)集都存在k條不相交的路徑，在此基礎(chǔ)上最小化網(wǎng)絡(luò)總功耗。②綜合分析異構(gòu)多跳WSN的特點(diǎn)，設(shè)計(jì)簡(jiǎn)化圖方法來(lái)對(duì)HWSN網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，以降低算法求解復(fù)雜度；通過(guò)構(gòu)造CN節(jié)點(diǎn)的有序鄰集來(lái)控制節(jié)點(diǎn)的最大發(fā)射功率，以最小化網(wǎng)絡(luò)總功耗與能量均衡雙優(yōu)化為目標(biāo)，實(shí)現(xiàn)k容錯(cuò)性分布式拓?fù)淇刂疲╧-fault-tolerant distributed topology control，k-FTDTC）算法，提高網(wǎng)絡(luò)健壯性。③基于仿真實(shí)驗(yàn)，對(duì)本文提出的k-FTDTC算法性能進(jìn)行了詳實(shí)的評(píng)估，同時(shí)與經(jīng)典的分布式拓?fù)淇刂疲╠istributed adaptive topology control，DATC）算法［15］進(jìn)行性能比較，以驗(yàn)證本文算法的有效性。
1 網(wǎng)絡(luò)模型與問(wèn)題描述
式中，Pr表示接收功率；λ為電磁波長(zhǎng)；d0為參考距離，一般為1m，d是發(fā)射天線與接收天線之間的距離；n是路徑損耗系數(shù)；G1，G2分別是發(fā)射天線增益和接收天線增益。
根據(jù)上述假設(shè)，CN節(jié)點(diǎn)和SN節(jié)點(diǎn)共同構(gòu)成一個(gè)連通的網(wǎng)絡(luò)，可抽象為一個(gè)無(wú)向加權(quán)網(wǎng)絡(luò)圖G＝（V，E，ω），其中點(diǎn)集V包含N個(gè)CN節(jié)點(diǎn)和M個(gè)SN節(jié)點(diǎn)，即V＝｛n1，n2，…，nN＋1，…，nN＋M｝，前N個(gè)為CN節(jié)點(diǎn)，后M個(gè)為SN節(jié)點(diǎn)。E為邊集，定義為E＝｛（ni，nj）｜dist（ni，nj）≤Dmax｝，其中dist（·）為歐式距離函數(shù)。ω為對(duì)應(yīng)E中每條邊的權(quán)值集合。下面給出用到的幾個(gè)定義：
定義1 邊的權(quán)重：用ω（ni，nj）表示，定義為節(jié)點(diǎn)ni與nj間通信所需的最小發(fā)射功率，具體值可以通過(guò)式（1）計(jì)算。
定義2 可達(dá)鄰集：用F（ni）表示，定義為節(jié)點(diǎn)ni以最大傳輸距離Dmax進(jìn)行通信，所能到達(dá)的節(jié)點(diǎn)集合，即F（ni）＝｛nj｜nj∈V，（ni，nj）∈E｝。
定義3 節(jié)點(diǎn)的功率：用P（ni）表示，定義為P（ni）＝
1.1 網(wǎng)絡(luò)模型
本文討論的HWSN網(wǎng)絡(luò)模型如圖1所示，包括N個(gè)CN節(jié)點(diǎn)和M個(gè)SN節(jié)點(diǎn)，其中M?N。其中，CN節(jié)點(diǎn)隨機(jī)分布，能量受限，具有短的通信能力和低的數(shù)據(jù)速率，主要任務(wù)是實(shí)時(shí)感知監(jiān)測(cè)目標(biāo)的信息，周期性地將感知數(shù)據(jù)通過(guò)多跳方式傳送給附近的SN節(jié)點(diǎn)，其主要的能耗來(lái)自于數(shù)據(jù)的無(wú)線收發(fā)。相比CN節(jié)點(diǎn)，SN節(jié)點(diǎn)具有更多能量、更強(qiáng)的計(jì)算存儲(chǔ)能力、更長(zhǎng)的通信距離和更高的數(shù)據(jù)速率，SN節(jié)點(diǎn)間形成骨干網(wǎng)絡(luò)，主要負(fù)責(zé)對(duì)CN節(jié)點(diǎn)的感知數(shù)據(jù)進(jìn)行融合處理、判決計(jì)算，實(shí)時(shí)可靠地將結(jié)果轉(zhuǎn)發(fā)給監(jiān)測(cè)中心。SN節(jié)點(diǎn)的應(yīng)用不僅延長(zhǎng)了整個(gè)網(wǎng)絡(luò)生命周期，還降低了端到端的數(shù)據(jù)傳輸延遲，因此，該結(jié)構(gòu)在實(shí)際中被廣泛研究和應(yīng)用［16－17］。上述模型滿足以下假設(shè)條件：
（1）CN節(jié)點(diǎn)隨機(jī)密集部署，具有相同的軟硬件，初始能量相同且為Einit，通信距離可調(diào)節(jié)，最大通信距離為Dmax；
（2）SN節(jié)點(diǎn)為高能力節(jié)點(diǎn)，定點(diǎn)部署，初始能量定義為Einit（1＋K），其中K表示SN節(jié)點(diǎn)能量是CN節(jié)點(diǎn)能量的倍數(shù)；
（3）CN節(jié)點(diǎn)間、CN節(jié)點(diǎn)與SN節(jié)點(diǎn)間的通信鏈路是本文拓?fù)淇刂蒲芯康闹攸c(diǎn)，而由于SN節(jié)點(diǎn)為定點(diǎn)部署且為高能力節(jié)點(diǎn)，本文認(rèn)為SN節(jié)點(diǎn)間通信鏈路是固定可靠的，不屬于本文拓?fù)淇刂脐P(guān)注的重點(diǎn)。
（4）CN節(jié)點(diǎn)與SN節(jié)點(diǎn)分布在二維平面上，形成一個(gè)靜態(tài)連通性網(wǎng)絡(luò)，鏈路具有對(duì)稱性，每個(gè)節(jié)點(diǎn)具有唯一ID，節(jié)點(diǎn)間通信滿足文獻(xiàn)［18］提出的無(wú)線信道模型，即max｛nj｜（ni，nj）∈E｝ω（ni，nj）。
定義4 網(wǎng)絡(luò)圖G總的功耗：用P（G）表示，為圖G中各節(jié)點(diǎn)功率之和，即
定義5 k點(diǎn)連通SN節(jié)點(diǎn)集：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)SN節(jié)點(diǎn)集，即任意k－1個(gè)CN節(jié)點(diǎn)或鏈路出現(xiàn)故障時(shí)，網(wǎng)絡(luò)仍保持連通，即CN節(jié)點(diǎn)的感知數(shù)據(jù)能通過(guò)SN節(jié)點(diǎn)傳送到監(jiān)控中心。
1.2 問(wèn)題描述及簡(jiǎn)化
基于上述異構(gòu)多跳網(wǎng)絡(luò)模型，k-FTDTC算法的目標(biāo)是：①通過(guò)調(diào)節(jié)CN節(jié)點(diǎn)的功率，使每個(gè)CN節(jié)點(diǎn)與SN節(jié)點(diǎn)集間存在k條不相交的路徑；②優(yōu)化CN節(jié)點(diǎn)的最大發(fā)射功率，并使所有CN節(jié)點(diǎn)功耗之和最小，即
結(jié)合k-FTDTC問(wèn)題描述，本文將網(wǎng)絡(luò)圖G＝（V，E，ω）進(jìn)行簡(jiǎn)化求解，簡(jiǎn)化規(guī)則如下：
（1）用一個(gè)根節(jié)點(diǎn)取代M個(gè)SN節(jié)點(diǎn)，形成的新點(diǎn)集為V1＝｛n1，n2，…，nN，root｝，這是因?yàn)檠芯勘砻鱏N節(jié)點(diǎn)間的通信鏈路是可靠的［17］。
（2）節(jié)點(diǎn)之間的邊保持不變，若同一個(gè)CN節(jié)點(diǎn)與兩個(gè)或兩個(gè)以上的SN節(jié)點(diǎn)相連，則僅保留邊權(quán)值最小的那條邊。這是因?yàn)閗-FTDTC的目標(biāo)是使CN節(jié)點(diǎn)與SN連通并最小化CN節(jié)點(diǎn)發(fā)射功率。
（3）邊的權(quán)重保持不變。
利用上述規(guī)則設(shè)計(jì)算法1將網(wǎng)絡(luò)圖G＝（V，E，ω）轉(zhuǎn)化為簡(jiǎn)化圖G1＝（V1，E1，ω1），簡(jiǎn)化圖偽代碼如表1所示。
表1 簡(jiǎn)化圖G1構(gòu)建算法偽代碼
定義6 簡(jiǎn)化圖k點(diǎn)連通root節(jié)點(diǎn)：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則稱簡(jiǎn)化圖k點(diǎn)連通root節(jié)點(diǎn)。
根據(jù)定義7可以獲得定理1。
定理1 異構(gòu)多跳WSN是k點(diǎn)連通SN節(jié)點(diǎn)當(dāng)且僅當(dāng)對(duì)應(yīng)的簡(jiǎn)化圖是k點(diǎn)連通root節(jié)點(diǎn)。
證明 （1）必要性。由于異構(gòu)多跳WSN是k點(diǎn)連通SN節(jié)點(diǎn)，即?ni∈V且i≤N的節(jié)點(diǎn)，都存在k條不相交的路徑到達(dá)SN節(jié)點(diǎn)集。用根節(jié)點(diǎn)root取代每條路徑上的SN節(jié)點(diǎn)，即獲得任意CN節(jié)點(diǎn)即?ni∈V且i≤N與根節(jié)點(diǎn)root之間的k條不相交的路徑，即簡(jiǎn)化圖G1是k點(diǎn)連通root節(jié)點(diǎn)。
（2）充分性。如果簡(jiǎn)化圖G1是k點(diǎn)連通root節(jié)點(diǎn)，則表明對(duì)于任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)。因此，對(duì)于圖G1中到根節(jié)點(diǎn)的任意路徑｛ni0，ni1，…，nim，root｝，都可以通過(guò)用一個(gè)SN節(jié)點(diǎn)即nk，k＞N，取代根節(jié)點(diǎn)root，而獲得等價(jià)路徑｛ni0，ni1，…，nim，nk｝，使（nim，nk）∈E，ω（nim，nk）＝ω1（nim，root），從而獲得?ni∈V且i≤N與SN節(jié)點(diǎn)集之間的k條不相交的路徑，即圖G是k點(diǎn)連通SN節(jié)點(diǎn)。圖2表示k＝3時(shí)，圖G與其簡(jiǎn)化圖G1的關(guān)系。
圖2 圖G與其簡(jiǎn)化圖G1間的關(guān)系
如果節(jié)點(diǎn)數(shù)很多時(shí)，基于簡(jiǎn)化圖的k-FTDTC問(wèn)題仍然是NP-難問(wèn)題［19］，很難計(jì)算最優(yōu)解，因此本文基于簡(jiǎn)化圖G1提出一種分布式近似算法來(lái)進(jìn)行求解。
2 容錯(cuò)性分布式拓?fù)淇刂扑惴ㄔO(shè)計(jì)
本文設(shè)計(jì)的k-FTDTC算法用到的參數(shù)定義如下：
flagi∶flagi為1表示節(jié)點(diǎn)ni確定了其最終發(fā)射功率，否則flagi為0；
di：簡(jiǎn)化圖G1中節(jié)點(diǎn)ni當(dāng)前的通信半徑；
P（Dmax）：節(jié)點(diǎn)在最大通信距離下的發(fā)射功率；
F（ni）＿list：節(jié)點(diǎn)以P（Dmax）進(jìn)行通信時(shí)，節(jié)點(diǎn)ni的鄰居列表，包含鄰居節(jié)點(diǎn)ID及節(jié)點(diǎn)間的接收信號(hào)強(qiáng)度，即F（ni）＿list＝｛F（ni）＿list＿ID，F(xiàn)（ni）＿list＿RSS｝；
G1（ni）＝（Vni，Eni）：節(jié)點(diǎn)ni的局部拓?fù)?，其?/p>
F1（ni）：節(jié)點(diǎn)ni在通信半徑為di時(shí)的鄰集，F(xiàn)1（ni）＝｛nj｜dist（ni，nj）≤di｝；
F2（ni）：在圖G1（ni）中與節(jié)點(diǎn)nik點(diǎn)連通且不在其鄰集F1（ni）中的節(jié)點(diǎn)集合，F(xiàn)2（ni）＝｛nj｜di＜dist（ni，nj）≤Dmax，且ni，nj在G1（ni）是k點(diǎn)連通｝；
本文提出的k-FTDTC算法基本思想是：通過(guò)信息交換，建立節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)信息列表，并通過(guò)節(jié)點(diǎn)間的RSS進(jìn)行排序，獲得有序鄰集F（ni）＿list；然后基于有序鄰集F（ni）＿list分別計(jì)算獲得和，由于任意節(jié)點(diǎn)ni若存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則節(jié)點(diǎn)ni的發(fā)射功率最小能到達(dá)其k個(gè)鄰居節(jié)點(diǎn)，因此定義節(jié)點(diǎn)ni的初始發(fā)射功率為；最后根據(jù)有序鄰集，不斷增加節(jié)點(diǎn)ni的發(fā)射功率Pi，使F（ni）＿list＿ID＝F1（ni）∪F2（ni），即F（ni）＿list中的任意節(jié)點(diǎn)nj屬于F1（ni）∪F2（ni）。滿足以上條件的發(fā)射功率Pi即為節(jié)點(diǎn)ni的最終發(fā)射功率，在保證任意節(jié)點(diǎn)k連通到根節(jié)點(diǎn)基礎(chǔ)上，通過(guò)降低節(jié)點(diǎn)的發(fā)射功率，來(lái)優(yōu)化網(wǎng)絡(luò)能量消耗。
k-FTDTC算法具體包括3個(gè)部分：構(gòu)建有序鄰集，Pmini與計(jì)算和k連通構(gòu)建。
2.1 構(gòu)建有序鄰集
網(wǎng)絡(luò)中的所有節(jié)點(diǎn)依次以最大發(fā)射功率廣播Hello消息，消息中包括節(jié)點(diǎn)ID。任意收到Hello的節(jié)點(diǎn)nj回復(fù)Response消息，Response消息中包括接收到的節(jié)點(diǎn)的ID以及其自身的ID。當(dāng)節(jié)點(diǎn)ni接收到包含其自身ID的Response消息時(shí)，判定節(jié)點(diǎn)nj是否已在F（ni）＿list列表中。若不存在，則將節(jié)點(diǎn)nj的ID，以及節(jié)點(diǎn)和nj間的RSS存儲(chǔ)于節(jié)點(diǎn)ni的鄰集F（ni）＿list列表中，否則不做任何處理。最后對(duì)節(jié)點(diǎn)ni的鄰集按照節(jié)點(diǎn)間的RSS非遞增方式進(jìn)行排序，獲得有序鄰集F（ni）＿list。
任意節(jié)點(diǎn)ni若存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則節(jié)點(diǎn)ni的最小發(fā)射功率應(yīng)能到達(dá)其鄰集F（ni）＿list中最近的k個(gè)節(jié)點(diǎn)，因此節(jié)點(diǎn)ni保持k點(diǎn)連通的發(fā)射功率將會(huì)在和之間。CN節(jié)點(diǎn)的最大發(fā)射功率P（Dmax）通常已知，有序鄰集F（ni）＿list列表中存儲(chǔ)了節(jié)點(diǎn)ni接收到其鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度，因此基于有序鄰集F（ni）＿list，可以計(jì)算得到節(jié)點(diǎn)ni的和。計(jì)算公式如下：
式中，F(xiàn)（ni）＿list＿RSS［k］表示節(jié)點(diǎn)ni接收到距其第k遠(yuǎn)鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度；｜F（ni）＿list｜表示列表中節(jié)點(diǎn)的數(shù)目。
2.3 k連通構(gòu)建
k-FTDTC算法中k連通構(gòu)建的基本思想是：任選一個(gè)節(jié)點(diǎn)ni，定義其初始發(fā)射功率為，根據(jù)有序鄰集，在，］逐次增加節(jié)點(diǎn)ni發(fā)射功率，使其鄰居節(jié)點(diǎn)F1（ni）逐個(gè)增加，當(dāng)滿足F（ni）＿list＿ID＝＝F1（ni）∪F2（ni）時(shí)，即獲得ni的最佳發(fā)射功率，并向其鄰居節(jié)點(diǎn)進(jìn)行廣播。
對(duì)于任意節(jié)點(diǎn)ni，基于上述思想進(jìn)行k連通構(gòu)建，確定其最佳發(fā)射功率，最多需要｜F（ni）＿list＿ID｜－k輪。在每一輪中，節(jié)點(diǎn)通過(guò)廣播獲得其一跳范圍內(nèi)節(jié)點(diǎn)的拓?fù)潢P(guān)系，同時(shí)節(jié)點(diǎn)ni利用有序鄰集可自適應(yīng)地獲得其發(fā)射功率Pi每次調(diào)整的增幅Δp，Δp利用式（4）計(jì)算獲得，從而保證每輪中至少有一個(gè)節(jié)點(diǎn)加入到F1（ni）中，提高了k連通構(gòu)建的效率。
其中每一輪后，k的值進(jìn)行自增，因此可知k值自增的次數(shù)與k連通構(gòu)建進(jìn)行的輪次一致。
本文設(shè)計(jì)的k-FTDTC算法的偽代碼如表2所示。
表2 k－FTDTC算法偽代碼
下面通過(guò)定理2對(duì)本文提出的k-FTDTC算法有效性進(jìn)行證明。
定理2 若G1是k點(diǎn)連通root節(jié)點(diǎn)，則通過(guò)k-FTDTC算法對(duì)每個(gè)CN節(jié)點(diǎn)的發(fā)射功率進(jìn)行優(yōu)化分配后，G1仍是k點(diǎn)連通到root節(jié)點(diǎn)。
證明 由于G1是k點(diǎn)連通root節(jié)點(diǎn)，因此對(duì)于G1中任意節(jié)點(diǎn)nv，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)，不失一般性，定義這k條不相交的路徑為：r1，r2，…，rk。若定義任意節(jié)點(diǎn)ni的發(fā)射功率是通過(guò)k-FTDTC算法調(diào)整后獲得的，其有序鄰集為F（ni）＿list，假設(shè)nj是其有序鄰集中的任意節(jié)點(diǎn)，若能證明節(jié)點(diǎn)ni的發(fā)射功率經(jīng)調(diào)整后，被刪除的任意邊（ni，nj）不影響節(jié)點(diǎn)nv與節(jié)點(diǎn)k點(diǎn)連通性，則證明了本文所提出的k-FTDTC算法的有效性。
為了證明上述論斷，分以下兩種情況進(jìn)行證明：
（1）被刪除的邊（ni，nj）不屬于r1，r2，…，rk中的任何一條路徑：由于邊（ni，nj）的刪除并不影響路徑r1，r2，…，rk，因此節(jié)點(diǎn)nv與root節(jié)點(diǎn)仍然k點(diǎn)連通性。
（2）被刪除的邊（ni，nj）屬于r1，r2，…，rk中某一條路徑：不失一般性，假設(shè)被刪除的邊（ni，nj）屬于路徑rk，下面證明若k－1個(gè)節(jié)點(diǎn)被刪除后，nv與root節(jié)點(diǎn)間仍存在可達(dá)路徑。如果k－1個(gè)節(jié)點(diǎn)不是同時(shí)分別屬于路徑r1，r2，…，rk－1，則在r1，r2，…，rk－1路徑中至少存在一條路徑使nv與root節(jié)點(diǎn)可達(dá)，因此重點(diǎn)是證明被刪除的k－1個(gè)節(jié)點(diǎn)分別屬于路徑r1，r2，…，rk－1時(shí)，nv與root節(jié)點(diǎn)仍存一條路徑可達(dá)。由于被刪除的k－1個(gè)節(jié)點(diǎn)分別屬于路徑r1，r2，…，rk－1，則通過(guò)路徑rk節(jié)點(diǎn)nv與節(jié)點(diǎn)ni仍然相通，定義節(jié)點(diǎn)nv與ni之間路徑為r1k；同時(shí)節(jié)點(diǎn)nj與root節(jié)點(diǎn)也是相通的，定義節(jié)點(diǎn)nj與root之間路徑為；根據(jù)k-FTDTC算法，節(jié)點(diǎn)ni與nj是k連通的，即存在k路徑相通，因此即使刪除的k－1個(gè)節(jié)點(diǎn)屬于該k條相通路徑，但節(jié)點(diǎn)ni與nj仍存在至少一條路徑連通，假設(shè)為。路徑、、構(gòu)成了節(jié)點(diǎn)nv與root間的一條連通路徑，即rk＝＋＋。根據(jù)k點(diǎn)相通定義，節(jié)點(diǎn)nv與root節(jié)點(diǎn)為k點(diǎn)連通。
上述證明從理論上保證了每個(gè)CN節(jié)點(diǎn)利用k-FTDTC算法進(jìn)行發(fā)射功率優(yōu)化分配后，G1仍是k點(diǎn)連通到root節(jié)點(diǎn)。
3 仿真分析
采用MATLAB對(duì)算法進(jìn)行仿真，并與經(jīng)典的分布式拓?fù)淇刂扑惴―ATC進(jìn)行比較，以驗(yàn)證k-FTDTC算法的性能。DATC算法是分布式拓?fù)淇刂扑惴ǎ摲椒ㄔ诿總€(gè)節(jié)點(diǎn)位置已知的前提下，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，對(duì)節(jié)點(diǎn)發(fā)射功率進(jìn)行調(diào)整以保證網(wǎng)絡(luò)是k點(diǎn)連通的。由于DATC算法是通過(guò)構(gòu)造有向圖進(jìn)行拓?fù)淇刂?，因此算法相?duì)復(fù)雜；其次該方法要求所有節(jié)點(diǎn)知道自身位置信息，適用性受限；最后該方法并沒(méi)有對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此存在網(wǎng)絡(luò)能量均衡問(wèn)題。
本文主要采用3項(xiàng)性能指標(biāo)對(duì)上述兩種算法進(jìn)行評(píng)價(jià)：①網(wǎng)絡(luò)總功耗，即網(wǎng)絡(luò)中每個(gè)CN節(jié)點(diǎn)發(fā)射功率之和；②最大發(fā)射功率，即經(jīng)過(guò)拓?fù)淇刂坪?，所有?jié)點(diǎn)中最大的發(fā)射功率，主要用來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)間能量均衡和網(wǎng)絡(luò)生命周期；③計(jì)算復(fù)雜度：HWSN進(jìn)行拓?fù)淇刂?，?jié)點(diǎn)功率優(yōu)化過(guò)程中，算法執(zhí)行基本運(yùn)算的數(shù)量。
3.1 仿真場(chǎng)景和參數(shù)設(shè)置
N節(jié)點(diǎn)隨機(jī)部署在500m×500m的方形平面區(qū)域內(nèi)，SN節(jié)點(diǎn)在預(yù)先設(shè)置的位置上部署，相鄰節(jié)點(diǎn)間的通信滿足式（1）定義的無(wú)線信道模型，算法仿真重復(fù)次數(shù)為100。具體的參數(shù)定義如表3所示。
表3 實(shí)驗(yàn)仿真參數(shù)
3.2 性能比較與分析
圖3為依次改變網(wǎng)絡(luò)中CN節(jié)點(diǎn)總數(shù)，當(dāng)網(wǎng)絡(luò)容錯(cuò)度k分別為2和4時(shí)，DATC算法和本文設(shè)計(jì)的k-FTDTC算法的網(wǎng)絡(luò)總功耗比較。可以發(fā)現(xiàn)k-FTDTC算法的網(wǎng)絡(luò)總功耗明顯小于經(jīng)典的DATC算法，這是因?yàn)閗-FTDTC算法不僅以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，還基于節(jié)點(diǎn)的有序鄰集對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此節(jié)點(diǎn)功率優(yōu)化效果更好。當(dāng)網(wǎng)絡(luò)容錯(cuò)度k從2增加到4時(shí)，整個(gè)網(wǎng)絡(luò)總功耗也在增加，可見(jiàn)網(wǎng)絡(luò)容錯(cuò)度的提高是以犧牲一定的網(wǎng)絡(luò)能量為代價(jià)的。然而當(dāng)網(wǎng)絡(luò)容錯(cuò)度為4時(shí)，增加傳感器節(jié)點(diǎn)數(shù)目，網(wǎng)絡(luò)總功耗反而少量降低，這是因?yàn)槿蒎e(cuò)度的提高意味著節(jié)點(diǎn)間鏈路的增加，對(duì)于鏈路密集的網(wǎng)絡(luò)，雖然傳感器節(jié)點(diǎn)數(shù)目的增加增大了網(wǎng)絡(luò)總功耗，但是由于節(jié)點(diǎn)間距離的縮短也降低了節(jié)點(diǎn)的發(fā)射功率。
圖3 網(wǎng)絡(luò)總功耗比較
圖4為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的最大發(fā)射功率比較?？梢园l(fā)現(xiàn)基于節(jié)點(diǎn)有序鄰集的k-FTDTC算法能夠有效降低節(jié)點(diǎn)的最大發(fā)射功率，使節(jié)點(diǎn)間能量消耗更加均衡。并且，隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目的不斷增加，k-FTDTC算法對(duì)最大發(fā)射功率優(yōu)化更為顯著，能夠有效延長(zhǎng)大規(guī)模HWSN的網(wǎng)絡(luò)生命周期。
圖4 最大發(fā)射功率比較
圖5為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的計(jì)算復(fù)雜度比較?？梢园l(fā)現(xiàn)，不同傳感器節(jié)點(diǎn)規(guī)模與不同容錯(cuò)度下，k-FTDTC算法的計(jì)算復(fù)雜度明顯低于DATC算法。這是因?yàn)镈ATC算法是通過(guò)構(gòu)造有向圖進(jìn)行拓?fù)淇刂?，而本文設(shè)計(jì)的k-FTDTC算法是基于無(wú)向簡(jiǎn)化圖，有效降低了算法的復(fù)雜度，使k-FTDTC算法更適合在計(jì)算能力受限的CN節(jié)點(diǎn)上運(yùn)行。
圖5 計(jì)算復(fù)雜度比較
5 結(jié) 論
在WSN中，除普通的CN節(jié)點(diǎn)外，通過(guò)有計(jì)劃地部署少量能量豐富、通信能力強(qiáng)的SN節(jié)點(diǎn)，組成轉(zhuǎn)發(fā)骨干網(wǎng)，可以有效增強(qiáng)網(wǎng)絡(luò)連通性、降低數(shù)據(jù)轉(zhuǎn)發(fā)延遲、提高網(wǎng)絡(luò)可擴(kuò)展性?；谏鲜霎悩?gòu)無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)性拓?fù)淇刂剖且活怤P-難問(wèn)題，本文基于構(gòu)建的HWSN網(wǎng)絡(luò)模型提出了簡(jiǎn)化網(wǎng)絡(luò)圖構(gòu)建方法，將NP-難問(wèn)題進(jìn)行簡(jiǎn)化，進(jìn)行形式化描述。然后，通過(guò)構(gòu)造節(jié)點(diǎn)的有序鄰集來(lái)約束其發(fā)射功率，在保證網(wǎng)絡(luò)k容錯(cuò)性的基礎(chǔ)上最小化網(wǎng)絡(luò)總功耗，提出了一個(gè)k容錯(cuò)性分布式拓?fù)淇刂扑惴ā?shí)驗(yàn)結(jié)果表明，本文所提k-FTDTC算法，相比經(jīng)典的DATC算法，網(wǎng)絡(luò)總功耗、節(jié)點(diǎn)的最大發(fā)射功率以及算法計(jì)算復(fù)雜度明顯降低，從而驗(yàn)證了算法的有效性。
［1］Guidoni D L，Mini R A F，Loureiro A A F.On the design of resilient heterogeneous wireless sensor networks based on small world concepts［J］.Computer Networks，2010，54（8）：1266－1281.
［2］Yin R R，Liu B，Li Y Q，et al.Research on the fault-tolerant topology in energy heterogeneous wireless sensor networks［J］.Journal of Electronics ＆Information Technology，2012，34（9）：2180－2186.（尹榮榮，劉彬，李雅倩，等.能量異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)拓?fù)溲芯浚跩］.電子與信息學(xué)報(bào)，2012，34（9）：2180－2186.）
［3］Hajiaghayi M，Nicole I，Vahab S M.Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks［J］.IEEE Trans.on Networking，2007，15（6）：1345－1358.
［4］Rajiv M，Chittaranjan M.Rotation of CDS via connected domatic partition in Ad Hoc sensor networks［J］.IEEE Trans.on Mobile Computing，2009，8（4）：488－499.
［5］Zhao Y X，Wu J，Li F，et al.VBS：maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones［C］∥Proc.of the IEEE INFOCOM，2010：71－75.
［6］Qi X Q，Ma S，Zheng G Z.Topology evolution of wireless sensor networks based on adaptive free-scale networks［J］.Journal of Information and Computational Science，2011，8（3）：467－475.
［7］Rossi K，Choong S H.Fault tolerant virtual backbone for minimum temperature in vivo sensor network［C］∥Proc.of the IEEE International Conference on Communications，2012：3394－3398.
［8］Renato E N，Celso C R，Christophe D.Optimal solutions for fault-tolerant topology control in wireless Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2009，8（12）：5970－5981.
［9］Calinescu G，Wan P J.Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks［J］.Mobile Network Applications，2006，11（2）：121－128.
［10］Dai F，Wu J.On constructing k-connected k-dominating set in wireless Ad Hoc and sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，66（7）：947－958.
［11］Cohen R，Kapchits B.An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor networks［J］.IEEE Trans.on Networks，2009，17（2）：570－581.
［12］Li N，Hou J C.Localized fault-tolerant topology control in wireless ad hoc networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，17（4）：307－320.
［13］Thai M，Zhang N，Tiwari R.On approximation algorithms of k-connected m-dominating set in disk graphs［J］.Theoretical Computer Science，2007，35（8）：49－59.
［14］Cardei M，Yang S H，Wu J.Algorithms for fault-tolerant topology in heterogeneous wireless sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2008，19（4）：545－558.
［15］Gui J S，Liu A F.A new distributed topology control algorithmbased on optimization of delay and energy in wireless networks［J］.Journal of Parallel and Distributed Computing，2012，72（8）：1032－1044.
［16］Luo X J，Yu H Q，Wang X.Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks［J］.International Journal of Systems Science，2013，44（10）：864－877.
［17］Xu Y J，Qi H C.A fault-tolerant topology control algorithm for heterogeneous wireless networks［C］∥Proc.of the International Conference on Computer Science ＆Education，2012：1106－1109.
［18］Andrew Y W.Lower power RF transceiver modeling and design for wireless microsensor networks［D］.Massachusetts：Massachusetts Institute of Technology，2005.
［19］Nishiyama H，Ngo T，Ansari N，et al.On minimizing the impact of mobility on topology control in mobile Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2012，11（3）：1158－1166.
Algorithm for fault-tolerant topology control in heterogeneous and multi-hop wireless sensor networks
LIU Xing-chuan，WU Zhen-feng，ZHAO Ke-jian
（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing 210007，China）
Heterogeneous wireless sensor networks（HWSN）is a more practical network model because of an improved network performance such as a shorter data-gathering delay and lower network energy consumption.The kfault-tolerant topology control is a kind of NP-hard problem in the HWSN.The paper designs an approach of constructing network reduced graphs based on comprehensive analysis on the network model of HWSN.And the k-fault-tolerant distributed topology control（k-FTDTC）algorithm is proposed based on the ordered reachable neighborhood which is used to restrict the maximum transmission power of the nodes，with the objective of minimizing the total power consumption and preserving k-vertex fault-tolerant property.The experimental results indicate that the k-FTDTC algorithm not only reduces the computational complexity and improves network robustness，but also reduces the total network power consumption and the maximum node power consumption，as compared with the distributed adaptive topology control（DATC）algorithm.
heterogeneous wireless sensor networks（HWST）；topology control；ordered reachable neighborhood；fault-tolerant
TP 393
A
10.3969／j.issn.1001-506X.2015.08.28
劉興川（1982－），男，工程師，博士，主要研究方向?yàn)閃SN容錯(cuò)性拓?fù)淇刂啤⒐?jié)點(diǎn)定位、數(shù)據(jù)融合。
E-mail：liuxch06＠163.com
吳振鋒（1975－），男，研究員，博士，主要研究方向?yàn)閭鞲芯W(wǎng)集成應(yīng)用技術(shù)。
E-mail：wuzhenf＠163.com
趙克儉（1964－），男，研究員，主要研究方向?yàn)閭鞲芯W(wǎng)／物聯(lián)網(wǎng)應(yīng)用技術(shù)。
E-mail：zhaokej＠163.com
1001－506X201508－1902－07
網(wǎng)址：www.sys－ele.com
2014－09－09；
2014－10－30；網(wǎng)絡(luò)優(yōu)先出版日期：2014－11－21。
網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20141121.0956.012.html
江蘇省青年科學(xué)基金（SBK2014042581）資助課題
猜你喜歡
無(wú)線電波發(fā)射功率防爆要求與檢測(cè)方法工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00 基于視覺(jué)補(bǔ)充的水稻插秧機(jī)多傳感器組合定位研究華中農(nóng)業(yè)大學(xué)學(xué)報(bào)(2024年2期)2024-01-01 00:00:00 試論同課異構(gòu)之“同”與“異”小學(xué)教學(xué)研究(2022年5期)2022-04-28 21:29:36 放大轉(zhuǎn)發(fā)中繼器降低發(fā)射功率的選擇策略研究無(wú)線互聯(lián)科技(2017年24期)2018-01-22 10:39:24 淺談AC在WLAN系統(tǒng)中的應(yīng)用中國(guó)管理信息化(2017年18期)2018-01-04 18:41:52 基于功率分配最優(yōu)中繼選擇的研究物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11 overlay SDN實(shí)現(xiàn)異構(gòu)兼容的關(guān)鍵技術(shù)電信科學(xué)(2016年11期)2016-11-23 05:07:56 LTE異構(gòu)網(wǎng)技術(shù)與組網(wǎng)研究通信電源技術(shù)(2016年6期)2016-04-20 06:21:36 基于認(rèn)知心理學(xué)的交互式產(chǎn)品的容錯(cuò)性設(shè)計(jì)研究工業(yè)設(shè)計(jì)(2016年8期)2016-04-16 02:43:26 基于免疫算法的高容錯(cuò)性廣域保護(hù)研究電測(cè)與儀表(2015年2期)2015-04-09 11:28:56
劉興川，吳振鋒，趙克儉
（中國(guó)電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)多跳無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/p>
劉興川，吳振鋒，趙克儉
（中國(guó)電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)（heterogeneous wireless sensor works，HWSN）能有效降低數(shù)據(jù)轉(zhuǎn)發(fā)延遲、網(wǎng)絡(luò)能量消耗，是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，基于HWSN的k容錯(cuò)性拓?fù)淇刂剖且活怤P-難問(wèn)題。在綜合分析HWSN網(wǎng)絡(luò)模型的基礎(chǔ)上，本文設(shè)計(jì)了簡(jiǎn)化網(wǎng)絡(luò)圖構(gòu)建方法，通過(guò)構(gòu)造有序鄰集來(lái)約束節(jié)點(diǎn)的最大發(fā)射功率，以網(wǎng)絡(luò)總功耗與容錯(cuò)性雙優(yōu)化為目標(biāo)，實(shí)現(xiàn)了一個(gè)k容錯(cuò)性分布式拓?fù)淇刂扑惴ǎ╧-fault-tolerant distributed topology control，k-FTDTC）。實(shí)驗(yàn)結(jié)果表明，相比分布式拓?fù)淇刂疲╠istributed adaptive topology control，DATC）方法，k-FTDTC算法有效降低了網(wǎng)絡(luò)總功耗和最大發(fā)射功率，且具有較好的容錯(cuò)性和較低算法復(fù)雜度。
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；有序鄰集；容錯(cuò)性
0 引 言
異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)（heterogeneous wireless sensor networks，HWSN）是指由多種不同類型的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，傳感器節(jié)點(diǎn)的異構(gòu)性主要表現(xiàn)在：計(jì)算能力異構(gòu)、通信能力異構(gòu)以及節(jié)點(diǎn)能量異構(gòu)［1－2］。無(wú)線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）早期的拓?fù)淇刂蒲芯恐饕性谕瑯?gòu)WSN，即網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有相同的軟硬件能力，被隨機(jī)部署在監(jiān)測(cè)區(qū)域，地位平等，開(kāi)展能量最優(yōu)化研究［3－5］。然而在實(shí)際環(huán)境中，傳感器節(jié)點(diǎn)通常承擔(dān)不同的角色功能，甚至具有不同的資源配置以適應(yīng)多樣化的應(yīng)用需求。此外，即使是同構(gòu)的WSN，由于節(jié)點(diǎn)感知任務(wù)的不同所造成的能耗不同，也促使初始能量相同的網(wǎng)絡(luò)逐漸演變成多級(jí)能量異構(gòu)網(wǎng)絡(luò)。可見(jiàn)，HWSN是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，最近的研究成果［6－8］也表明，相比同構(gòu)網(wǎng)絡(luò)架構(gòu)，HWSN有效降低了監(jiān)測(cè)數(shù)據(jù)轉(zhuǎn)發(fā)延遲、網(wǎng)絡(luò)能量消耗，具有更優(yōu)的網(wǎng)絡(luò)性能。
本文研究的HWSN是由兩類傳感器節(jié)點(diǎn)組成：一類是資源受限隨機(jī)部署的傳感器節(jié)點(diǎn)，稱為普通節(jié)點(diǎn)（common node，CN），用于感知監(jiān)測(cè)異常事件；一類是高能力定點(diǎn)部署的超級(jí)節(jié)點(diǎn)（super node，SN），組成骨干網(wǎng)絡(luò)，完成數(shù)據(jù)融合和快速轉(zhuǎn)發(fā)等任務(wù)，如圖1所示。CN節(jié)點(diǎn)通過(guò)多跳方式與SN節(jié)點(diǎn)進(jìn)行通信，由于復(fù)雜惡劣環(huán)境的影響，經(jīng)常導(dǎo)致CN節(jié)點(diǎn)間通信鏈路失效，再加上CN節(jié)點(diǎn)能量受限，如何在保證網(wǎng)絡(luò)具有容錯(cuò)性的基礎(chǔ)上最優(yōu)化網(wǎng)絡(luò)能量消耗成為HWSN拓?fù)淇刂曝叫杞鉀Q的一個(gè)難題。
圖1 異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)模型
針對(duì)上述問(wèn)題，文獻(xiàn)［9－11］利用同構(gòu)網(wǎng)絡(luò)中已有的研究成果，提出了通過(guò)構(gòu)造網(wǎng)絡(luò)的k點(diǎn)連通圖建立容錯(cuò)性拓?fù)洌淳W(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間都至少存在k條不相交的路徑，當(dāng)任意k－1個(gè)節(jié)點(diǎn)或鏈路發(fā)生故障時(shí)，網(wǎng)絡(luò)仍然保持連通，該方法可有效提高網(wǎng)絡(luò)容錯(cuò)性，但是由于任意節(jié)點(diǎn)都要保持k條不相交的路徑，因此導(dǎo)致整個(gè)網(wǎng)絡(luò)能耗隨其容錯(cuò)能力的提升成倍增加。文獻(xiàn)［12－13］證明了k點(diǎn)連通圖構(gòu)建是一個(gè)NP-難問(wèn)題，需要對(duì)該問(wèn)題進(jìn)行簡(jiǎn)化，求其次優(yōu)解，同時(shí)分別提出了兩種集中式近似求解算法，但是對(duì)于節(jié)點(diǎn)數(shù)據(jù)眾多的WSN而言，集中式拓?fù)淇刂扑惴ú⒉焕诰W(wǎng)絡(luò)規(guī)模的擴(kuò)展。隨后，文獻(xiàn)［14－15］針對(duì)HWSN容錯(cuò)性拓?fù)淇刂?，基于?jié)點(diǎn)剩余能量，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，提出k點(diǎn)連通圖的分布式近似求解算法。但是在多跳網(wǎng)絡(luò)中節(jié)點(diǎn)剩余能量多少并不能準(zhǔn)確反映節(jié)點(diǎn)剩余生命周期的長(zhǎng)短，需要綜合考慮節(jié)點(diǎn)的剩余能量和能量消耗速度，同時(shí)這些方法也沒(méi)有對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行控制，因此導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗不均衡。
綜上所述，文獻(xiàn)［9－15］研究的問(wèn)題與本文相似，目標(biāo)都是在保證網(wǎng)絡(luò)具有k容錯(cuò)性的基礎(chǔ)上，最小化網(wǎng)絡(luò)總功耗。本文與上述工作的不同之處主要體現(xiàn)在：①在HWSN中，感知數(shù)據(jù)從CN節(jié)點(diǎn)發(fā)送到SN節(jié)點(diǎn)，因此在任意兩個(gè)節(jié)點(diǎn)之間都保持k條不相交的路徑是沒(méi)有必要的，重要的是使每一個(gè)CN節(jié)點(diǎn)存在k條不相交的路徑可達(dá)SN節(jié)點(diǎn)?；谏鲜鏊枷?，本文設(shè)計(jì)的目標(biāo)函數(shù)是保證任意CN節(jié)點(diǎn)與SN節(jié)點(diǎn)集都存在k條不相交的路徑，在此基礎(chǔ)上最小化網(wǎng)絡(luò)總功耗。②綜合分析異構(gòu)多跳WSN的特點(diǎn)，設(shè)計(jì)簡(jiǎn)化圖方法來(lái)對(duì)HWSN網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，以降低算法求解復(fù)雜度；通過(guò)構(gòu)造CN節(jié)點(diǎn)的有序鄰集來(lái)控制節(jié)點(diǎn)的最大發(fā)射功率，以最小化網(wǎng)絡(luò)總功耗與能量均衡雙優(yōu)化為目標(biāo)，實(shí)現(xiàn)k容錯(cuò)性分布式拓?fù)淇刂疲╧-fault-tolerant distributed topology control，k-FTDTC）算法，提高網(wǎng)絡(luò)健壯性。③基于仿真實(shí)驗(yàn)，對(duì)本文提出的k-FTDTC算法性能進(jìn)行了詳實(shí)的評(píng)估，同時(shí)與經(jīng)典的分布式拓?fù)淇刂疲╠istributed adaptive topology control，DATC）算法［15］進(jìn)行性能比較，以驗(yàn)證本文算法的有效性。
1 網(wǎng)絡(luò)模型與問(wèn)題描述
式中，Pr表示接收功率；λ為電磁波長(zhǎng)；d0為參考距離，一般為1m，d是發(fā)射天線與接收天線之間的距離；n是路徑損耗系數(shù)；G1，G2分別是發(fā)射天線增益和接收天線增益。
根據(jù)上述假設(shè)，CN節(jié)點(diǎn)和SN節(jié)點(diǎn)共同構(gòu)成一個(gè)連通的網(wǎng)絡(luò)，可抽象為一個(gè)無(wú)向加權(quán)網(wǎng)絡(luò)圖G＝（V，E，ω），其中點(diǎn)集V包含N個(gè)CN節(jié)點(diǎn)和M個(gè)SN節(jié)點(diǎn)，即V＝｛n1，n2，…，nN＋1，…，nN＋M｝，前N個(gè)為CN節(jié)點(diǎn)，后M個(gè)為SN節(jié)點(diǎn)。E為邊集，定義為E＝｛（ni，nj）｜dist（ni，nj）≤Dmax｝，其中dist（·）為歐式距離函數(shù)。ω為對(duì)應(yīng)E中每條邊的權(quán)值集合。下面給出用到的幾個(gè)定義：
定義1 邊的權(quán)重：用ω（ni，nj）表示，定義為節(jié)點(diǎn)ni與nj間通信所需的最小發(fā)射功率，具體值可以通過(guò)式（1）計(jì)算。
定義2 可達(dá)鄰集：用F（ni）表示，定義為節(jié)點(diǎn)ni以最大傳輸距離Dmax進(jìn)行通信，所能到達(dá)的節(jié)點(diǎn)集合，即F（ni）＝｛nj｜nj∈V，（ni，nj）∈E｝。
定義3 節(jié)點(diǎn)的功率：用P（ni）表示，定義為P（ni）＝
1.1 網(wǎng)絡(luò)模型
本文討論的HWSN網(wǎng)絡(luò)模型如圖1所示，包括N個(gè)CN節(jié)點(diǎn)和M個(gè)SN節(jié)點(diǎn)，其中M?N。其中，CN節(jié)點(diǎn)隨機(jī)分布，能量受限，具有短的通信能力和低的數(shù)據(jù)速率，主要任務(wù)是實(shí)時(shí)感知監(jiān)測(cè)目標(biāo)的信息，周期性地將感知數(shù)據(jù)通過(guò)多跳方式傳送給附近的SN節(jié)點(diǎn)，其主要的能耗來(lái)自于數(shù)據(jù)的無(wú)線收發(fā)。相比CN節(jié)點(diǎn)，SN節(jié)點(diǎn)具有更多能量、更強(qiáng)的計(jì)算存儲(chǔ)能力、更長(zhǎng)的通信距離和更高的數(shù)據(jù)速率，SN節(jié)點(diǎn)間形成骨干網(wǎng)絡(luò)，主要負(fù)責(zé)對(duì)CN節(jié)點(diǎn)的感知數(shù)據(jù)進(jìn)行融合處理、判決計(jì)算，實(shí)時(shí)可靠地將結(jié)果轉(zhuǎn)發(fā)給監(jiān)測(cè)中心。SN節(jié)點(diǎn)的應(yīng)用不僅延長(zhǎng)了整個(gè)網(wǎng)絡(luò)生命周期，還降低了端到端的數(shù)據(jù)傳輸延遲，因此，該結(jié)構(gòu)在實(shí)際中被廣泛研究和應(yīng)用［16－17］。上述模型滿足以下假設(shè)條件：
（1）CN節(jié)點(diǎn)隨機(jī)密集部署，具有相同的軟硬件，初始能量相同且為Einit，通信距離可調(diào)節(jié)，最大通信距離為Dmax；
（2）SN節(jié)點(diǎn)為高能力節(jié)點(diǎn)，定點(diǎn)部署，初始能量定義為Einit（1＋K），其中K表示SN節(jié)點(diǎn)能量是CN節(jié)點(diǎn)能量的倍數(shù)；
（3）CN節(jié)點(diǎn)間、CN節(jié)點(diǎn)與SN節(jié)點(diǎn)間的通信鏈路是本文拓?fù)淇刂蒲芯康闹攸c(diǎn)，而由于SN節(jié)點(diǎn)為定點(diǎn)部署且為高能力節(jié)點(diǎn)，本文認(rèn)為SN節(jié)點(diǎn)間通信鏈路是固定可靠的，不屬于本文拓?fù)淇刂脐P(guān)注的重點(diǎn)。
（4）CN節(jié)點(diǎn)與SN節(jié)點(diǎn)分布在二維平面上，形成一個(gè)靜態(tài)連通性網(wǎng)絡(luò)，鏈路具有對(duì)稱性，每個(gè)節(jié)點(diǎn)具有唯一ID，節(jié)點(diǎn)間通信滿足文獻(xiàn)［18］提出的無(wú)線信道模型，即max｛nj｜（ni，nj）∈E｝ω（ni，nj）。
定義4 網(wǎng)絡(luò)圖G總的功耗：用P（G）表示，為圖G中各節(jié)點(diǎn)功率之和，即
定義5 k點(diǎn)連通SN節(jié)點(diǎn)集：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)SN節(jié)點(diǎn)集，即任意k－1個(gè)CN節(jié)點(diǎn)或鏈路出現(xiàn)故障時(shí)，網(wǎng)絡(luò)仍保持連通，即CN節(jié)點(diǎn)的感知數(shù)據(jù)能通過(guò)SN節(jié)點(diǎn)傳送到監(jiān)控中心。
1.2 問(wèn)題描述及簡(jiǎn)化
基于上述異構(gòu)多跳網(wǎng)絡(luò)模型，k-FTDTC算法的目標(biāo)是：①通過(guò)調(diào)節(jié)CN節(jié)點(diǎn)的功率，使每個(gè)CN節(jié)點(diǎn)與SN節(jié)點(diǎn)集間存在k條不相交的路徑；②優(yōu)化CN節(jié)點(diǎn)的最大發(fā)射功率，并使所有CN節(jié)點(diǎn)功耗之和最小，即
結(jié)合k-FTDTC問(wèn)題描述，本文將網(wǎng)絡(luò)圖G＝（V，E，ω）進(jìn)行簡(jiǎn)化求解，簡(jiǎn)化規(guī)則如下：
（1）用一個(gè)根節(jié)點(diǎn)取代M個(gè)SN節(jié)點(diǎn)，形成的新點(diǎn)集為V1＝｛n1，n2，…，nN，root｝，這是因?yàn)檠芯勘砻鱏N節(jié)點(diǎn)間的通信鏈路是可靠的［17］。
（2）節(jié)點(diǎn)之間的邊保持不變，若同一個(gè)CN節(jié)點(diǎn)與兩個(gè)或兩個(gè)以上的SN節(jié)點(diǎn)相連，則僅保留邊權(quán)值最小的那條邊。這是因?yàn)閗-FTDTC的目標(biāo)是使CN節(jié)點(diǎn)與SN連通并最小化CN節(jié)點(diǎn)發(fā)射功率。
（3）邊的權(quán)重保持不變。
利用上述規(guī)則設(shè)計(jì)算法1將網(wǎng)絡(luò)圖G＝（V，E，ω）轉(zhuǎn)化為簡(jiǎn)化圖G1＝（V1，E1，ω1），簡(jiǎn)化圖偽代碼如表1所示。
表1 簡(jiǎn)化圖G1構(gòu)建算法偽代碼
定義6 簡(jiǎn)化圖k點(diǎn)連通root節(jié)點(diǎn)：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則稱簡(jiǎn)化圖k點(diǎn)連通root節(jié)點(diǎn)。
根據(jù)定義7可以獲得定理1。
定理1 異構(gòu)多跳WSN是k點(diǎn)連通SN節(jié)點(diǎn)當(dāng)且僅當(dāng)對(duì)應(yīng)的簡(jiǎn)化圖是k點(diǎn)連通root節(jié)點(diǎn)。
證明 （1）必要性。由于異構(gòu)多跳WSN是k點(diǎn)連通SN節(jié)點(diǎn)，即?ni∈V且i≤N的節(jié)點(diǎn)，都存在k條不相交的路徑到達(dá)SN節(jié)點(diǎn)集。用根節(jié)點(diǎn)root取代每條路徑上的SN節(jié)點(diǎn)，即獲得任意CN節(jié)點(diǎn)即?ni∈V且i≤N與根節(jié)點(diǎn)root之間的k條不相交的路徑，即簡(jiǎn)化圖G1是k點(diǎn)連通root節(jié)點(diǎn)。
（2）充分性。如果簡(jiǎn)化圖G1是k點(diǎn)連通root節(jié)點(diǎn)，則表明對(duì)于任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)。因此，對(duì)于圖G1中到根節(jié)點(diǎn)的任意路徑｛ni0，ni1，…，nim，root｝，都可以通過(guò)用一個(gè)SN節(jié)點(diǎn)即nk，k＞N，取代根節(jié)點(diǎn)root，而獲得等價(jià)路徑｛ni0，ni1，…，nim，nk｝，使（nim，nk）∈E，ω（nim，nk）＝ω1（nim，root），從而獲得?ni∈V且i≤N與SN節(jié)點(diǎn)集之間的k條不相交的路徑，即圖G是k點(diǎn)連通SN節(jié)點(diǎn)。圖2表示k＝3時(shí)，圖G與其簡(jiǎn)化圖G1的關(guān)系。
圖2 圖G與其簡(jiǎn)化圖G1間的關(guān)系
如果節(jié)點(diǎn)數(shù)很多時(shí)，基于簡(jiǎn)化圖的k-FTDTC問(wèn)題仍然是NP-難問(wèn)題［19］，很難計(jì)算最優(yōu)解，因此本文基于簡(jiǎn)化圖G1提出一種分布式近似算法來(lái)進(jìn)行求解。
2 容錯(cuò)性分布式拓?fù)淇刂扑惴ㄔO(shè)計(jì)
本文設(shè)計(jì)的k-FTDTC算法用到的參數(shù)定義如下：
flagi∶flagi為1表示節(jié)點(diǎn)ni確定了其最終發(fā)射功率，否則flagi為0；
di：簡(jiǎn)化圖G1中節(jié)點(diǎn)ni當(dāng)前的通信半徑；
P（Dmax）：節(jié)點(diǎn)在最大通信距離下的發(fā)射功率；
F（ni）＿list：節(jié)點(diǎn)以P（Dmax）進(jìn)行通信時(shí)，節(jié)點(diǎn)ni的鄰居列表，包含鄰居節(jié)點(diǎn)ID及節(jié)點(diǎn)間的接收信號(hào)強(qiáng)度，即F（ni）＿list＝｛F（ni）＿list＿ID，F(xiàn)（ni）＿list＿RSS｝；
G1（ni）＝（Vni，Eni）：節(jié)點(diǎn)ni的局部拓?fù)?，其?/p>
F1（ni）：節(jié)點(diǎn)ni在通信半徑為di時(shí)的鄰集，F(xiàn)1（ni）＝｛nj｜dist（ni，nj）≤di｝；
F2（ni）：在圖G1（ni）中與節(jié)點(diǎn)nik點(diǎn)連通且不在其鄰集F1（ni）中的節(jié)點(diǎn)集合，F(xiàn)2（ni）＝｛nj｜di＜dist（ni，nj）≤Dmax，且ni，nj在G1（ni）是k點(diǎn)連通｝；
本文提出的k-FTDTC算法基本思想是：通過(guò)信息交換，建立節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)信息列表，并通過(guò)節(jié)點(diǎn)間的RSS進(jìn)行排序，獲得有序鄰集F（ni）＿list；然后基于有序鄰集F（ni）＿list分別計(jì)算獲得和，由于任意節(jié)點(diǎn)ni若存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則節(jié)點(diǎn)ni的發(fā)射功率最小能到達(dá)其k個(gè)鄰居節(jié)點(diǎn)，因此定義節(jié)點(diǎn)ni的初始發(fā)射功率為；最后根據(jù)有序鄰集，不斷增加節(jié)點(diǎn)ni的發(fā)射功率Pi，使F（ni）＿list＿ID＝F1（ni）∪F2（ni），即F（ni）＿list中的任意節(jié)點(diǎn)nj屬于F1（ni）∪F2（ni）。滿足以上條件的發(fā)射功率Pi即為節(jié)點(diǎn)ni的最終發(fā)射功率，在保證任意節(jié)點(diǎn)k連通到根節(jié)點(diǎn)基礎(chǔ)上，通過(guò)降低節(jié)點(diǎn)的發(fā)射功率，來(lái)優(yōu)化網(wǎng)絡(luò)能量消耗。
k-FTDTC算法具體包括3個(gè)部分：構(gòu)建有序鄰集，Pmini與計(jì)算和k連通構(gòu)建。
2.1 構(gòu)建有序鄰集
網(wǎng)絡(luò)中的所有節(jié)點(diǎn)依次以最大發(fā)射功率廣播Hello消息，消息中包括節(jié)點(diǎn)ID。任意收到Hello的節(jié)點(diǎn)nj回復(fù)Response消息，Response消息中包括接收到的節(jié)點(diǎn)的ID以及其自身的ID。當(dāng)節(jié)點(diǎn)ni接收到包含其自身ID的Response消息時(shí)，判定節(jié)點(diǎn)nj是否已在F（ni）＿list列表中。若不存在，則將節(jié)點(diǎn)nj的ID，以及節(jié)點(diǎn)和nj間的RSS存儲(chǔ)于節(jié)點(diǎn)ni的鄰集F（ni）＿list列表中，否則不做任何處理。最后對(duì)節(jié)點(diǎn)ni的鄰集按照節(jié)點(diǎn)間的RSS非遞增方式進(jìn)行排序，獲得有序鄰集F（ni）＿list。
任意節(jié)點(diǎn)ni若存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則節(jié)點(diǎn)ni的最小發(fā)射功率應(yīng)能到達(dá)其鄰集F（ni）＿list中最近的k個(gè)節(jié)點(diǎn)，因此節(jié)點(diǎn)ni保持k點(diǎn)連通的發(fā)射功率將會(huì)在和之間。CN節(jié)點(diǎn)的最大發(fā)射功率P（Dmax）通常已知，有序鄰集F（ni）＿list列表中存儲(chǔ)了節(jié)點(diǎn)ni接收到其鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度，因此基于有序鄰集F（ni）＿list，可以計(jì)算得到節(jié)點(diǎn)ni的和。計(jì)算公式如下：
式中，F(xiàn)（ni）＿list＿RSS［k］表示節(jié)點(diǎn)ni接收到距其第k遠(yuǎn)鄰居節(jié)點(diǎn)的信號(hào)強(qiáng)度；｜F（ni）＿list｜表示列表中節(jié)點(diǎn)的數(shù)目。
2.3 k連通構(gòu)建
k-FTDTC算法中k連通構(gòu)建的基本思想是：任選一個(gè)節(jié)點(diǎn)ni，定義其初始發(fā)射功率為，根據(jù)有序鄰集，在，］逐次增加節(jié)點(diǎn)ni發(fā)射功率，使其鄰居節(jié)點(diǎn)F1（ni）逐個(gè)增加，當(dāng)滿足F（ni）＿list＿ID＝＝F1（ni）∪F2（ni）時(shí)，即獲得ni的最佳發(fā)射功率，并向其鄰居節(jié)點(diǎn)進(jìn)行廣播。
對(duì)于任意節(jié)點(diǎn)ni，基于上述思想進(jìn)行k連通構(gòu)建，確定其最佳發(fā)射功率，最多需要｜F（ni）＿list＿ID｜－k輪。在每一輪中，節(jié)點(diǎn)通過(guò)廣播獲得其一跳范圍內(nèi)節(jié)點(diǎn)的拓?fù)潢P(guān)系，同時(shí)節(jié)點(diǎn)ni利用有序鄰集可自適應(yīng)地獲得其發(fā)射功率Pi每次調(diào)整的增幅Δp，Δp利用式（4）計(jì)算獲得，從而保證每輪中至少有一個(gè)節(jié)點(diǎn)加入到F1（ni）中，提高了k連通構(gòu)建的效率。
其中每一輪后，k的值進(jìn)行自增，因此可知k值自增的次數(shù)與k連通構(gòu)建進(jìn)行的輪次一致。
本文設(shè)計(jì)的k-FTDTC算法的偽代碼如表2所示。
表2 k－FTDTC算法偽代碼
下面通過(guò)定理2對(duì)本文提出的k-FTDTC算法有效性進(jìn)行證明。
定理2 若G1是k點(diǎn)連通root節(jié)點(diǎn)，則通過(guò)k-FTDTC算法對(duì)每個(gè)CN節(jié)點(diǎn)的發(fā)射功率進(jìn)行優(yōu)化分配后，G1仍是k點(diǎn)連通到root節(jié)點(diǎn)。
證明 由于G1是k點(diǎn)連通root節(jié)點(diǎn)，因此對(duì)于G1中任意節(jié)點(diǎn)nv，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)，不失一般性，定義這k條不相交的路徑為：r1，r2，…，rk。若定義任意節(jié)點(diǎn)ni的發(fā)射功率是通過(guò)k-FTDTC算法調(diào)整后獲得的，其有序鄰集為F（ni）＿list，假設(shè)nj是其有序鄰集中的任意節(jié)點(diǎn)，若能證明節(jié)點(diǎn)ni的發(fā)射功率經(jīng)調(diào)整后，被刪除的任意邊（ni，nj）不影響節(jié)點(diǎn)nv與節(jié)點(diǎn)k點(diǎn)連通性，則證明了本文所提出的k-FTDTC算法的有效性。
為了證明上述論斷，分以下兩種情況進(jìn)行證明：
（1）被刪除的邊（ni，nj）不屬于r1，r2，…，rk中的任何一條路徑：由于邊（ni，nj）的刪除并不影響路徑r1，r2，…，rk，因此節(jié)點(diǎn)nv與root節(jié)點(diǎn)仍然k點(diǎn)連通性。
（2）被刪除的邊（ni，nj）屬于r1，r2，…，rk中某一條路徑：不失一般性，假設(shè)被刪除的邊（ni，nj）屬于路徑rk，下面證明若k－1個(gè)節(jié)點(diǎn)被刪除后，nv與root節(jié)點(diǎn)間仍存在可達(dá)路徑。如果k－1個(gè)節(jié)點(diǎn)不是同時(shí)分別屬于路徑r1，r2，…，rk－1，則在r1，r2，…，rk－1路徑中至少存在一條路徑使nv與root節(jié)點(diǎn)可達(dá)，因此重點(diǎn)是證明被刪除的k－1個(gè)節(jié)點(diǎn)分別屬于路徑r1，r2，…，rk－1時(shí)，nv與root節(jié)點(diǎn)仍存一條路徑可達(dá)。由于被刪除的k－1個(gè)節(jié)點(diǎn)分別屬于路徑r1，r2，…，rk－1，則通過(guò)路徑rk節(jié)點(diǎn)nv與節(jié)點(diǎn)ni仍然相通，定義節(jié)點(diǎn)nv與ni之間路徑為r1k；同時(shí)節(jié)點(diǎn)nj與root節(jié)點(diǎn)也是相通的，定義節(jié)點(diǎn)nj與root之間路徑為；根據(jù)k-FTDTC算法，節(jié)點(diǎn)ni與nj是k連通的，即存在k路徑相通，因此即使刪除的k－1個(gè)節(jié)點(diǎn)屬于該k條相通路徑，但節(jié)點(diǎn)ni與nj仍存在至少一條路徑連通，假設(shè)為。路徑、、構(gòu)成了節(jié)點(diǎn)nv與root間的一條連通路徑，即rk＝＋＋。根據(jù)k點(diǎn)相通定義，節(jié)點(diǎn)nv與root節(jié)點(diǎn)為k點(diǎn)連通。
上述證明從理論上保證了每個(gè)CN節(jié)點(diǎn)利用k-FTDTC算法進(jìn)行發(fā)射功率優(yōu)化分配后，G1仍是k點(diǎn)連通到root節(jié)點(diǎn)。
3 仿真分析
采用MATLAB對(duì)算法進(jìn)行仿真，并與經(jīng)典的分布式拓?fù)淇刂扑惴―ATC進(jìn)行比較，以驗(yàn)證k-FTDTC算法的性能。DATC算法是分布式拓?fù)淇刂扑惴ǎ摲椒ㄔ诿總€(gè)節(jié)點(diǎn)位置已知的前提下，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，對(duì)節(jié)點(diǎn)發(fā)射功率進(jìn)行調(diào)整以保證網(wǎng)絡(luò)是k點(diǎn)連通的。由于DATC算法是通過(guò)構(gòu)造有向圖進(jìn)行拓?fù)淇刂?，因此算法相?duì)復(fù)雜；其次該方法要求所有節(jié)點(diǎn)知道自身位置信息，適用性受限；最后該方法并沒(méi)有對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此存在網(wǎng)絡(luò)能量均衡問(wèn)題。
本文主要采用3項(xiàng)性能指標(biāo)對(duì)上述兩種算法進(jìn)行評(píng)價(jià)：①網(wǎng)絡(luò)總功耗，即網(wǎng)絡(luò)中每個(gè)CN節(jié)點(diǎn)發(fā)射功率之和；②最大發(fā)射功率，即經(jīng)過(guò)拓?fù)淇刂坪?，所有?jié)點(diǎn)中最大的發(fā)射功率，主要用來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)間能量均衡和網(wǎng)絡(luò)生命周期；③計(jì)算復(fù)雜度：HWSN進(jìn)行拓?fù)淇刂?，?jié)點(diǎn)功率優(yōu)化過(guò)程中，算法執(zhí)行基本運(yùn)算的數(shù)量。
3.1 仿真場(chǎng)景和參數(shù)設(shè)置
N節(jié)點(diǎn)隨機(jī)部署在500m×500m的方形平面區(qū)域內(nèi)，SN節(jié)點(diǎn)在預(yù)先設(shè)置的位置上部署，相鄰節(jié)點(diǎn)間的通信滿足式（1）定義的無(wú)線信道模型，算法仿真重復(fù)次數(shù)為100。具體的參數(shù)定義如表3所示。
表3 實(shí)驗(yàn)仿真參數(shù)
3.2 性能比較與分析
圖3為依次改變網(wǎng)絡(luò)中CN節(jié)點(diǎn)總數(shù)，當(dāng)網(wǎng)絡(luò)容錯(cuò)度k分別為2和4時(shí)，DATC算法和本文設(shè)計(jì)的k-FTDTC算法的網(wǎng)絡(luò)總功耗比較。可以發(fā)現(xiàn)k-FTDTC算法的網(wǎng)絡(luò)總功耗明顯小于經(jīng)典的DATC算法，這是因?yàn)閗-FTDTC算法不僅以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，還基于節(jié)點(diǎn)的有序鄰集對(duì)節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此節(jié)點(diǎn)功率優(yōu)化效果更好。當(dāng)網(wǎng)絡(luò)容錯(cuò)度k從2增加到4時(shí)，整個(gè)網(wǎng)絡(luò)總功耗也在增加，可見(jiàn)網(wǎng)絡(luò)容錯(cuò)度的提高是以犧牲一定的網(wǎng)絡(luò)能量為代價(jià)的。然而當(dāng)網(wǎng)絡(luò)容錯(cuò)度為4時(shí)，增加傳感器節(jié)點(diǎn)數(shù)目，網(wǎng)絡(luò)總功耗反而少量降低，這是因?yàn)槿蒎e(cuò)度的提高意味著節(jié)點(diǎn)間鏈路的增加，對(duì)于鏈路密集的網(wǎng)絡(luò)，雖然傳感器節(jié)點(diǎn)數(shù)目的增加增大了網(wǎng)絡(luò)總功耗，但是由于節(jié)點(diǎn)間距離的縮短也降低了節(jié)點(diǎn)的發(fā)射功率。
圖3 網(wǎng)絡(luò)總功耗比較
圖4為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的最大發(fā)射功率比較?？梢园l(fā)現(xiàn)基于節(jié)點(diǎn)有序鄰集的k-FTDTC算法能夠有效降低節(jié)點(diǎn)的最大發(fā)射功率，使節(jié)點(diǎn)間能量消耗更加均衡。并且，隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目的不斷增加，k-FTDTC算法對(duì)最大發(fā)射功率優(yōu)化更為顯著，能夠有效延長(zhǎng)大規(guī)模HWSN的網(wǎng)絡(luò)生命周期。
圖4 最大發(fā)射功率比較
圖5為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的計(jì)算復(fù)雜度比較?？梢园l(fā)現(xiàn)，不同傳感器節(jié)點(diǎn)規(guī)模與不同容錯(cuò)度下，k-FTDTC算法的計(jì)算復(fù)雜度明顯低于DATC算法。這是因?yàn)镈ATC算法是通過(guò)構(gòu)造有向圖進(jìn)行拓?fù)淇刂?，而本文設(shè)計(jì)的k-FTDTC算法是基于無(wú)向簡(jiǎn)化圖，有效降低了算法的復(fù)雜度，使k-FTDTC算法更適合在計(jì)算能力受限的CN節(jié)點(diǎn)上運(yùn)行。
圖5 計(jì)算復(fù)雜度比較
5 結(jié) 論
在WSN中，除普通的CN節(jié)點(diǎn)外，通過(guò)有計(jì)劃地部署少量能量豐富、通信能力強(qiáng)的SN節(jié)點(diǎn)，組成轉(zhuǎn)發(fā)骨干網(wǎng)，可以有效增強(qiáng)網(wǎng)絡(luò)連通性、降低數(shù)據(jù)轉(zhuǎn)發(fā)延遲、提高網(wǎng)絡(luò)可擴(kuò)展性?；谏鲜霎悩?gòu)無(wú)線傳感器網(wǎng)絡(luò)的容錯(cuò)性拓?fù)淇刂剖且活怤P-難問(wèn)題，本文基于構(gòu)建的HWSN網(wǎng)絡(luò)模型提出了簡(jiǎn)化網(wǎng)絡(luò)圖構(gòu)建方法，將NP-難問(wèn)題進(jìn)行簡(jiǎn)化，進(jìn)行形式化描述。然后，通過(guò)構(gòu)造節(jié)點(diǎn)的有序鄰集來(lái)約束其發(fā)射功率，在保證網(wǎng)絡(luò)k容錯(cuò)性的基礎(chǔ)上最小化網(wǎng)絡(luò)總功耗，提出了一個(gè)k容錯(cuò)性分布式拓?fù)淇刂扑惴ā?shí)驗(yàn)結(jié)果表明，本文所提k-FTDTC算法，相比經(jīng)典的DATC算法，網(wǎng)絡(luò)總功耗、節(jié)點(diǎn)的最大發(fā)射功率以及算法計(jì)算復(fù)雜度明顯降低，從而驗(yàn)證了算法的有效性。
［1］Guidoni D L，Mini R A F，Loureiro A A F.On the design of resilient heterogeneous wireless sensor networks based on small world concepts［J］.Computer Networks，2010，54（8）：1266－1281.
［2］Yin R R，Liu B，Li Y Q，et al.Research on the fault-tolerant topology in energy heterogeneous wireless sensor networks［J］.Journal of Electronics ＆Information Technology，2012，34（9）：2180－2186.（尹榮榮，劉彬，李雅倩，等.能量異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)容錯(cuò)拓?fù)溲芯浚跩］.電子與信息學(xué)報(bào)，2012，34（9）：2180－2186.）
［3］Hajiaghayi M，Nicole I，Vahab S M.Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks［J］.IEEE Trans.on Networking，2007，15（6）：1345－1358.
［4］Rajiv M，Chittaranjan M.Rotation of CDS via connected domatic partition in Ad Hoc sensor networks［J］.IEEE Trans.on Mobile Computing，2009，8（4）：488－499.
［5］Zhao Y X，Wu J，Li F，et al.VBS：maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones［C］∥Proc.of the IEEE INFOCOM，2010：71－75.
［6］Qi X Q，Ma S，Zheng G Z.Topology evolution of wireless sensor networks based on adaptive free-scale networks［J］.Journal of Information and Computational Science，2011，8（3）：467－475.
［7］Rossi K，Choong S H.Fault tolerant virtual backbone for minimum temperature in vivo sensor network［C］∥Proc.of the IEEE International Conference on Communications，2012：3394－3398.
［8］Renato E N，Celso C R，Christophe D.Optimal solutions for fault-tolerant topology control in wireless Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2009，8（12）：5970－5981.
［9］Calinescu G，Wan P J.Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks［J］.Mobile Network Applications，2006，11（2）：121－128.
［10］Dai F，Wu J.On constructing k-connected k-dominating set in wireless Ad Hoc and sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，66（7）：947－958.
［11］Cohen R，Kapchits B.An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor networks［J］.IEEE Trans.on Networks，2009，17（2）：570－581.
［12］Li N，Hou J C.Localized fault-tolerant topology control in wireless ad hoc networks［J］.IEEE Trans.on Parallel and Distributed Systems，2006，17（4）：307－320.
［13］Thai M，Zhang N，Tiwari R.On approximation algorithms of k-connected m-dominating set in disk graphs［J］.Theoretical Computer Science，2007，35（8）：49－59.
［14］Cardei M，Yang S H，Wu J.Algorithms for fault-tolerant topology in heterogeneous wireless sensor networks［J］.IEEE Trans.on Parallel and Distributed Systems，2008，19（4）：545－558.
［15］Gui J S，Liu A F.A new distributed topology control algorithmbased on optimization of delay and energy in wireless networks［J］.Journal of Parallel and Distributed Computing，2012，72（8）：1032－1044.
［16］Luo X J，Yu H Q，Wang X.Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks［J］.International Journal of Systems Science，2013，44（10）：864－877.
［17］Xu Y J，Qi H C.A fault-tolerant topology control algorithm for heterogeneous wireless networks［C］∥Proc.of the International Conference on Computer Science ＆Education，2012：1106－1109.
［18］Andrew Y W.Lower power RF transceiver modeling and design for wireless microsensor networks［D］.Massachusetts：Massachusetts Institute of Technology，2005.
［19］Nishiyama H，Ngo T，Ansari N，et al.On minimizing the impact of mobility on topology control in mobile Ad Hoc networks［J］.IEEE Trans.on Wireless Communications，2012，11（3）：1158－1166.
Algorithm for fault-tolerant topology control in heterogeneous and multi-hop wireless sensor networks
LIU Xing-chuan，WU Zhen-feng，ZHAO Ke-jian
（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing 210007，China）
Heterogeneous wireless sensor networks（HWSN）is a more practical network model because of an improved network performance such as a shorter data-gathering delay and lower network energy consumption.The kfault-tolerant topology control is a kind of NP-hard problem in the HWSN.The paper designs an approach of constructing network reduced graphs based on comprehensive analysis on the network model of HWSN.And the k-fault-tolerant distributed topology control（k-FTDTC）algorithm is proposed based on the ordered reachable neighborhood which is used to restrict the maximum transmission power of the nodes，with the objective of minimizing the total power consumption and preserving k-vertex fault-tolerant property.The experimental results indicate that the k-FTDTC algorithm not only reduces the computational complexity and improves network robustness，but also reduces the total network power consumption and the maximum node power consumption，as compared with the distributed adaptive topology control（DATC）algorithm.
heterogeneous wireless sensor networks（HWST）；topology control；ordered reachable neighborhood；fault-tolerant
TP 393
A
10.3969／j.issn.1001-506X.2015.08.28
劉興川（1982－），男，工程師，博士，主要研究方向?yàn)閃SN容錯(cuò)性拓?fù)淇刂啤⒐?jié)點(diǎn)定位、數(shù)據(jù)融合。
E-mail：liuxch06＠163.com
吳振鋒（1975－），男，研究員，博士，主要研究方向?yàn)閭鞲芯W(wǎng)集成應(yīng)用技術(shù)。
E-mail：wuzhenf＠163.com
趙克儉（1964－），男，研究員，主要研究方向?yàn)閭鞲芯W(wǎng)／物聯(lián)網(wǎng)應(yīng)用技術(shù)。
E-mail：zhaokej＠163.com
1001－506X201508－1902－07
網(wǎng)址：www.sys－ele.com
2014－09－09；
2014－10－30；網(wǎng)絡(luò)優(yōu)先出版日期：2014－11－21。
網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20141121.0956.012.html
江蘇省青年科學(xué)基金（SBK2014042581）資助課題
猜你喜歡
工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00
華中農(nóng)業(yè)大學(xué)學(xué)報(bào)(2024年2期)2024-01-01 00:00:00
小學(xué)教學(xué)研究(2022年5期)2022-04-28 21:29:36
無(wú)線互聯(lián)科技(2017年24期)2018-01-22 10:39:24
中國(guó)管理信息化(2017年18期)2018-01-04 18:41:52
物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11
電信科學(xué)(2016年11期)2016-11-23 05:07:56
通信電源技術(shù)(2016年6期)2016-04-20 06:21:36
工業(yè)設(shè)計(jì)(2016年8期)2016-04-16 02:43:26
電測(cè)與儀表(2015年2期)2015-04-09 11:28:56
