異構(gòu)多跳無線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/h1>
2015-05-25 00:32:19劉興川吳振鋒趙克儉
系統(tǒng)工程與電子技術(shù) 2015年8期
劉興川，吳振鋒，趙克儉
（中國電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)多跳無線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/p>
劉興川，吳振鋒，趙克儉
（中國電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)無線傳感器網(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-難問題。在綜合分析HWSN網(wǎng)絡(luò)模型的基礎(chǔ)上，本文設(shè)計(jì)了簡化網(wǎng)絡(luò)圖構(gòu)建方法，通過構(gòu)造有序鄰集來約束節(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ǎng)絡(luò)；拓?fù)淇刂疲挥行蜞徏蝗蒎e(cuò)性
0 引 言
異構(gòu)無線傳感器網(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ǎng)絡(luò)（wireless sensor network，WSN）早期的拓?fù)淇刂蒲芯恐饕性谕瑯?gòu)WSN，即網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有相同的軟硬件能力，被隨機(jī)部署在監(jiān)測區(qū)域，地位平等，開展能量最優(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ò)。可見，HWSN是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，最近的研究成果［6－8］也表明，相比同構(gòu)網(wǎng)絡(luò)架構(gòu)，HWSN有效降低了監(jiān)測數(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)測異常事件；一類是高能力定點(diǎn)部署的超級(jí)節(jié)點(diǎn)（super node，SN），組成骨干網(wǎng)絡(luò)，完成數(shù)據(jù)融合和快速轉(zhuǎn)發(fā)等任務(wù)，如圖1所示。CN節(jié)點(diǎn)通過多跳方式與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ǎng)絡(luò)模型
針對上述問題，文獻(xiàn)［9－11］利用同構(gòu)網(wǎng)絡(luò)中已有的研究成果，提出了通過構(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-難問題，需要對該問題進(jìn)行簡化，求其次優(yōu)解，同時(shí)分別提出了兩種集中式近似求解算法，但是對于節(jié)點(diǎn)數(shù)據(jù)眾多的WSN而言，集中式拓?fù)淇刂扑惴ú⒉焕诰W(wǎng)絡(luò)規(guī)模的擴(kuò)展。隨后，文獻(xiàn)［14－15］針對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)剩余生命周期的長短，需要綜合考慮節(jié)點(diǎn)的剩余能量和能量消耗速度，同時(shí)這些方法也沒有對節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行控制，因此導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗不均衡。
綜上所述，文獻(xiàn)［9－15］研究的問題與本文相似，目標(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條不相交的路徑是沒有必要的，重要的是使每一個(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ì)簡化圖方法來對HWSN網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，以降低算法求解復(fù)雜度；通過構(gòu)造CN節(jié)點(diǎn)的有序鄰集來控制節(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)，對本文提出的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ò)模型與問題描述
式中，Pr表示接收功率；λ為電磁波長；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è)無向加權(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ù)。ω為對應(yīng)E中每條邊的權(quán)值集合。下面給出用到的幾個(gè)定義：
定義1 邊的權(quán)重：用ω（ni，nj）表示，定義為節(jié)點(diǎn)ni與nj間通信所需的最小發(fā)射功率，具體值可以通過式（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)測目標(biāo)的信息，周期性地將感知數(shù)據(jù)通過多跳方式傳送給附近的SN節(jié)點(diǎn)，其主要的能耗來自于數(shù)據(jù)的無線收發(fā)。相比CN節(jié)點(diǎn)，SN節(jié)點(diǎn)具有更多能量、更強(qiáng)的計(jì)算存儲(chǔ)能力、更長的通信距離和更高的數(shù)據(jù)速率，SN節(jié)點(diǎn)間形成骨干網(wǎng)絡(luò)，主要負(fù)責(zé)對CN節(jié)點(diǎn)的感知數(shù)據(jù)進(jìn)行融合處理、判決計(jì)算，實(shí)時(shí)可靠地將結(jié)果轉(zhuǎn)發(fā)給監(jiān)測中心。SN節(jié)點(diǎn)的應(yī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ò)，鏈路具有對稱性，每個(gè)節(jié)點(diǎn)具有唯一ID，節(jié)點(diǎn)間通信滿足文獻(xiàn)［18］提出的無線信道模型，即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ù)能通過SN節(jié)點(diǎn)傳送到監(jiān)控中心。
1.2 問題描述及簡化
基于上述異構(gòu)多跳網(wǎng)絡(luò)模型，k-FTDTC算法的目標(biāo)是：①通過調(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ǎng)絡(luò)圖G＝（V，E，ω）進(jì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)化為簡化圖G1＝（V1，E1，ω1），簡化圖偽代碼如表1所示。
表1 簡化圖G1構(gòu)建算法偽代碼
定義6 簡化圖k點(diǎn)連通root節(jié)點(diǎn)：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則稱簡化圖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)對應(yīng)的簡化圖是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條不相交的路徑，即簡化圖G1是k點(diǎn)連通root節(jié)點(diǎn)。
（2）充分性。如果簡化圖G1是k點(diǎn)連通root節(jié)點(diǎn)，則表明對于任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)。因此，對于圖G1中到根節(jié)點(diǎn)的任意路徑｛ni0，ni1，…，nim，root｝，都可以通過用一個(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與其簡化圖G1的關(guān)系。
圖2 圖G與其簡化圖G1間的關(guān)系
如果節(jié)點(diǎn)數(shù)很多時(shí)，基于簡化圖的k-FTDTC問題仍然是NP-難問題［19］，很難計(jì)算最優(yōu)解，因此本文基于簡化圖G1提出一種分布式近似算法來進(jìn)行求解。
2 容錯(cuò)性分布式拓?fù)淇刂扑惴ㄔO(shè)計(jì)
本文設(shè)計(jì)的k-FTDTC算法用到的參數(shù)定義如下：
flagi∶flagi為1表示節(jié)點(diǎn)ni確定了其最終發(fā)射功率，否則flagi為0；
di：簡化圖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算法基本思想是：通過信息交換，建立節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)信息列表，并通過節(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ǔ)上，通過降低節(jié)點(diǎn)的發(fā)射功率，來優(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列表中，否則不做任何處理。最后對節(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)行廣播。
對于任意節(jié)點(diǎn)ni，基于上述思想進(jìn)行k連通構(gòu)建，確定其最佳發(fā)射功率，最多需要｜F（ni）＿list＿ID｜－k輪。在每一輪中，節(jié)點(diǎn)通過廣播獲得其一跳范圍內(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算法偽代碼
下面通過定理2對本文提出的k-FTDTC算法有效性進(jìn)行證明。
定理2 若G1是k點(diǎn)連通root節(jié)點(diǎn)，則通過k-FTDTC算法對每個(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)，因此對于G1中任意節(jié)點(diǎn)nv，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)，不失一般性，定義這k條不相交的路徑為：r1，r2，…，rk。若定義任意節(jié)點(diǎn)ni的發(fā)射功率是通過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，則通過路徑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對算法進(jìn)行仿真，并與經(jīng)典的分布式拓?fù)淇刂扑惴―ATC進(jìn)行比較，以驗(yàn)證k-FTDTC算法的性能。DATC算法是分布式拓?fù)淇刂扑惴ǎ摲椒ㄔ诿總€(gè)節(jié)點(diǎn)位置已知的前提下，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，對節(jié)點(diǎn)發(fā)射功率進(jìn)行調(diào)整以保證網(wǎng)絡(luò)是k點(diǎn)連通的。由于DATC算法是通過構(gòu)造有向圖進(jìn)行拓?fù)淇刂疲虼怂惴ㄏ鄬?fù)雜；其次該方法要求所有節(jié)點(diǎn)知道自身位置信息，適用性受限；最后該方法并沒有對節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此存在網(wǎng)絡(luò)能量均衡問題。
本文主要采用3項(xiàng)性能指標(biāo)對上述兩種算法進(jìn)行評(píng)價(jià)：①網(wǎng)絡(luò)總功耗，即網(wǎng)絡(luò)中每個(gè)CN節(jié)點(diǎn)發(fā)射功率之和；②最大發(fā)射功率，即經(jīng)過拓?fù)淇刂坪螅泄?jié)點(diǎn)中最大的發(fā)射功率，主要用來衡量網(wǎng)絡(luò)節(jié)點(diǎn)間能量均衡和網(wǎng)絡(luò)生命周期；③計(jì)算復(fù)雜度：HWSN進(jìn)行拓?fù)淇刂疲?jié)點(diǎn)功率優(yōu)化過程中，算法執(zhí)行基本運(yùn)算的數(shù)量。
3.1 仿真場景和參數(shù)設(shè)置
N節(jié)點(diǎn)隨機(jī)部署在500m×500m的方形平面區(qū)域內(nèi)，SN節(jié)點(diǎn)在預(yù)先設(shè)置的位置上部署，相鄰節(jié)點(diǎn)間的通信滿足式（1）定義的無線信道模型，算法仿真重復(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)的有序鄰集對節(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ò)總功耗也在增加，可見網(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)間鏈路的增加，對于鏈路密集的網(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ā)射功率比較。可以發(fā)現(xiàn)基于節(jié)點(diǎn)有序鄰集的k-FTDTC算法能夠有效降低節(jié)點(diǎn)的最大發(fā)射功率，使節(jié)點(diǎn)間能量消耗更加均衡。并且，隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目的不斷增加，k-FTDTC算法對最大發(fā)射功率優(yōu)化更為顯著，能夠有效延長大規(guī)模HWSN的網(wǎng)絡(luò)生命周期。
圖4 最大發(fā)射功率比較
圖5為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的計(jì)算復(fù)雜度比較。可以發(fā)現(xiàn)，不同傳感器節(jié)點(diǎn)規(guī)模與不同容錯(cuò)度下，k-FTDTC算法的計(jì)算復(fù)雜度明顯低于DATC算法。這是因?yàn)镈ATC算法是通過構(gòu)造有向圖進(jìn)行拓?fù)淇刂疲疚脑O(shè)計(jì)的k-FTDTC算法是基于無向簡化圖，有效降低了算法的復(fù)雜度，使k-FTDTC算法更適合在計(jì)算能力受限的CN節(jié)點(diǎn)上運(yùn)行。
圖5 計(jì)算復(fù)雜度比較
5 結(jié) 論
在WSN中，除普通的CN節(jié)點(diǎn)外，通過有計(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ǎng)絡(luò)的容錯(cuò)性拓?fù)淇刂剖且活怤P-難問題，本文基于構(gòu)建的HWSN網(wǎng)絡(luò)模型提出了簡化網(wǎng)絡(luò)圖構(gòu)建方法，將NP-難問題進(jìn)行簡化，進(jìn)行形式化描述。然后，通過構(gòu)造節(jié)點(diǎn)的有序鄰集來約束其發(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ǎ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）資助課題
猜你喜歡
基于N-gram相似度增強(qiáng)蛋白質(zhì)肽段組裝的方法電腦知識(shí)與技術(shù)(2025年18期)2025-07-20 00:00:00 永遠(yuǎn)不要用“起點(diǎn)”定義自己海峽姐妹(2020年9期)2021-01-04 01:35:44 定義“風(fēng)格”VOGUE服飾與美容(2020年9期)2020-09-02 14:47:26 大擺臂分流器在行李處理系統(tǒng)中的應(yīng)用設(shè)計(jì)科技資訊(2019年7期)2019-06-17 01:24:12 基于一致性哈希的高可用多級(jí)緩存系統(tǒng)設(shè)計(jì)無線互聯(lián)科技(2017年5期)2017-06-21 18:14:46 基于認(rèn)知心理學(xué)的交互式產(chǎn)品的容錯(cuò)性設(shè)計(jì)研究工業(yè)設(shè)計(jì)(2016年8期)2016-04-16 02:43:26 成功的定義山東青年(2016年1期)2016-02-28 14:25:25 基于免疫算法的高容錯(cuò)性廣域保護(hù)研究電測與儀表(2015年2期)2015-04-09 11:28:56 基于多Agent的有限廣域方向比較算法與仿真實(shí)現(xiàn)電子技術(shù)與軟件工程(2014年20期)2014-11-19 09:46:07 修辭學(xué)的重大定義當(dāng)代修辭學(xué)(2014年3期)2014-01-21 02:30:44
劉興川，吳振鋒，趙克儉
（中國電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)多跳無線傳感器網(wǎng)絡(luò)容錯(cuò)性拓?fù)淇刂扑惴?/p>
劉興川，吳振鋒，趙克儉
（中國電子科技集團(tuán)公司第二十八研究所，江蘇南京210007）
異構(gòu)無線傳感器網(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-難問題。在綜合分析HWSN網(wǎng)絡(luò)模型的基礎(chǔ)上，本文設(shè)計(jì)了簡化網(wǎng)絡(luò)圖構(gòu)建方法，通過構(gòu)造有序鄰集來約束節(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ǎng)絡(luò)；拓?fù)淇刂疲挥行蜞徏蝗蒎e(cuò)性
0 引 言
異構(gòu)無線傳感器網(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ǎng)絡(luò)（wireless sensor network，WSN）早期的拓?fù)淇刂蒲芯恐饕性谕瑯?gòu)WSN，即網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)具有相同的軟硬件能力，被隨機(jī)部署在監(jiān)測區(qū)域，地位平等，開展能量最優(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ò)。可見，HWSN是一種更現(xiàn)實(shí)的網(wǎng)絡(luò)模型，最近的研究成果［6－8］也表明，相比同構(gòu)網(wǎng)絡(luò)架構(gòu)，HWSN有效降低了監(jiān)測數(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)測異常事件；一類是高能力定點(diǎn)部署的超級(jí)節(jié)點(diǎn)（super node，SN），組成骨干網(wǎng)絡(luò)，完成數(shù)據(jù)融合和快速轉(zhuǎn)發(fā)等任務(wù)，如圖1所示。CN節(jié)點(diǎn)通過多跳方式與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ǎng)絡(luò)模型
針對上述問題，文獻(xiàn)［9－11］利用同構(gòu)網(wǎng)絡(luò)中已有的研究成果，提出了通過構(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-難問題，需要對該問題進(jìn)行簡化，求其次優(yōu)解，同時(shí)分別提出了兩種集中式近似求解算法，但是對于節(jié)點(diǎn)數(shù)據(jù)眾多的WSN而言，集中式拓?fù)淇刂扑惴ú⒉焕诰W(wǎng)絡(luò)規(guī)模的擴(kuò)展。隨后，文獻(xiàn)［14－15］針對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)剩余生命周期的長短，需要綜合考慮節(jié)點(diǎn)的剩余能量和能量消耗速度，同時(shí)這些方法也沒有對節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行控制，因此導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)能量消耗不均衡。
綜上所述，文獻(xiàn)［9－15］研究的問題與本文相似，目標(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條不相交的路徑是沒有必要的，重要的是使每一個(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ì)簡化圖方法來對HWSN網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，以降低算法求解復(fù)雜度；通過構(gòu)造CN節(jié)點(diǎn)的有序鄰集來控制節(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)，對本文提出的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ò)模型與問題描述
式中，Pr表示接收功率；λ為電磁波長；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è)無向加權(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ù)。ω為對應(yīng)E中每條邊的權(quán)值集合。下面給出用到的幾個(gè)定義：
定義1 邊的權(quán)重：用ω（ni，nj）表示，定義為節(jié)點(diǎn)ni與nj間通信所需的最小發(fā)射功率，具體值可以通過式（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)測目標(biāo)的信息，周期性地將感知數(shù)據(jù)通過多跳方式傳送給附近的SN節(jié)點(diǎn)，其主要的能耗來自于數(shù)據(jù)的無線收發(fā)。相比CN節(jié)點(diǎn)，SN節(jié)點(diǎn)具有更多能量、更強(qiáng)的計(jì)算存儲(chǔ)能力、更長的通信距離和更高的數(shù)據(jù)速率，SN節(jié)點(diǎn)間形成骨干網(wǎng)絡(luò)，主要負(fù)責(zé)對CN節(jié)點(diǎn)的感知數(shù)據(jù)進(jìn)行融合處理、判決計(jì)算，實(shí)時(shí)可靠地將結(jié)果轉(zhuǎn)發(fā)給監(jiān)測中心。SN節(jié)點(diǎn)的應(yī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ò)，鏈路具有對稱性，每個(gè)節(jié)點(diǎn)具有唯一ID，節(jié)點(diǎn)間通信滿足文獻(xiàn)［18］提出的無線信道模型，即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ù)能通過SN節(jié)點(diǎn)傳送到監(jiān)控中心。
1.2 問題描述及簡化
基于上述異構(gòu)多跳網(wǎng)絡(luò)模型，k-FTDTC算法的目標(biāo)是：①通過調(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ǎng)絡(luò)圖G＝（V，E，ω）進(jì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)化為簡化圖G1＝（V1，E1，ω1），簡化圖偽代碼如表1所示。
表1 簡化圖G1構(gòu)建算法偽代碼
定義6 簡化圖k點(diǎn)連通root節(jié)點(diǎn)：任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)根節(jié)點(diǎn)root，則稱簡化圖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)對應(yīng)的簡化圖是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條不相交的路徑，即簡化圖G1是k點(diǎn)連通root節(jié)點(diǎn)。
（2）充分性。如果簡化圖G1是k點(diǎn)連通root節(jié)點(diǎn)，則表明對于任意CN節(jié)點(diǎn)即?ni∈V且i≤N，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)。因此，對于圖G1中到根節(jié)點(diǎn)的任意路徑｛ni0，ni1，…，nim，root｝，都可以通過用一個(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與其簡化圖G1的關(guān)系。
圖2 圖G與其簡化圖G1間的關(guān)系
如果節(jié)點(diǎn)數(shù)很多時(shí)，基于簡化圖的k-FTDTC問題仍然是NP-難問題［19］，很難計(jì)算最優(yōu)解，因此本文基于簡化圖G1提出一種分布式近似算法來進(jìn)行求解。
2 容錯(cuò)性分布式拓?fù)淇刂扑惴ㄔO(shè)計(jì)
本文設(shè)計(jì)的k-FTDTC算法用到的參數(shù)定義如下：
flagi∶flagi為1表示節(jié)點(diǎn)ni確定了其最終發(fā)射功率，否則flagi為0；
di：簡化圖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算法基本思想是：通過信息交換，建立節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)信息列表，并通過節(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ǔ)上，通過降低節(jié)點(diǎn)的發(fā)射功率，來優(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列表中，否則不做任何處理。最后對節(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)行廣播。
對于任意節(jié)點(diǎn)ni，基于上述思想進(jìn)行k連通構(gòu)建，確定其最佳發(fā)射功率，最多需要｜F（ni）＿list＿ID｜－k輪。在每一輪中，節(jié)點(diǎn)通過廣播獲得其一跳范圍內(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算法偽代碼
下面通過定理2對本文提出的k-FTDTC算法有效性進(jìn)行證明。
定理2 若G1是k點(diǎn)連通root節(jié)點(diǎn)，則通過k-FTDTC算法對每個(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)，因此對于G1中任意節(jié)點(diǎn)nv，存在k條不相交的路徑到達(dá)root節(jié)點(diǎn)，不失一般性，定義這k條不相交的路徑為：r1，r2，…，rk。若定義任意節(jié)點(diǎn)ni的發(fā)射功率是通過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，則通過路徑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對算法進(jìn)行仿真，并與經(jīng)典的分布式拓?fù)淇刂扑惴―ATC進(jìn)行比較，以驗(yàn)證k-FTDTC算法的性能。DATC算法是分布式拓?fù)淇刂扑惴ǎ摲椒ㄔ诿總€(gè)節(jié)點(diǎn)位置已知的前提下，以最小化網(wǎng)絡(luò)總功耗為目標(biāo)，對節(jié)點(diǎn)發(fā)射功率進(jìn)行調(diào)整以保證網(wǎng)絡(luò)是k點(diǎn)連通的。由于DATC算法是通過構(gòu)造有向圖進(jìn)行拓?fù)淇刂疲虼怂惴ㄏ鄬?fù)雜；其次該方法要求所有節(jié)點(diǎn)知道自身位置信息，適用性受限；最后該方法并沒有對節(jié)點(diǎn)的最大發(fā)射功率進(jìn)行有效約束，因此存在網(wǎng)絡(luò)能量均衡問題。
本文主要采用3項(xiàng)性能指標(biāo)對上述兩種算法進(jìn)行評(píng)價(jià)：①網(wǎng)絡(luò)總功耗，即網(wǎng)絡(luò)中每個(gè)CN節(jié)點(diǎn)發(fā)射功率之和；②最大發(fā)射功率，即經(jīng)過拓?fù)淇刂坪螅泄?jié)點(diǎn)中最大的發(fā)射功率，主要用來衡量網(wǎng)絡(luò)節(jié)點(diǎn)間能量均衡和網(wǎng)絡(luò)生命周期；③計(jì)算復(fù)雜度：HWSN進(jìn)行拓?fù)淇刂疲?jié)點(diǎn)功率優(yōu)化過程中，算法執(zhí)行基本運(yùn)算的數(shù)量。
3.1 仿真場景和參數(shù)設(shè)置
N節(jié)點(diǎn)隨機(jī)部署在500m×500m的方形平面區(qū)域內(nèi)，SN節(jié)點(diǎn)在預(yù)先設(shè)置的位置上部署，相鄰節(jié)點(diǎn)間的通信滿足式（1）定義的無線信道模型，算法仿真重復(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)的有序鄰集對節(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ò)總功耗也在增加，可見網(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)間鏈路的增加，對于鏈路密集的網(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ā)射功率比較。可以發(fā)現(xiàn)基于節(jié)點(diǎn)有序鄰集的k-FTDTC算法能夠有效降低節(jié)點(diǎn)的最大發(fā)射功率，使節(jié)點(diǎn)間能量消耗更加均衡。并且，隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)數(shù)目的不斷增加，k-FTDTC算法對最大發(fā)射功率優(yōu)化更為顯著，能夠有效延長大規(guī)模HWSN的網(wǎng)絡(luò)生命周期。
圖4 最大發(fā)射功率比較
圖5為DATC算法和本文設(shè)計(jì)的k-FTDTC算法的計(jì)算復(fù)雜度比較。可以發(fā)現(xiàn)，不同傳感器節(jié)點(diǎn)規(guī)模與不同容錯(cuò)度下，k-FTDTC算法的計(jì)算復(fù)雜度明顯低于DATC算法。這是因?yàn)镈ATC算法是通過構(gòu)造有向圖進(jìn)行拓?fù)淇刂疲疚脑O(shè)計(jì)的k-FTDTC算法是基于無向簡化圖，有效降低了算法的復(fù)雜度，使k-FTDTC算法更適合在計(jì)算能力受限的CN節(jié)點(diǎn)上運(yùn)行。
圖5 計(jì)算復(fù)雜度比較
5 結(jié) 論
在WSN中，除普通的CN節(jié)點(diǎn)外，通過有計(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ǎng)絡(luò)的容錯(cuò)性拓?fù)淇刂剖且活怤P-難問題，本文基于構(gòu)建的HWSN網(wǎng)絡(luò)模型提出了簡化網(wǎng)絡(luò)圖構(gòu)建方法，將NP-難問題進(jìn)行簡化，進(jìn)行形式化描述。然后，通過構(gòu)造節(jié)點(diǎn)的有序鄰集來約束其發(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ǎ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）資助課題
猜你喜歡
電腦知識(shí)與技術(shù)(2025年18期)2025-07-20 00:00:00
海峽姐妹(2020年9期)2021-01-04 01:35:44
VOGUE服飾與美容(2020年9期)2020-09-02 14:47:26
科技資訊(2019年7期)2019-06-17 01:24:12
無線互聯(lián)科技(2017年5期)2017-06-21 18:14:46
工業(yè)設(shè)計(jì)(2016年8期)2016-04-16 02:43:26
山東青年(2016年1期)2016-02-28 14:25:25
電測與儀表(2015年2期)2015-04-09 11:28:56
電子技術(shù)與軟件工程(2014年20期)2014-11-19 09:46:07
當(dāng)代修辭學(xué)(2014年3期)2014-01-21 02:30:44
