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

趙新元

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

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

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

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

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

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

作者簡介:

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

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

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

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

2相關(guān)研究

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

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

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

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

3.1簡介

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

3.2問題描述

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

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

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

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

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

定義如下描述：

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

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

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

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

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

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

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

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

已知：L，A,dij,Adij；

求：Xiu,fij,Oi。

(1)

(2)

使得：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

(10)

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

4仿真實(shí)驗(yàn)及評價(jià)

4.1仿真實(shí)驗(yàn)設(shè)置及評價(jià)參數(shù)

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

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

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

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

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

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

Table 1　Scenarios for simulation experiments

4.3實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

4.3.3任意多點(diǎn)失效

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

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

Figure 6　Elapsed time for solving NAOM 圖6　求解NAOM的時(shí)間

5結(jié)束語

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

參考文獻(xiàn):

[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.

參考文獻(xiàn)附中文.

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

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

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

[11]劉林峰，吳家臬,鄒志強(qiáng)，等.面向節(jié)點(diǎn)失效問題的無線傳感器網(wǎng)絡(luò)拓?fù)渥杂惴╗J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，39(4):695-699.

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

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