無線傳感器/反應(yīng)器網(wǎng)絡(luò)中反應(yīng)節(jié)點優(yōu)化重定位機制研究*

趙新元

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

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

關(guān)鍵詞：多反應(yīng)器失效;連通性恢復(fù);網(wǎng)絡(luò)流；優(yōu)化重定位開銷

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

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

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

作者簡介:

通信地址：830054 新疆烏魯木齊市新醫(yī)路104號新疆師范大學網(wǎng)絡(luò)信息安全與輿情分析實驗室

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引言

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

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

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

2相關(guān)研究

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

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

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

3處理多節(jié)點失效的NAOM模型

3.1簡介

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

3.2問題描述

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

3.3基于網(wǎng)絡(luò)流的優(yōu)化模型

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

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

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

定義如下描述：

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

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

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

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

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

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

(7)fij表示由站點i發(fā)送給站點j的貨物的數(shù)量。則在集合L中優(yōu)化重定位集合A中節(jié)點可以寫成如下的數(shù)學規(guī)劃：

問題：在NL個位置中優(yōu)化重定位NA個反應(yīng)器。

已知：L，A,dij,Adij；

求：Xiu,fij,Oi。

(1)

(2)

使得：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

(10)

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

4仿真實驗及評價

4.1仿真實驗設(shè)置及評價參數(shù)

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

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

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

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

4.2比對協(xié)議及設(shè)置

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

Table 1　Scenarios for simulation experiments

4.3實驗結(jié)果

4.3.1單關(guān)鍵點失效

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

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

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

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

4.3.2多關(guān)鍵點失效

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

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

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

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

4.3.3任意多點失效

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

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

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

5結(jié)束語

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

參考文獻:

[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]趙文棟，彭來獻，田暢.無線傳感器執(zhí)行網(wǎng)絡(luò)的協(xié)調(diào)機制綜述[J]. 計算機應(yīng)用， 2009，29(8):2183-2187.

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

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

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

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

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