無線傳感器/反應器網絡中反應節點優化重定位機制研究

無線傳感器/反應器網絡中反應節點優化重定位機制研究*

趙新元

(新疆師范大學網絡信息安全與輿情分析實驗室，新疆 烏魯木齊 830054)

摘要：針對無線傳感器/反應器網絡中因多個反應器失效而造成的反應器網絡連通性被破壞問題，以網絡流理論為基礎，提出了一個基于網絡流的多目標規劃模型來求解優化的反應器重定位方案。模型將反應器網絡看成是一個運輸網絡，通過流平衡條件來重建反應器網絡的連通性。最小化多個參與恢復的反應器總體開銷和最小化單個反應器的最大開銷是該模型的兩個優化目標。仿真實驗結果表明，基于該模型的優化重定位方案能夠有效地恢復因多反應器節點失效而造成的網絡連通性問題。

關鍵詞：多反應器失效;連通性恢復;網絡流；優化重定位開銷

中圖分類號：TP393 文獻標志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.011

收稿日期：*2014-04-08;修回日期：2014-08-14

作者簡介:

通信地址：830054 新疆烏魯木齊市新醫路104號新疆師范大學網絡信息安全與輿情分析實驗室

Address:Laboratory for Network Information Security and Public Opinion Analysis,Xinjiang Normal University,104 Xinyi Rd,Urumqi 830054,Xinjiang,P.R.China

Research on optimal actors’relocation in wireless sensor and actor networks

ZHAO Xin-yuan

(Laboratory for Network Information Security and Public Opinion Analysis,

Xinjiang Normal University,Urumqi 830054,China)

Abstract:The connectivity of actor networks is vital in the wireless sensor and actor networks (WSANs) due to the nature of the WSANs operation. Relocating actors is an effective solution to restore the connectivity when actors fail.The relocation solutions proposed in recent studies do not optimize the relocation distance. In this paper we present a network flow based multi-objects actor relocation model to handle multiple actors' failures. Minimizing the total overheads and the individual maximal overhead are the two optimal objectives.To restore the connectivity of the network, the model constructs a flow balancing condition for the actor network which can be treated as a transportation network.The simulation results demonstrate the effectiveness of the proposed model and show that the model outperforms other existing approaches in terms of optimal restoration overheads in handling multiple failures.

Key words:multiple actors failure;connectivity restoration;net flow;optimal relocation overheads

1引言

無線傳感器/反應器網絡WSANs(Wireless Sensor and Actor Networks)是無線傳輸器網絡WSNs(Wireless Sensor and Networks)的一個變種，其中部署了兩種重疊的網絡，一種是由可以移動的反應器(Actor)構成的反應器網絡，另一種就是由傳感器節點組成的傳感器網絡[1]。相對傳感器來說，反應器節點的資源受限程度較小，具有較大的能量、傳輸距離以及處理能力等等。反應器節點從傳感器節點收集數據，通過與WSANs中的其他反應器節點的相互協作來完成任務,這是WSANs網絡的一個重要特性[2]。因此，維護反應器網絡的連通性就變得尤為重要了。

反應器節點的失效會造成反應器網絡連通性的破壞。盡管單個反應器失效的概率要遠遠高于多個反應器節點，但研究多反應器同時失效也是非常有意義的。例如，在戰場環境中，一次爆炸可能會導致一個區域內多個反應器節點失效，或者是在安全應用方面，一次有敵意的攻擊可能會使WSANs網絡中多個反應器節點同時失效。通過重定位剩余的反應器節點來重建反應器網絡是一個可行的辦法。在這種情況下，主要考慮的是以盡可能小的重定位開銷來恢復網絡的連通性。

本文提出一個基于網絡流的多目標優化反應器重定位模型NAOM(Network flow-based multi-object Actor Relocation Model)來恢復反應器網絡的連通性。模型的第一個優化目標是最小化重定位過程中所有反應節點的總體開銷。一般來說，反應器節點移動能耗要遠大于其通信能耗，因此本文只考慮節點移動引起的開銷，即重定位距離(本文中開銷與重定位距離是同義語)。只優化總體開銷有可能導致單個反應節點的開銷過大，從而影響了反應節點的生存期，所以模型的第二個優化目標是最小化個體的最大開銷，即單個反應器節點的最大移動距離。本文以網絡流理論為基礎，首先將反應器網絡看成一個運輸網絡，然后利用流平衡條件來重建網絡的連通性。該問題被建模為一個二次混合整型數學規劃模型。

2相關研究

近年來已有很多文獻關注恢復因單點失效而造成的WSANs網絡中反應器網絡連通性被破壞的問題[3]。 Abbasi A A等人[4]針對WSANs網絡提出一種典型的基于關鍵點(即失效節點為反應器網絡拓撲中的割點)的分布式解決方案DARA。DARA利用2跳鄰居表和級聯移動機制有效地恢復了斷開的反應器網絡。Younis M等人[5]則針對WSNs網絡提出了另一種不依賴于關鍵點的典型的分布式算法RIM來修復斷裂的網絡。RIM的主要思想是讓失效節點的鄰居向著失效節點移動，直到它們之間建立連接為止，這個過程被遞歸應用到后續的節點移動中。與DARA算法相比，RIM產生的個體開銷要小于DARA，但其產生的總體開銷要遠遠大于DARA產生的總體開銷。文獻[6～10]分別從不同的方面對RIM和DARA算法進行了改進。但是，這些分布式算法均只能處理單一節點失效問題。

恢復因多節點失效而造成的網絡連通性問題要比單節點失效困難一些。劉林峰等人[11]提出了針對WSNs網絡中多傳感器節點失效時恢復WSNs網絡拓撲自愈算法。該算法在發現節點失效后通過調整一些未失效節點的功率來完成拓撲的自愈。Lee S等人[12～14]則利用Steiner樹來研究向WSNs網絡中部署最少的后備節點來重建網絡的連通性，這實際上是一個NP-難問題[15]。但是，由于反應器的代價比較大，因此利用在反應器網絡中部署冗余的反應器節點以防止節點故障不太適合于WSANs網絡。Akkaya K等人[16]針對WSANs中反應器網絡最早提出了偵測斷裂子網的分布式發現算法和子網融合算法。該方法利用WSANs網絡中的傳感器作為中繼節點，采用基于行-列廣播機制來偵測斷裂的反應器網絡，然后在子網中選出一個首領反應器節點，多個子網的首領反應器通過基于最小連接集的移動機制將斷開的反應器網絡融合在一起。Alfadhly A等人[17]則提出了一種基于樹的恢復機制來處理多節點失效時網絡的連通性問題。算法預先在網絡中構造一棵樹，當失效發生時，失效反應器的孩子節點通過彼此之間的協作來觸發重定位機制。Mi Zhen-qiang等人[18]則研究了移動Adhoc網絡中的多節點失效問題，介紹了一種基于K跳鄰居信息的分布式機制來恢復節點之間的連接性。但是，以上的分布式恢復機制僅關注于恢復網絡連通性而忽略了對恢復開銷的優化。

Alfadhly A等人[19]首先提出了基于關鍵點的集中式優化算法ILP。文獻[19]將節點重定位問題建模為一個整型線性規劃。該算法的目標是求解總體開銷最小的節點重定位方案。ILP算法通過將剩余的反應器重新部署在失效的關鍵節點的位置上來恢復網絡的連通性，因此該算法只能處理多個關鍵點失效的問題。

3處理多節點失效的NAOM模型

3.1簡介

在WSANs網絡中維護反應器網絡的連通性十分重要。反應器節點的失效有可能導致反應器網絡的連通性被破壞。在單一反應器節點失效的情況下，只有那些在網絡拓撲中位于關鍵位置上(即反應器網絡拓撲中的割點)的反應器失效才會導致網絡的連通性被破壞，本文將處于這種位置上的反應器節點簡稱為關鍵節點。然而，在多節點失效的情況下，多個非關鍵節點的失效也可以導致網絡連通性的破壞。如圖1a中的a8和a9兩個非關鍵節點的失效割裂了整個反應器網絡。文獻[19]提出的ILP方法無法處理這種情況。為了彌補文獻[19]所提出的ILP模型的缺點，本文根據網絡流理論提出了一個新的多目標優化模型，來處理網絡中因多反應器節點失效而造成的網絡連通性恢復問題。

3.2問題描述

本文所提出的問題可以形式化描述為：考慮平面上的一個連通圖，圖中的每條邊長度小于或等于一個預定義的值R。令集合L={li|i=1,2,…,NL}中的每個元素表示連圖圖中各個頂點的位置。現將反應器信合A={ai|i=1,2,…,NA}中的所有反應器節點放置在連通圖的NL個頂點上(NL≥NA)，并假設反應器之間的最大通信距離為R。則該問題實際上就是在位置集合L中重新定位這NA個反應器，使它們能夠以最小的總體開銷和最小的個體最大開銷來建立一個互連的反應器網絡。很明顯，這個問題是一個典型的多目標優化問題。

3.3基于網絡流的優化模型

針對3.2節中提出的問題，可以將連通圖看成是一個運輸網絡，該運輸網絡中每個位置都是一個運輸站(在以下的描述中，站點與位置是同義語)。假定該運輸網絡可以從一個運輸站向另一個運輸站運輸貨物。有如下規定：(1)若運輸站擁有反應器節點(即反應器位于該運輸站)，則該站能夠接收或發出貨物；(2)反之，則該站既不能接收貨物也不能發送貨物。

Figure 1　Overview of NAOM 圖1　NAOM模型的基本思想

在這個運輸網絡中，任意選擇一個位置作為源站點，由該站點向運輸網絡中的所有其他站點均發送一個單位的貨物。擁有反應器的站點收到不是給自己的貨物后必須要轉運該貨物。最終，若反應器所構成的網絡是連通的，則每個擁有反應器的站點必然會收到一個源站點發給自己的貨物，否則就表明反應器網絡一定不是連通的。圖1展示了模型的基本思想。

定義如下描述：

(1)L是平面上包含NL個位置的集合。

(2)A是包含Na個反應器的節點集合，集合中的每個反應器均位于集合L中的某些位置上。

(3)dij表示L中位置i和j之間的距離。

(4)Adij是一個二元值，表示兩個位置i、j是否是相鄰的。當dij≤R時，Adij=1,其中R是反應器節點之間的最大通信距離。

(5)Xiu是二元值，為1表示反應器u占據位置i。

(6)Oi是二元值，為1表示位置i被一個反應器所占據。

(7)fij表示由站點i發送給站點j的貨物的數量。則在集合L中優化重定位集合A中節點可以寫成如下的數學規劃：

問題：在NL個位置中優化重定位NA個反應器。

已知：L，A,dij,Adij；

求：Xiu,fij,Oi。

(1)

(2)

使得：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

該模型是一個混合整型的二次規劃。目標函數(1)和(2)最小化總的重定位距離和最小化單個最大重定位距離。限制條件(3)確保了反應器u必須要重定位到集合L中的一個位置上去，而限制條件(4)則確保L中的任何一個位置i只能夠被至多一個反應器所占據。公式(5)表明位置i是否被一個反應器所占據。限制條件(6)則保證源站點s發出的貨物總數為NL-1個。等式(7)是一個網絡流平衡限制條件，它保證流向站點位置i的總貨物量等于1(源站s送至位置i的貨物)加上站點i轉運的貨物數量。該式同時表明，站點j如果擁有反應器則會至少收到一個貨物(即Oj=1)。流平衡條件能夠保證反應器節點在重定位之后整個反應器網絡是連通的。限制條件(8)則限制了站點i向站點j運送的最大貨物運輸量。根據前面的假定，未擁有反應器節點的運輸站既不能接收貨物也不能轉運貨物，因此若位置i或j未被反應器占據，則有fij=0。限制條件(9)表示貨物總數量fij為正值。

一般來說，最小化總體開銷和最小化個體的最大開銷是一對矛盾的優化目標。為了求解這個多目標優化問題，重定義如下優化函數：

(10)

其中α(α∈[0,1])在模型中是一個針對總重定位距離的優化權重值，它表示求解模型時優先考慮優化總體開銷的程度。α=0表示該模型在求解時只考慮優化個體的最大開銷。在這種情況下，單個反應器節點的開銷是最小的，但有可能導致總體開銷最大。權重值α=1則表示模型在求解時只考慮優化總體開銷而不考慮優化個體開銷，因而導致單個反應器節點要花費更多的能量來進行重定位。圖1b是圖1a中節點a2、a3、a8及a9失效后的一種可行解(可能不是優化解)。

4仿真實驗及評價

4.1仿真實驗設置及評價參數

為了能夠評價優化求解模型NAOM，本文采用AMPL語言[20]來描述該模型并通過IBM LOG CMPLEX 12.04[21]工具箱進行求解。仿真實驗中的反應器網絡拓撲是在1 000*1 000 m2的范圍內隨機生成，反應器節點的數目在20到100之間。反應器之間的最大通信半徑設置為50 m。仿真實驗在不同的網絡拓撲中重復30次，最終的優化結果取這30次的平均值。下面為評價模型性能的主要指標：

(1)總體開銷TO。該值可以用來描述所有反應器節點在重定位過程中的總體開銷，即總體重定位距離。TO可以用來評價整個網絡在恢復過程中的能耗情況。最小化TO是模型NAOM的優化目標之一。

(2)個體最大開銷MIO和平均開銷SIO。MIO越大就意味著個體的能耗越大，因此最小化該值是模型NAOM的另一個優化目標。除了個體最大開銷MIO以外，反應器節點的平均開銷(平均重定位距離)SIO也可以粗略地評價節點在恢復過程中的個體能耗。在某種程度上它反映了節點的平均性能。

(3)參與重定位反應器節點總數TNA。可以用該值來粗略地評價總體恢復開銷在反應器節點上的分布性以及評價網絡中受影響的范圍。一般來說，TNA越大，網絡中受影響的區域就越大。

4.2比對協議及設置

在仿真實驗中將NAOM模型、ILP模型[19]和一個典型的分布式算法DARA[6]作對比來綜合評價NAOM模型的性能。如表1所示，根據這三個協議各自的適應范圍共設置了三個對比實驗。實驗1用來評價在單點故障的情況下NAOM、ILP和DARA的性能。在30個不同的網絡拓撲中，網絡中的所有關鍵節點輪流充當失效節點，仿真結果取它們的平均值。實驗2用來評價在多關鍵點故障情況下NAOM與ILP的性能(因為ILP只能處理多個關鍵節點失效的情況)。實驗3則通過對比在不同的優化權值α下NAOM的性能，α表示在求解NAOM問題(10)時優先考慮優化TO的程度。α=0和α=1分別表示求解NAOM問題時只優化總體開銷TO和個體最大開銷MIO。實驗3隨機選擇30%的反應器節點同時失效。為了評價NAOM模型在非關鍵節點失效時的性能，實驗3要求隨機選擇的失效節點中至少要包含多個非關鍵節點，同時這些非關鍵節點的失效必須造成反應器網絡的斷裂。

Table 1　Scenarios for simulation experiments

4.3實驗結果

4.3.1單關鍵點失效

圖2展示了實驗1的仿真結果。為了描述上簡單起見，本文用NAOMα來表明求解NAOM模型時采用的α值。在仿真中，NAOM1.0、NAOM0.0和NAOM0.5分別表示只優化TO、MIO以及均衡優化TO和MIO。從直覺上來說，分布式算法的DARA似乎應該比優化算法ILP和NAOM消耗更多的總開銷TO。圖2a表示，DARA消耗的TO大于ILP、NAOM0.5和NAOM1.0的TO(圖2中ILP、NAOM0.5,1.0的TO曲線是重合的)，但卻遠小于NAOM0.0的。由于NAOM0.0僅優化求解MIO，因此在該優化方案下會使更多的反應器參與了，移動從而導致了較大的TO，如圖2a和圖3所示。同時，從NAOM1.0和ILP的TO仿真結果上可以看出二者基本上是相等的，這是因為二者在求解時均只優化TO。從求解NAOM時的優化權值上來說，NAOM0.5似乎應該比NAOM1.0要產生更多的TO，這是因為NAOM0.5在求解時要同時考慮均衡的優化TO和MIO而NAOM1.0只優化TO。然而仿真結果表明NAOM0.5和NAOM1.0的總開銷TO基本上是一致的。主要原因在于實驗1中只有一個反應器失效并且剩余的反應器只在一些固定的位置上進行重定位。另外，從圖2a也可以看到，除了NAOM0.0，算法ILP和算法NAOM要比DARA在總開銷TO方面提升大約15%的性能。

Figure 2　Simulation results for single actor failures(Scenario 1) 圖2　實驗1的仿真結果

圖2b展示了單個反應器的開銷情況。正如預料的一樣，只優化TO的ILP和NAOM1.0的優化重定位方案使得單個反應器的最大開銷MIO和平均開銷SIO均比較大。與之相反，NAOM0.0獲得了最好的個體性能，但卻導致了更多的反應器參與了重定位(如圖3a所示)。由于采用級聯移動機制，DARA所帶來的MIO總是小于節點通信半徑。從圖中也可以看到NAOM0.5在MIO和SIO方面與DARA基本上是一致的。綜合考慮總體開銷和個體開銷，有理由認為NAOM0.0的部署方案的性能是最差的，盡管該方案下個體的開銷最小(比其他的低大約10%)，但卻比其它方案消耗了約2～3倍的總體開銷。DARA和NAOM0.5比其他方案的性能要好一些。由于DARA是分布式算法而NAOM是集中式算法，因此可以認為DARA的總體性能要優于NAOM0.5，盡管DARA的總體開銷要比后者高大約15%。總的來說，實驗1的仿真結果表明，在處理單關鍵點故障方面， DARA的總體性能要優于ILP和NAOM。

Figure 3　Number of relocated actors in scenario 1 and 2 圖3　實驗1和實驗2中參與重定位的節點數

4.3.2多關鍵點失效

實驗2的仿真結果如圖3b和圖4所示。圖4a表明，隨著反應器節點數的增大，ILP和NAOM的總體開銷均有所增大。特別是NAOM0.0，由于它僅優化個體開銷MIO，因此當節點數比較多時導致的總體開銷TO將非常大。這就表明采用NAOM0.0的優化方案會使更多的反應器參與重定位，從圖5中可以看到大約有40%～50%的節點均參與了重定位。從圖4中還可以看到，盡管ILP和NAOM1.0均是只優化TO，但ILP的總開銷TO要大于NAOM1.0的。這主要是因為ILP模型只是通過將剩余的反應器重定位到已失效的關鍵節點位置上來恢復網絡的連通性，而NAOM則利用網絡流理論來恢復連通性，在這種情況下并不是所有的失效節點的位置都要被剩余的反應器來占據。如圖1a，位置7是運輸網絡中的關鍵位置，當節點a7、a8和a9失效后網絡被分裂了。將a10重定位到位置8是NAOM模型的一個可行解，盡管在原來的關鍵位置7上沒有反應器。因而NAOM1.0的總開銷TO要小于ILP的。

Figure 4　Simulation results for multiple cut-vertices failure(Scenario 2) 圖4　實驗2的仿真結果

Figure 5　Simulation resubts for multiple actors failure(Scenario 3) 圖5　實驗3的仿真結果

圖4b則展示了模型ILP和NAOM中單個反應器的最大開銷MIO和平均開銷SIO。正如期望的一樣，NAOM0.0的個體性能最優。從圖4b中可以看到，ILP和NAOM1.0的最大個體開銷MIO基本是一致的，但模型ILP的個體平均開銷SIO要小于NAOM1.0的。這種差異是由兩種模型ILP和NAOM在重建網絡連通性時所采用的不同機制引起的。相對NOAM模型來說，ILP模型使更多的節點參與到重定位過程中(如圖5所示)，因此它的SIO要較NAOM1.0的小一些。同時，從圖4b中也可以觀察到NAOM0.5和NAOM0.0的個體平均開銷SIO幾乎一樣，而且前者的MIO也只比后者的高約13%左右。這說明從個體開銷性能上來說，NAOM0.5與NAOM0.0基本是相同的。綜合考慮總體性能和個體性能，可以認為在處理多關鍵節點失效問題方面，NAOM0.5的優化方案要優于ILP和其它的NAOMα(α≠0.5)的優化方案。

4.3.3任意多點失效

圖5展示了實驗3的仿真結果。實驗3仿真了在不同的優化權值α(α=0,0.2,0.5,0.7和1.0)下NAOM模型的優化重定位方案。與實驗2類似，NAOM0.0的總體開銷TO隨著節點數N的增大呈急劇上升的趨勢。從圖5中也可以看到，當權值α≥0.2時，NAOM所產生的優化重定位方案的總體性能幾乎是相等的。這就說明，在求解NAOM模型時僅優化個體開銷時如果能夠稍微考慮優化一點總體開銷，會使優化方案的總體開銷大大降低，同時也不會產生太大的個體開銷。圖5b表明，隨著α的增大，NAOM的最大個體開銷MIO逐漸趨向于最優值。一般來說，NAOM模型提升個體性能是以犧牲總體性能為代價的。從圖5b的仿真結果中可以看到，這些不同α值的NAOM分布方案所產生的MIO最大的差值大約是40 m，而平均開銷SIO僅為13 m。這就表明，在求解NAOM模型時僅僅考慮優化個體開銷是不可取得，因為它只提升了個體性能大約20%，但卻降低了大約300%的總體開銷性能。

在仿真實驗中，本文也研究了對不同α值來求解NAOM模型所需要的時間。圖6展示了α與求解時間的仿真結果。從圖6中可以觀察到求解時間t反比于優化權值α。也就是說，α越大，求解所需要的時間就越多，這說明求解優化個體開銷MIO所需要的時間要大于求解優化總體開銷TO。同時，從圖6中也發現，求解時間t并不是隨著α的增大而均勻下降，這里存在著一個拐點α=0.5。當α≥0.5時，求解時間t與其最小值(即NAOM1.0時的求解時間)的差距變化就逐漸減小了。綜合以上三個實驗的仿真結果，對于多節點失效問題的處理上可以認為，NAOM0.5所產生的優化重定位方案無論在總體性能還是個體性能方面都要比ILP和其它權值的NAOM方案要好。

Figure 6　Elapsed time for solving NAOM 圖6　求解NAOM的時間

5結束語

本文針對WSANs網絡中因多個反應器節點失效而造成的反應器網絡連通性斷裂的問題提出了一個多目標優化模型來恢復其連通性。通用引入網絡流理論將該問題建模為一個二次混合整型線性規劃問題NAOM。所提出的模型同時考慮優化總體開銷和優化個體的最大開銷。仿真結果表明，在處理單關鍵節點失效問題方面，ILP和NAOM模型的性能與分布式算法DARA的性能基本上是相同的，這就說明在這種情況下用DARA算法來處理單節點失效問題要更好一些。在處理多節點失效問題方面，仿真結果表明僅考慮優化個體開銷是一個不明智的選擇，因為這會導致總體性能的急劇下降，同時也消耗了更多的模型求解時間。從仿真結果看，對本文提出的模型NAOM來說，均衡地考慮優化總體開銷和優化最大個體開銷是一個比較理想的選擇(NAOM0.5)。同時，NAOM0.5無論是總體性能還是個體性能均要優于ILP模型。NAOM模型的優化求解值也可以作為其他分布式算法的一個評價標準。本文下一步的工作是研究分布算法來處理多反應器失效時反應器網絡的連通性問題。

參考文獻:

[1]Zhao Wen-dong,Peng Lai-xian,Tian Chang.Survey of coordination mechanisms in wireless sensor and actor network[J]. Journal of Computer Applications,2009,29(8):2183-2187.(in Chinese)

[2]Yang Jie,Feng Yong. Survey on cooperative communication research in wireless sensor and actuator networks[J]. Application Research of Computers,2014,31(3),645-650.(in Chinese)

[3]Kashi S,Sharifi M. Connectivity weakness impacts on coordination in wireless sensor and actor networks[J].IEEE Communications Surveys & Tutorials,2013,2(1):145-166.

[4]Abbasi A A,Younis M,Akkaya K. Movement-assisted connectivity restoration in wireless sensor and actor networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(9):1366-1379.

[5]Younis M,Sookyoung L,Abbasi A A.A localized algorithm for restoring internode connectivity in networks of moveable sensors[J].IEEE Transactions on Computers,2010,59(12):1669-1682.

[6]Zhao Xin-yuan,Wang Neng. Overlap-based connectivity restoration approach for wireless sensor and actor network[J]. Journal of Computer Applications,2011,31(10):2638-2643.(in Chinese)

[7]Zhao Xin-yuan,Wang Neng.Coordination-assisted connectivity recovery approach in WSANs[C]//Proc of the 3rd International Conference on Computer Research and Development (ICCRD),2011:82-86.

[8]Imran M,Younis M,Md Said A,et al. Localized motion based connectivity restoration algorithms for wireless sensor and actor networks[J].Journal of Network and Computer Applications,2012,35(2):844-856.

[9]Noman H,Muhammad I.Resource efficient connectivity restoration algorithm for mobile sensoractor networks[J].EURASIP Journal on Wireless Communications and Networking,2012,347(1):1-16.

[10]Abbasi A A,Baroudi U,Younis M,et al.C2am:An algorithm for application-aware movement-assisted recovery in wireless sensor and actor networks[C]//Proc of the 2009 International Conference on Wireless Communications and Mobile Computing:Connecting the World Wirelessly(ACM),2009:655-659.

[11]Liu Lin-feng,Wu Jia-gao,Zou Zhi-qiang,et al. Topology self-cure algorithm aiming at node failure problem in wireless sensor networks[J]. Journal of Southeast University(Natural Science Edition),2009，39(4):695-699.(in Chinese)

[12]Lee S,Younis M. Optimized relay node placement for connecting disjoint wireless sensor networks[J].Computer Networks,2012,56(12):2788-2803.

[13]Lee S,Younis M.Recovery from multiple simultaneous failures in wireless sensor networks using minimum steiner tree[J].Journal of Parallel and Distributed Computing,2010,70(5):525-536.

[14]Lee S,Younis M.Optimized relay placement to federate segments in wireless sensor networks[J].IEEE Journal on Selected Areas in Communications,2010,28(5):742-752.

[15]Lin Guo-hui,Xue Guo-liang.Steiner tree problem with minimum number of steiner points and bounded edge-length[J].Information Processing Letters,1999,69(2):53-57.

[16]Akkaya K,Senel F. Detecting and connecting disjoint sub-networks in wireless sensor and actor networks[J].Ad Hoc Networks,2009,7(7):1330-1346.

[17]Alfadhly A,Baroudi U,Younis M. An effective approach for tolerating simultaneous failures in wireless sensor and actor networks[C]//Proc of the 1st ACM International Workshop on Mission-Oriented Wireless Sensor Networking,2012:21-26.

[18]Mi Zhen-qiang,Yang Yang.Connectivity restorability of mobile ad hoc sensor network based on k-hop neighbor information[C]//Proc of 2011 IEEE International Conference on Communications (ICC),2011:1-5.

[19]Alfadhly A,Baroudi U,Younis M.Optimal node repositioning for tolerating node failure in wireless sensor actor network[C]//Proc of 2010 25th Biennial Symposium on Communications (QBSC),2010:67-71.

[20]Gay D M.Hooking your solver to AMPL[Z].Murray Hill:Computing Science Research Center Bell Laboratories,1997.

[21]Gay D M.IBM ILOG CPLEX optimization studio CPLEX user’s manual:Version 12.4[Z].New York:IBM,1987.

參考文獻附中文.

[1]趙文棟，彭來獻，田暢.無線傳感器執行網絡的協調機制綜述[J]. 計算機應用， 2009，29(8):2183-2187.

[2]楊杰，馮勇.無線傳感器與執行器網絡中協同通信研究綜述[J]. 計算機應用研究，2014,31(3):645-650.

[6]趙新元，王能.基于重疊區域的無線傳感反應網絡連接性恢復機制[J]. 計算機應用，2011,31(10):2638-2643.

[11]劉林峰，吳家臬,鄒志強，等.面向節點失效問題的無線傳感器網絡拓撲自愈算法[J].東南大學學報(自然科學版)，2009，39(4):695-699.

趙新元(1974-),男,陜西眉縣人，碩士，講師，研究方向為無線傳感器網絡。E-mail:Zxy4095e1@163.com

ZHAO Xin-yuan,born in 1974,MS,lecturer,his research interest includes wireless sensor networks.