異構多跳無線傳感器網絡容錯性拓撲控制算法

劉興川，吳振鋒，趙克儉

（中國電子科技集團公司第二十八研究所，江蘇南京210007）

異構多跳無線傳感器網絡容錯性拓撲控制算法

劉興川，吳振鋒，趙克儉

（中國電子科技集團公司第二十八研究所，江蘇南京210007）

異構無線傳感器網絡（heterogeneous wireless sensor works，HWSN）能有效降低數據轉發延遲、網絡能量消耗，是一種更現實的網絡模型，基于HWSN的k容錯性拓撲控制是一類NP-難問題。在綜合分析HWSN網絡模型的基礎上，本文設計了簡化網絡圖構建方法，通過構造有序鄰集來約束節點的最大發射功率，以網絡總功耗與容錯性雙優化為目標，實現了一個k容錯性分布式拓撲控制算法（k-fault-tolerant distributed topology control，k-FTDTC）。實驗結果表明，相比分布式拓撲控制（distributed adaptive topology control，DATC）方法，k-FTDTC算法有效降低了網絡總功耗和最大發射功率，且具有較好的容錯性和較低算法復雜度。

異構無線傳感器網絡；拓撲控制；有序鄰集；容錯性

0 引 言

異構無線傳感器網絡（heterogeneous wireless sensor networks，HWSN）是指由多種不同類型的傳感器節點構成的網絡，傳感器節點的異構性主要表現在：計算能力異構、通信能力異構以及節點能量異構［1－2］。無線傳感器網絡（wireless sensor network，WSN）早期的拓撲控制研究主要集中在同構WSN，即網絡中所有傳感器節點具有相同的軟硬件能力，被隨機部署在監測區域，地位平等，開展能量最優化研究［3－5］。然而在實際環境中，傳感器節點通常承擔不同的角色功能，甚至具有不同的資源配置以適應多樣化的應用需求。此外，即使是同構的WSN，由于節點感知任務的不同所造成的能耗不同，也促使初始能量相同的網絡逐漸演變成多級能量異構網絡?？梢姡琀WSN是一種更現實的網絡模型，最近的研究成果［6－8］也表明，相比同構網絡架構，HWSN有效降低了監測數據轉發延遲、網絡能量消耗，具有更優的網絡性能。

本文研究的HWSN是由兩類傳感器節點組成：一類是資源受限隨機部署的傳感器節點，稱為普通節點（common node，CN），用于感知監測異常事件；一類是高能力定點部署的超級節點（super node，SN），組成骨干網絡，完成數據融合和快速轉發等任務，如圖1所示。CN節點通過多跳方式與SN節點進行通信，由于復雜惡劣環境的影響，經常導致CN節點間通信鏈路失效，再加上CN節點能量受限，如何在保證網絡具有容錯性的基礎上最優化網絡能量消耗成為HWSN拓撲控制亟需解決的一個難題。

圖1 異構無線傳感器網絡模型

針對上述問題，文獻［9－11］利用同構網絡中已有的研究成果，提出了通過構造網絡的k點連通圖建立容錯性拓撲，即網絡中任意兩個節點之間都至少存在k條不相交的路徑，當任意k－1個節點或鏈路發生故障時，網絡仍然保持連通，該方法可有效提高網絡容錯性，但是由于任意節點都要保持k條不相交的路徑，因此導致整個網絡能耗隨其容錯能力的提升成倍增加。文獻［12－13］證明了k點連通圖構建是一個NP-難問題，需要對該問題進行簡化，求其次優解，同時分別提出了兩種集中式近似求解算法，但是對于節點數據眾多的WSN而言，集中式拓撲控制算法并不利于網絡規模的擴展。隨后，文獻［14－15］針對HWSN容錯性拓撲控制，基于節點剩余能量，以最小化網絡總功耗為目標，提出k點連通圖的分布式近似求解算法。但是在多跳網絡中節點剩余能量多少并不能準確反映節點剩余生命周期的長短，需要綜合考慮節點的剩余能量和能量消耗速度，同時這些方法也沒有對節點的最大發射功率進行控制，因此導致網絡中節點能量消耗不均衡。

綜上所述，文獻［9－15］研究的問題與本文相似，目標都是在保證網絡具有k容錯性的基礎上，最小化網絡總功耗。本文與上述工作的不同之處主要體現在：①在HWSN中，感知數據從CN節點發送到SN節點，因此在任意兩個節點之間都保持k條不相交的路徑是沒有必要的，重要的是使每一個CN節點存在k條不相交的路徑可達SN節點。基于上述思想，本文設計的目標函數是保證任意CN節點與SN節點集都存在k條不相交的路徑，在此基礎上最小化網絡總功耗。②綜合分析異構多跳WSN的特點，設計簡化圖方法來對HWSN網絡模型進行優化，以降低算法求解復雜度；通過構造CN節點的有序鄰集來控制節點的最大發射功率，以最小化網絡總功耗與能量均衡雙優化為目標，實現k容錯性分布式拓撲控制（k-fault-tolerant distributed topology control，k-FTDTC）算法，提高網絡健壯性。③基于仿真實驗，對本文提出的k-FTDTC算法性能進行了詳實的評估，同時與經典的分布式拓撲控制（distributed adaptive topology control，DATC）算法［15］進行性能比較，以驗證本文算法的有效性。

1 網絡模型與問題描述

式中，Pr表示接收功率；λ為電磁波長；d0為參考距離，一般為1m，d是發射天線與接收天線之間的距離；n是路徑損耗系數；G1，G2分別是發射天線增益和接收天線增益。

根據上述假設，CN節點和SN節點共同構成一個連通的網絡，可抽象為一個無向加權網絡圖G＝（V，E，ω），其中點集V包含N個CN節點和M個SN節點，即V＝｛n1，n2，…，nN＋1，…，nN＋M｝，前N個為CN節點，后M個為SN節點。E為邊集，定義為E＝｛（ni，nj）｜dist（ni，nj）≤Dmax｝，其中dist（·）為歐式距離函數。ω為對應E中每條邊的權值集合。下面給出用到的幾個定義：

定義1 邊的權重：用ω（ni，nj）表示，定義為節點ni與nj間通信所需的最小發射功率，具體值可以通過式（1）計算。

定義2 可達鄰集：用F（ni）表示，定義為節點ni以最大傳輸距離Dmax進行通信，所能到達的節點集合，即F（ni）＝｛nj｜nj∈V，（ni，nj）∈E｝。

定義3 節點的功率：用P（ni）表示，定義為P（ni）＝

1.1 網絡模型

本文討論的HWSN網絡模型如圖1所示，包括N個CN節點和M個SN節點，其中M?N。其中，CN節點隨機分布，能量受限，具有短的通信能力和低的數據速率，主要任務是實時感知監測目標的信息，周期性地將感知數據通過多跳方式傳送給附近的SN節點，其主要的能耗來自于數據的無線收發。相比CN節點，SN節點具有更多能量、更強的計算存儲能力、更長的通信距離和更高的數據速率，SN節點間形成骨干網絡，主要負責對CN節點的感知數據進行融合處理、判決計算，實時可靠地將結果轉發給監測中心。SN節點的應用不僅延長了整個網絡生命周期，還降低了端到端的數據傳輸延遲，因此，該結構在實際中被廣泛研究和應用［16－17］。上述模型滿足以下假設條件：

（1）CN節點隨機密集部署，具有相同的軟硬件，初始能量相同且為Einit，通信距離可調節，最大通信距離為Dmax；

（2）SN節點為高能力節點，定點部署，初始能量定義為Einit（1＋K），其中K表示SN節點能量是CN節點能量的倍數；

（3）CN節點間、CN節點與SN節點間的通信鏈路是本文拓撲控制研究的重點，而由于SN節點為定點部署且為高能力節點，本文認為SN節點間通信鏈路是固定可靠的，不屬于本文拓撲控制關注的重點。

（4）CN節點與SN節點分布在二維平面上，形成一個靜態連通性網絡，鏈路具有對稱性，每個節點具有唯一ID，節點間通信滿足文獻［18］提出的無線信道模型，即max｛nj｜（ni，nj）∈E｝ω（ni，nj）。

定義4 網絡圖G總的功耗：用P（G）表示，為圖G中各節點功率之和，即

定義5 k點連通SN節點集：任意CN節點即?ni∈V且i≤N，存在k條不相交的路徑到達SN節點集，即任意k－1個CN節點或鏈路出現故障時，網絡仍保持連通，即CN節點的感知數據能通過SN節點傳送到監控中心。

1.2 問題描述及簡化

基于上述異構多跳網絡模型，k-FTDTC算法的目標是：①通過調節CN節點的功率，使每個CN節點與SN節點集間存在k條不相交的路徑；②優化CN節點的最大發射功率，并使所有CN節點功耗之和最小，即

結合k-FTDTC問題描述，本文將網絡圖G＝（V，E，ω）進行簡化求解，簡化規則如下：

（1）用一個根節點取代M個SN節點，形成的新點集為V1＝｛n1，n2，…，nN，root｝，這是因為研究表明SN節點間的通信鏈路是可靠的［17］。

（2）節點之間的邊保持不變，若同一個CN節點與兩個或兩個以上的SN節點相連，則僅保留邊權值最小的那條邊。這是因為k-FTDTC的目標是使CN節點與SN連通并最小化CN節點發射功率。

（3）邊的權重保持不變。

利用上述規則設計算法1將網絡圖G＝（V，E，ω）轉化為簡化圖G1＝（V1，E1，ω1），簡化圖偽代碼如表1所示。

表1 簡化圖G1構建算法偽代碼

定義6 簡化圖k點連通root節點：任意CN節點即?ni∈V且i≤N，存在k條不相交的路徑到達根節點root，則稱簡化圖k點連通root節點。

根據定義7可以獲得定理1。

定理1 異構多跳WSN是k點連通SN節點當且僅當對應的簡化圖是k點連通root節點。

證明 （1）必要性。由于異構多跳WSN是k點連通SN節點，即?ni∈V且i≤N的節點，都存在k條不相交的路徑到達SN節點集。用根節點root取代每條路徑上的SN節點，即獲得任意CN節點即?ni∈V且i≤N與根節點root之間的k條不相交的路徑，即簡化圖G1是k點連通root節點。

（2）充分性。如果簡化圖G1是k點連通root節點，則表明對于任意CN節點即?ni∈V且i≤N，存在k條不相交的路徑到達root節點。因此，對于圖G1中到根節點的任意路徑｛ni0，ni1，…，nim，root｝，都可以通過用一個SN節點即nk，k＞N，取代根節點root，而獲得等價路徑｛ni0，ni1，…，nim，nk｝，使（nim，nk）∈E，ω（nim，nk）＝ω1（nim，root），從而獲得?ni∈V且i≤N與SN節點集之間的k條不相交的路徑，即圖G是k點連通SN節點。圖2表示k＝3時，圖G與其簡化圖G1的關系。

圖2 圖G與其簡化圖G1間的關系

如果節點數很多時，基于簡化圖的k-FTDTC問題仍然是NP-難問題［19］，很難計算最優解，因此本文基于簡化圖G1提出一種分布式近似算法來進行求解。

2 容錯性分布式拓撲控制算法設計

本文設計的k-FTDTC算法用到的參數定義如下：

flagi∶flagi為1表示節點ni確定了其最終發射功率，否則flagi為0；

di：簡化圖G1中節點ni當前的通信半徑；

P（Dmax）：節點在最大通信距離下的發射功率；

F（ni）＿list：節點以P（Dmax）進行通信時，節點ni的鄰居列表，包含鄰居節點ID及節點間的接收信號強度，即F（ni）＿list＝｛F（ni）＿list＿ID，F（ni）＿list＿RSS｝；

G1（ni）＝（Vni，Eni）：節點ni的局部拓撲，其中

F1（ni）：節點ni在通信半徑為di時的鄰集，F1（ni）＝｛nj｜dist（ni，nj）≤di｝；

F2（ni）：在圖G1（ni）中與節點nik點連通且不在其鄰集F1（ni）中的節點集合，F2（ni）＝｛nj｜di＜dist（ni，nj）≤Dmax，且ni，nj在G1（ni）是k點連通｝；

本文提出的k-FTDTC算法基本思想是：通過信息交換，建立節點ni的鄰居節點信息列表，并通過節點間的RSS進行排序，獲得有序鄰集F（ni）＿list；然后基于有序鄰集F（ni）＿list分別計算獲得和，由于任意節點ni若存在k條不相交的路徑到達根節點root，則節點ni的發射功率最小能到達其k個鄰居節點，因此定義節點ni的初始發射功率為；最后根據有序鄰集，不斷增加節點ni的發射功率Pi，使F（ni）＿list＿ID＝F1（ni）∪F2（ni），即F（ni）＿list中的任意節點nj屬于F1（ni）∪F2（ni）。滿足以上條件的發射功率Pi即為節點ni的最終發射功率，在保證任意節點k連通到根節點基礎上，通過降低節點的發射功率，來優化網絡能量消耗。

k-FTDTC算法具體包括3個部分：構建有序鄰集，Pmini與計算和k連通構建。

2.1 構建有序鄰集

網絡中的所有節點依次以最大發射功率廣播Hello消息，消息中包括節點ID。任意收到Hello的節點nj回復Response消息，Response消息中包括接收到的節點的ID以及其自身的ID。當節點ni接收到包含其自身ID的Response消息時，判定節點nj是否已在F（ni）＿list列表中。若不存在，則將節點nj的ID，以及節點和nj間的RSS存儲于節點ni的鄰集F（ni）＿list列表中，否則不做任何處理。最后對節點ni的鄰集按照節點間的RSS非遞增方式進行排序，獲得有序鄰集F（ni）＿list。

任意節點ni若存在k條不相交的路徑到達根節點root，則節點ni的最小發射功率應能到達其鄰集F（ni）＿list中最近的k個節點，因此節點ni保持k點連通的發射功率將會在和之間。CN節點的最大發射功率P（Dmax）通常已知，有序鄰集F（ni）＿list列表中存儲了節點ni接收到其鄰居節點的信號強度，因此基于有序鄰集F（ni）＿list，可以計算得到節點ni的和。計算公式如下：

式中，F（ni）＿list＿RSS［k］表示節點ni接收到距其第k遠鄰居節點的信號強度；｜F（ni）＿list｜表示列表中節點的數目。

2.3 k連通構建

k-FTDTC算法中k連通構建的基本思想是：任選一個節點ni，定義其初始發射功率為，根據有序鄰集，在，］逐次增加節點ni發射功率，使其鄰居節點F1（ni）逐個增加，當滿足F（ni）＿list＿ID＝＝F1（ni）∪F2（ni）時，即獲得ni的最佳發射功率，并向其鄰居節點進行廣播。

對于任意節點ni，基于上述思想進行k連通構建，確定其最佳發射功率，最多需要｜F（ni）＿list＿ID｜－k輪。在每一輪中，節點通過廣播獲得其一跳范圍內節點的拓撲關系，同時節點ni利用有序鄰集可自適應地獲得其發射功率Pi每次調整的增幅Δp，Δp利用式（4）計算獲得，從而保證每輪中至少有一個節點加入到F1（ni）中，提高了k連通構建的效率。

其中每一輪后，k的值進行自增，因此可知k值自增的次數與k連通構建進行的輪次一致。

本文設計的k-FTDTC算法的偽代碼如表2所示。

表2 k－FTDTC算法偽代碼

下面通過定理2對本文提出的k-FTDTC算法有效性進行證明。

定理2 若G1是k點連通root節點，則通過k-FTDTC算法對每個CN節點的發射功率進行優化分配后，G1仍是k點連通到root節點。

證明 由于G1是k點連通root節點，因此對于G1中任意節點nv，存在k條不相交的路徑到達root節點，不失一般性，定義這k條不相交的路徑為：r1，r2，…，rk。若定義任意節點ni的發射功率是通過k-FTDTC算法調整后獲得的，其有序鄰集為F（ni）＿list，假設nj是其有序鄰集中的任意節點，若能證明節點ni的發射功率經調整后，被刪除的任意邊（ni，nj）不影響節點nv與節點k點連通性，則證明了本文所提出的k-FTDTC算法的有效性。

為了證明上述論斷，分以下兩種情況進行證明：

（1）被刪除的邊（ni，nj）不屬于r1，r2，…，rk中的任何一條路徑：由于邊（ni，nj）的刪除并不影響路徑r1，r2，…，rk，因此節點nv與root節點仍然k點連通性。

（2）被刪除的邊（ni，nj）屬于r1，r2，…，rk中某一條路徑：不失一般性，假設被刪除的邊（ni，nj）屬于路徑rk，下面證明若k－1個節點被刪除后，nv與root節點間仍存在可達路徑。如果k－1個節點不是同時分別屬于路徑r1，r2，…，rk－1，則在r1，r2，…，rk－1路徑中至少存在一條路徑使nv與root節點可達，因此重點是證明被刪除的k－1個節點分別屬于路徑r1，r2，…，rk－1時，nv與root節點仍存一條路徑可達。由于被刪除的k－1個節點分別屬于路徑r1，r2，…，rk－1，則通過路徑rk節點nv與節點ni仍然相通，定義節點nv與ni之間路徑為r1k；同時節點nj與root節點也是相通的，定義節點nj與root之間路徑為；根據k-FTDTC算法，節點ni與nj是k連通的，即存在k路徑相通，因此即使刪除的k－1個節點屬于該k條相通路徑，但節點ni與nj仍存在至少一條路徑連通，假設為。路徑、、構成了節點nv與root間的一條連通路徑，即rk＝＋＋。根據k點相通定義，節點nv與root節點為k點連通。

上述證明從理論上保證了每個CN節點利用k-FTDTC算法進行發射功率優化分配后，G1仍是k點連通到root節點。

3 仿真分析

采用MATLAB對算法進行仿真，并與經典的分布式拓撲控制算法DATC進行比較，以驗證k-FTDTC算法的性能。DATC算法是分布式拓撲控制算法，該方法在每個節點位置已知的前提下，以最小化網絡總功耗為目標，對節點發射功率進行調整以保證網絡是k點連通的。由于DATC算法是通過構造有向圖進行拓撲控制，因此算法相對復雜；其次該方法要求所有節點知道自身位置信息，適用性受限；最后該方法并沒有對節點的最大發射功率進行有效約束，因此存在網絡能量均衡問題。

本文主要采用3項性能指標對上述兩種算法進行評價：①網絡總功耗，即網絡中每個CN節點發射功率之和；②最大發射功率，即經過拓撲控制后，所有節點中最大的發射功率，主要用來衡量網絡節點間能量均衡和網絡生命周期；③計算復雜度：HWSN進行拓撲控制，節點功率優化過程中，算法執行基本運算的數量。

3.1 仿真場景和參數設置

N節點隨機部署在500m×500m的方形平面區域內，SN節點在預先設置的位置上部署，相鄰節點間的通信滿足式（1）定義的無線信道模型，算法仿真重復次數為100。具體的參數定義如表3所示。

表3 實驗仿真參數

3.2 性能比較與分析

圖3為依次改變網絡中CN節點總數，當網絡容錯度k分別為2和4時，DATC算法和本文設計的k-FTDTC算法的網絡總功耗比較?？梢园l現k-FTDTC算法的網絡總功耗明顯小于經典的DATC算法，這是因為k-FTDTC算法不僅以最小化網絡總功耗為目標，還基于節點的有序鄰集對節點的最大發射功率進行有效約束，因此節點功率優化效果更好。當網絡容錯度k從2增加到4時，整個網絡總功耗也在增加，可見網絡容錯度的提高是以犧牲一定的網絡能量為代價的。然而當網絡容錯度為4時，增加傳感器節點數目，網絡總功耗反而少量降低，這是因為容錯度的提高意味著節點間鏈路的增加，對于鏈路密集的網絡，雖然傳感器節點數目的增加增大了網絡總功耗，但是由于節點間距離的縮短也降低了節點的發射功率。

圖3 網絡總功耗比較

圖4為DATC算法和本文設計的k-FTDTC算法的最大發射功率比較。可以發現基于節點有序鄰集的k-FTDTC算法能夠有效降低節點的最大發射功率，使節點間能量消耗更加均衡。并且，隨著網絡中傳感器節點數目的不斷增加，k-FTDTC算法對最大發射功率優化更為顯著，能夠有效延長大規模HWSN的網絡生命周期。

圖4 最大發射功率比較

圖5為DATC算法和本文設計的k-FTDTC算法的計算復雜度比較。可以發現，不同傳感器節點規模與不同容錯度下，k-FTDTC算法的計算復雜度明顯低于DATC算法。這是因為DATC算法是通過構造有向圖進行拓撲控制，而本文設計的k-FTDTC算法是基于無向簡化圖，有效降低了算法的復雜度，使k-FTDTC算法更適合在計算能力受限的CN節點上運行。

圖5 計算復雜度比較

5 結 論

在WSN中，除普通的CN節點外，通過有計劃地部署少量能量豐富、通信能力強的SN節點，組成轉發骨干網，可以有效增強網絡連通性、降低數據轉發延遲、提高網絡可擴展性?；谏鲜霎悩嫙o線傳感器網絡的容錯性拓撲控制是一類NP-難問題，本文基于構建的HWSN網絡模型提出了簡化網絡圖構建方法，將NP-難問題進行簡化，進行形式化描述。然后，通過構造節點的有序鄰集來約束其發射功率，在保證網絡k容錯性的基礎上最小化網絡總功耗，提出了一個k容錯性分布式拓撲控制算法。實驗結果表明，本文所提k-FTDTC算法，相比經典的DATC算法，網絡總功耗、節點的最大發射功率以及算法計算復雜度明顯降低，從而驗證了算法的有效性。

［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.（尹榮榮，劉彬，李雅倩，等.能量異構無線傳感器網絡容錯拓撲研究［J］.電子與信息學報，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－），男，工程師，博士，主要研究方向為WSN容錯性拓撲控制、節點定位、數據融合。

E-mail：liuxch06＠163.com

吳振鋒（1975－），男，研究員，博士，主要研究方向為傳感網集成應用技術。

E-mail：wuzhenf＠163.com

趙克儉（1964－），男，研究員，主要研究方向為傳感網／物聯網應用技術。

E-mail：zhaokej＠163.com

1001－506X201508－1902－07

網址：www.sys－ele.com

2014－09－09；

2014－10－30；網絡優先出版日期：2014－11－21。

網絡優先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20141121.0956.012.html

江蘇省青年科學基金（SBK2014042581）資助課題