基于滿Steiner樹(shù)問(wèn)題的水下無(wú)線傳感器網(wǎng)絡(luò)拓?fù)溆纤惴ㄑ芯?/h1>
2010-08-06 13:15:28劉林峰劉業(yè)
通信學(xué)報(bào) 2010年9期
劉林峰，劉業(yè)
（1. 南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.中國(guó)科學(xué)技術(shù)大學(xué) 蘇州研究院，江蘇 蘇州 215123）
1 引言
地球表面71%被人跡罕至的水域（海洋、湖泊、河流）覆蓋，出于科學(xué)探索、資源開(kāi)采、污染監(jiān)控、戰(zhàn)術(shù)監(jiān)視或海岸線保護(hù)等種種目的，人類(lèi)對(duì)監(jiān)測(cè)這些水域一直有著極大的興趣。在無(wú)線傳感器網(wǎng)絡(luò)[1～3]（WSN, wireless sensor network）被應(yīng)用之前，水下數(shù)據(jù)的感知和收集工作一般通過(guò)有線網(wǎng)絡(luò)來(lái)完成，這種方式代價(jià)高昂并且需要大量工程技術(shù)輔助。適合水下環(huán)境的大量傳感器節(jié)點(diǎn)協(xié)同工作，它們隨機(jī)分布于監(jiān)測(cè)水域，并通過(guò)基于聲通信的無(wú)線方式自組織構(gòu)成水下無(wú)線傳感器網(wǎng)絡(luò)[4～6]（UWSN, underwater wireless sensor network），不僅部署代價(jià)相對(duì)低廉，而且其分布式結(jié)構(gòu)能夠在水下監(jiān)測(cè)應(yīng)用中展現(xiàn)出更高的靈活度。然而，水下傳感器網(wǎng)絡(luò)的設(shè)計(jì)也面臨著多方面的約束和挑戰(zhàn)，主要表現(xiàn)在鏈接時(shí)延明顯且多變、節(jié)點(diǎn)能量有限、帶寬較低、誤碼率高等。此外，水下傳感器節(jié)點(diǎn)極易受到各類(lèi)外力（如海浪和海風(fēng)擾動(dòng)、水下生物觸動(dòng)等）影響發(fā)生位置遷移，甚至可能因此遭受毀壞，從而導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓l繁、局部網(wǎng)絡(luò)失效概率增高，如何愈合局部失效拓?fù)湟殉蔀樵擃I(lǐng)域的研究熱點(diǎn)之一。
部署于水域場(chǎng)景的水下傳感器網(wǎng)絡(luò)中應(yīng)有4種節(jié)點(diǎn)類(lèi)型：底面節(jié)點(diǎn)、浮游節(jié)點(diǎn)、自移動(dòng)節(jié)點(diǎn)（AUV,autonomous underwater vehicle）[7]和匯聚節(jié)點(diǎn)，其中底面節(jié)點(diǎn)鋪設(shè)于水域底面，由于水域底面地形異常復(fù)雜，可能會(huì)遭遇障礙地勢(shì)而形成通信孤島，該類(lèi)節(jié)點(diǎn)受水域底面摩擦力影響所以位置遷移幅度較小，浮游節(jié)點(diǎn)依靠浮力裝置懸浮在水中（懸浮深度與水域鹽度、浮力裝置屬性相關(guān)），該類(lèi)節(jié)點(diǎn)受外力擾動(dòng)而位移的幅度較大，但發(fā)生位移待穩(wěn)定后仍將處于相同懸浮深度的橫切平面上，自移動(dòng)節(jié)點(diǎn)具備自主的移動(dòng)能力，能夠按照某種策略進(jìn)行位移，承擔(dān)改善網(wǎng)絡(luò)結(jié)構(gòu)和自愈失效拓?fù)涞闹匾饔谩?/p>
在傳統(tǒng)WSN中，由于一般不考慮自移動(dòng)節(jié)點(diǎn)的存在，故通常采用調(diào)大節(jié)點(diǎn)功率的方式來(lái)愈合失效拓?fù)?，該方式無(wú)法改變?nèi)魏喂?jié)點(diǎn)的位置，因此愈合過(guò)程很難改善拓?fù)湫再|(zhì)，并極有可能造成拓?fù)湫再|(zhì)惡化。水下傳感器網(wǎng)絡(luò)中的AUV節(jié)點(diǎn)具備移動(dòng)能力，能夠按照特定策略遷移至指定位置替代失效節(jié)點(diǎn)并承擔(dān)其原角色，由該類(lèi)節(jié)點(diǎn)進(jìn)行的拓?fù)溆喜粌H能夠使得全局拓?fù)浠謴?fù)連通性，還能通過(guò)改變節(jié)點(diǎn)原有位置的方式來(lái)改善全局拓?fù)洌瑥亩哂懈叩膶?shí)用性。目前關(guān)于水下傳感器網(wǎng)絡(luò)的拓?fù)溆涎芯枯^為薄弱，多側(cè)重于AUV節(jié)點(diǎn)設(shè)計(jì)或節(jié)點(diǎn)協(xié)作策略的研究，如文獻(xiàn)[8]設(shè)計(jì)的Odyssey-class AUV能夠到達(dá)水域的任意深度，可以修復(fù)失效的局部拓?fù)?；文獻(xiàn)[9]提出了一種節(jié)點(diǎn)間協(xié)作控制的網(wǎng)絡(luò)管理模式，增強(qiáng)了網(wǎng)絡(luò)的健壯性和自適應(yīng)程度，能夠有效地應(yīng)對(duì)節(jié)點(diǎn)失效情況。然而，AUV節(jié)點(diǎn)遷移至何處才能達(dá)到拓?fù)溆虾屯負(fù)鋬?yōu)化的雙重目標(biāo)，該問(wèn)題尚未見(jiàn)深入研究，尤其對(duì)于時(shí)延較大的水下環(huán)境，AUV節(jié)點(diǎn)遷移策略的研究將有助于全局拓?fù)鋬?yōu)化、網(wǎng)絡(luò)傳輸時(shí)延降低、能耗效率的提升，因此研究該問(wèn)題很有必要。本文將針對(duì)時(shí)延敏感類(lèi)水下應(yīng)用（如水域戰(zhàn)術(shù)監(jiān)視、污染監(jiān)控等），采用 AUV節(jié)點(diǎn)遷移修復(fù)拓?fù)涞牟呗?，提出一種能夠降低傳輸時(shí)延和提高能耗效率的拓?fù)溆纤惴ā?/p>
2 網(wǎng)絡(luò)模型及問(wèn)題描述
2.1 模型構(gòu)建
在實(shí)際應(yīng)用場(chǎng)景中浮游節(jié)點(diǎn)和底面節(jié)點(diǎn)一般都扮演數(shù)據(jù)感知、采集和傳輸?shù)慕巧虼吮疚膶⒃?種節(jié)點(diǎn)歸為水下傳感器節(jié)點(diǎn)。假定有S個(gè)匯聚節(jié)點(diǎn)、N個(gè)水下傳感器節(jié)點(diǎn)和M個(gè)自移動(dòng)節(jié)點(diǎn)隨機(jī)均勻散布于監(jiān)測(cè)水域，其中水下傳感器節(jié)點(diǎn)攜帶有限能量的電池。水下傳感器節(jié)點(diǎn)能夠感知并發(fā)送監(jiān)測(cè)所得數(shù)據(jù)，同時(shí)根據(jù)網(wǎng)絡(luò)拓?fù)錇楫?dāng)前傳輸轄域內(nèi)的鄰居節(jié)點(diǎn)提供報(bào)文接收和轉(zhuǎn)發(fā)服務(wù)，隨著數(shù)據(jù)流量的經(jīng)由，節(jié)點(diǎn)的無(wú)線收發(fā)能耗和通信模塊的閑時(shí)開(kāi)銷(xiāo)使得電池能量不斷降低。初始工作狀態(tài)時(shí)水下傳感器網(wǎng)絡(luò)由水下傳感器節(jié)點(diǎn)保持全局連通，隨后節(jié)點(diǎn)可能由于能量耗盡、外力作用等復(fù)雜因素而導(dǎo)致失效，就需要自移動(dòng)節(jié)點(diǎn)來(lái)愈合拓?fù)洹?/p>
抽象水下傳感器網(wǎng)絡(luò)拓?fù)錇橐粋€(gè)權(quán)重圖G(V,E)，其中 V、E分別表示節(jié)點(diǎn)、鏈接的集合，V={n0, …, nS-1, nS, …, nS+N-1, nS+N, …, nS+N+M-1}，n0, …, nS-1表示匯聚節(jié)點(diǎn)，nS, …, nS+N-1表示N個(gè)水下傳感器節(jié)點(diǎn)，nS+N, …, nS+N+M-1表示M個(gè)自移動(dòng)節(jié)點(diǎn)；標(biāo)記節(jié)點(diǎn) ni的鄰居集合為 Neighbor(ni)，數(shù)量為N(ni)；失效節(jié)點(diǎn)記作nf，替代該節(jié)點(diǎn)的自移動(dòng)節(jié)點(diǎn)記作nAUV；對(duì)于任意i∈[S, S+N+M-1]，節(jié)點(diǎn)ni的當(dāng)前能量記作e(ni)，節(jié)點(diǎn)ni的當(dāng)前覆蓋半徑記作radius(ni)，所有節(jié)點(diǎn)擁有相同的最大傳輸范圍R；節(jié)點(diǎn)ni的最大覆蓋區(qū)域可以表示為cover(ni)={ nj| d(i,j)≤R and nj∈IR2}；定義網(wǎng)絡(luò)連通函數(shù)connectivity(G)∶ G(V,E)→X，X為布爾邏輯數(shù)集合。若節(jié)點(diǎn)ni和nj之間存在通信鏈接則記作(i,j)∈E，鏈接(i,j)的距離記作 d(i,j)，其上時(shí)延記作 delay(i,j)，delay(i,j)[10]表示為式（1）所示形式。
其中，L表示數(shù)據(jù)分組大小，B表示數(shù)據(jù)傳輸率，Vp為水下聲波傳輸速率。鏈接(i,j)上的能耗記作cost(i,j)如式（2）所示。
其中，ω為常系數(shù)，α為能量衰減指數(shù)，當(dāng)在惡劣通信環(huán)境中或有障礙物時(shí)較大，據(jù)實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)一般有α≥2。為便于模型的分析和描述，本文還給出如下假設(shè)：
假設(shè) 1 傳感器節(jié)點(diǎn)的天線以全方位廣播方式進(jìn)行通信，且通信鏈接具有對(duì)稱性；
假設(shè) 2 水下傳感器網(wǎng)絡(luò)的部署獲得定位系統(tǒng)（如GPS）的輔助, 每個(gè)節(jié)點(diǎn)均獲知自己及其鄰居的地理位置；
假設(shè) 3 匯聚節(jié)點(diǎn)能量為+∞，自移動(dòng)節(jié)點(diǎn)因位置移動(dòng)發(fā)生的能耗忽略不計(jì)；
假設(shè) 4 節(jié)點(diǎn)發(fā)生失效前水下傳感器網(wǎng)絡(luò)拓?fù)湟呀?jīng)為近似最優(yōu)結(jié)構(gòu)；
假設(shè)5 M＜＜N，因代價(jià)較高所以水下傳感器網(wǎng)絡(luò)中可供部署的自移動(dòng)節(jié)點(diǎn)數(shù)量一般認(rèn)為很少；
假設(shè)6 水下傳感器網(wǎng)絡(luò)的生命期[11]定義為在傳感器網(wǎng)絡(luò)系統(tǒng)的流量路由過(guò)程中，最先因電池能量耗盡而失效的節(jié)點(diǎn)生命期。
2.2 問(wèn)題描述
當(dāng)有節(jié)點(diǎn)發(fā)生失效后，拓?fù)浣Y(jié)構(gòu)可能不再滿足全局連通性，此時(shí)應(yīng)由自移動(dòng)節(jié)點(diǎn)替代已失效的節(jié)點(diǎn)，與失效節(jié)點(diǎn)的單跳鄰居連接，從而實(shí)現(xiàn)拓?fù)涞闹匦掠?。水下傳感器網(wǎng)絡(luò)拓?fù)淇刂浦袝r(shí)延和能耗是2個(gè)應(yīng)予以首要關(guān)注的因素，因此當(dāng)AUV節(jié)點(diǎn)愈合拓?fù)鋾r(shí)也必須考慮這2個(gè)因素。就該問(wèn)題而言，扮演替代角色的自移動(dòng)節(jié)點(diǎn)的位置選取至關(guān)重要，自移動(dòng)節(jié)點(diǎn)的遷移行為不僅能夠恢復(fù)受損拓?fù)?，更能改善受損拓?fù)涞臅r(shí)延和能耗特性，故不應(yīng)簡(jiǎn)單地讓AUV節(jié)點(diǎn)遷移至失效節(jié)點(diǎn)位置，而應(yīng)重新權(quán)衡并選取更為合適的位置，因此水下傳感器網(wǎng)絡(luò)拓?fù)溆蠁?wèn)題可歸結(jié)為最優(yōu)化網(wǎng)絡(luò)拓?fù)涞腁UV節(jié)點(diǎn)位置選取問(wèn)題。然而最優(yōu)化全局拓?fù)湫枰W(wǎng)絡(luò)尺度上的拓?fù)湫畔⒔换?，這對(duì)于水下傳感器網(wǎng)絡(luò)而言是難以承受和異常復(fù)雜的。因水下傳感器網(wǎng)絡(luò)屬于一種自組織網(wǎng)絡(luò)，自組織理論[12]觀點(diǎn)認(rèn)為全局優(yōu)化目標(biāo)可以通過(guò)局部?jī)?yōu)化的疊加來(lái)實(shí)現(xiàn)（如基于局部視角的拓?fù)淇刂扑惴?LMST[13]），從而該問(wèn)題可以近似地簡(jiǎn)化為通過(guò)選擇AUV節(jié)點(diǎn)遷移位置來(lái)優(yōu)化局部失效拓?fù)洹Ｎ恢眠x取問(wèn)題可以映射到斯坦納最小樹(shù)(SMT, Steiner minimum tree)[14]問(wèn)題，SMT問(wèn)題尋求若干個(gè)Steiner點(diǎn)，使得與給定節(jié)點(diǎn)相連后能夠生成最小連通網(wǎng)絡(luò)。結(jié)合水下環(huán)境特點(diǎn)和水下傳感器網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)，AUV節(jié)點(diǎn)的遷移位置選取需要考慮3項(xiàng)目標(biāo)：恢復(fù)受損拓?fù)涞倪B通性，愈合后局部拓?fù)涞耐ㄐ艜r(shí)延較小，愈合后局部拓?fù)涞耐ㄐ拍芎妮^低。此外，由于水下傳感器網(wǎng)絡(luò)中匯聚節(jié)點(diǎn)是數(shù)據(jù)接收的終點(diǎn)，據(jù)定理1可知接近匯聚節(jié)點(diǎn)的傳感器節(jié)點(diǎn)承擔(dān)較多的通信負(fù)載，因此，AUV節(jié)點(diǎn)還應(yīng)當(dāng)偏向遷移至接近匯聚節(jié)點(diǎn)的位置，以分流部分通信負(fù)載，實(shí)現(xiàn)網(wǎng)絡(luò)系統(tǒng)負(fù)載均衡的目的。這在 SMT問(wèn)題中可以通過(guò)設(shè)置權(quán)重參數(shù)方式來(lái)進(jìn)行調(diào)節(jié)，即賦予距匯聚節(jié)點(diǎn)近的鄰居節(jié)點(diǎn)較高權(quán)重。
定理 1 在節(jié)點(diǎn)均勻分布的情況下，層次較低的節(jié)點(diǎn)可能承擔(dān)的流量負(fù)載期望值較大。
證明 考慮匯聚節(jié)點(diǎn)唯一或多個(gè)[15]的情況，S=1時(shí)和S＞＞1時(shí)層次劃分示意如圖1所示，k表示節(jié)點(diǎn)所處的層次。
圖1 水下傳感器網(wǎng)絡(luò)層次劃分
不妨設(shè)水下傳感器網(wǎng)絡(luò)部署于 A×A的方形區(qū)域，采用節(jié)點(diǎn)可能需要提供直接轉(zhuǎn)發(fā)或間接轉(zhuǎn)發(fā)服務(wù)的節(jié)點(diǎn)數(shù)作為衡量負(fù)載期望值的指標(biāo)，一般情況下可以視作第k層節(jié)點(diǎn)為第k+1及更高層節(jié)點(diǎn)提供轉(zhuǎn)發(fā)服務(wù)。下面分別針對(duì)S=1和S＞＞1情況進(jìn)行討論。
1) 當(dāng)S=1時(shí)，第k層節(jié)點(diǎn)所需承擔(dān)負(fù)載的節(jié)點(diǎn)數(shù)期望值E(k)表示為式（3）所示。
2) 當(dāng)S＞＞1時(shí)，第k層節(jié)點(diǎn)所需承擔(dān)負(fù)載的節(jié)點(diǎn)數(shù)期望值E(k)表示為式（4）所示。
無(wú)論式（3）或式（4）中，k較小時(shí)E(k)較大，因此定理1得證。
連通性是傳感器網(wǎng)絡(luò)的獲取并傳輸數(shù)據(jù)的基本要求，由于水下聲通信的特性，水下傳感器網(wǎng)絡(luò)中傳輸時(shí)延和能耗要明顯高于陸地部署的傳感器網(wǎng)絡(luò)，故本文將連通性、傳輸時(shí)延、傳輸能耗作為問(wèn)題求解的主要目標(biāo)。當(dāng)理想情況下，所有節(jié)點(diǎn)的L、B和Vp都為相同的固定值，水下傳感器網(wǎng)絡(luò)拓?fù)涫У挠夏繕?biāo)obj可表述為如下目標(biāo)：
目標(biāo)1 connectivity(G)=1
目標(biāo)2
目標(biāo)3
目標(biāo)2～目標(biāo)3中ak、bk表示SMT中鏈接的權(quán)重，nu表示失效節(jié)點(diǎn)nf的鄰居節(jié)點(diǎn)，k表示nu所屬的層數(shù)。根據(jù)定理 1結(jié)論權(quán)重系數(shù)的設(shè)置應(yīng)滿足ak+1≤ak≤ak-1，bk+1≤bk≤bk-1。依據(jù)水下傳感器網(wǎng)絡(luò)的真實(shí)部署特點(diǎn)，水下傳感器網(wǎng)絡(luò)的拓?fù)溆蠁?wèn)題是一種特殊的SMT問(wèn)題，主要表現(xiàn)在如下約束：
約束1 傳統(tǒng)SMT問(wèn)題只具有一個(gè)最小網(wǎng)絡(luò)目標(biāo)，而本研究中需兼顧時(shí)延和能耗2種因素，并且Neighbor(nf)在優(yōu)化后均為SMT的葉節(jié)點(diǎn)，從而該問(wèn)題演化為一種攜帶多目標(biāo)的滿Steiner樹(shù)[16]；
約束2 廣義上的SMT可能會(huì)選取多個(gè)Steiner點(diǎn)作為網(wǎng)絡(luò)連接者，但是據(jù)假設(shè)5可知水下傳感器網(wǎng)絡(luò)中AUV數(shù)量極少，故在單次愈合拓?fù)鋾r(shí)僅考慮使用一個(gè)AUV的情況；
約束3 為滿足網(wǎng)絡(luò)連通目標(biāo)，AUV必須位于nf鄰居的覆蓋交集區(qū)域內(nèi)。
綜上分析，水下傳感器網(wǎng)絡(luò)拓?fù)溆蠁?wèn)題的一般形式化描述可歸結(jié)為問(wèn)題1。
問(wèn)題 1 給定水下傳感器網(wǎng)絡(luò)拓?fù)鋵?duì)應(yīng)的無(wú)向圖 G(V,E)和一個(gè)可行的優(yōu)化目標(biāo) obj，當(dāng)出現(xiàn)節(jié)點(diǎn)nf發(fā)生失效后，由一個(gè) AUV節(jié)點(diǎn)遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得Neighbor(nf)∪nf生成一棵滿 Steiner樹(shù)，并且該滿Steiner樹(shù)能符合目標(biāo)1～目標(biāo)3。
3 問(wèn)題轉(zhuǎn)化及近似算法
3.1 問(wèn)題轉(zhuǎn)化
滿Steiner樹(shù)問(wèn)題難以對(duì)多目標(biāo)進(jìn)行優(yōu)化，為了綜合考慮目標(biāo)2和目標(biāo)3，本文提出一種描述節(jié)點(diǎn)ni和nj間時(shí)延和能耗的綜合權(quán)值參數(shù)w(i,j)，給出其元素w(i,j)啟發(fā)式的定義，如式（5）所示。
其中，β、γ為預(yù)設(shè)指數(shù)，權(quán)值 w(i,j)由 delay(i,j)和cost(i,j)2部分決定，由于 delay(i,j)和 cost(i,j)都與d(i,j)相關(guān)，且 L、B都為常量，故最終近似作w(i,j)∝d(i,j)δ（δ≥1）。此時(shí)問(wèn)題1可以轉(zhuǎn)化為問(wèn)題2。
問(wèn)題2 節(jié)點(diǎn)nf發(fā)生失效后，由一個(gè)AUV節(jié)點(diǎn)遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得ckw(u,AUV)最小，其中ck+1≤ck≤ck-1，k表示nu所屬層數(shù)。
定理2 問(wèn)題2是個(gè)NP-hard問(wèn)題。
證明 滿 Steiner樹(shù)問(wèn)題已被證明是一個(gè) NP-完全問(wèn)題[17]，問(wèn)題2可以視作滿Steiner樹(shù)問(wèn)題的一種特例，因此易證問(wèn)題1也是一個(gè)NP-完全問(wèn)題。
3.2 近似算法
為解決問(wèn)題 2，本文設(shè)計(jì)了一種水下傳感器網(wǎng)絡(luò)拓?fù)溆纤惴?TRA(topology recovery algorithm of underwater sensor network)。TRA算法的主要思想是：首先為所有 nu∈Neighbor(nf)在∩cover(nu)域內(nèi)映射到各自的最優(yōu) Steiner位置（記作Steiner(nu)），再對(duì)各Steiner點(diǎn)使用質(zhì)心量算方法獲得近似最優(yōu)解 Pmove。TRA算法具體按照如下步驟1～步驟5進(jìn)行。
步驟1 當(dāng)nf失效后，判斷nu∈Neighbor(nf)之間是否能夠恢復(fù)連通，如能則采用TCS-CA算法[18]恢復(fù)連通性，否則轉(zhuǎn)至步驟2。
步驟2 計(jì)算∩cover(nu)（如圖2（a）所示陰影部分區(qū)域），若∩cover(nu)域?yàn)橐粋€(gè)點(diǎn)，令A(yù)UV節(jié)點(diǎn)遷移至nf，否則轉(zhuǎn)至步驟3。
步驟3 依據(jù)式（6）從nf的鄰居節(jié)點(diǎn)分別映射至交集區(qū)域（如圖 2（b）所示），令映射點(diǎn)所屬層次與鄰居節(jié)點(diǎn)一致，轉(zhuǎn)至步驟4。
Steiner(nu) = { P| P∈∩cover(nu) & min(w(u,P))} (6)其中，w(u,P)表示節(jié)點(diǎn)nu與位置P間的權(quán)值。
圖2 TRA算法
步驟 4 賦予較低層次鄰居的映射點(diǎn)以較高的權(quán)重參數(shù)，采用質(zhì)心量算方法計(jì)算近似最優(yōu)位置Pmove，Pmove的表達(dá)式如式（7）所示。將 AUV節(jié)點(diǎn)移至Pmove，轉(zhuǎn)至步驟5。
其中，du表示鄰居nu所對(duì)應(yīng)映射點(diǎn)的權(quán)值，nu所屬層數(shù)越小則權(quán)值越大，并對(duì)權(quán)值進(jìn)行了歸一化處理，即令根據(jù)步驟 1～步驟 4描述，有定理3成立。
定理3 Pmove必在∩cover(nu)域內(nèi)。
證明 ∩cover(nu)是 N(nf)個(gè)半徑為 R 圓的交集，Steiner位置都位于∩cover(nu)域的邊界，按照逆時(shí)針（或順時(shí)針）順序連接各Steiner位置，生成的多邊形為凸多邊形，可以證明每個(gè)內(nèi)角均小于π。角度大小由連續(xù)3個(gè)點(diǎn)位置決定，因此該結(jié)論可以分以下3種情況進(jìn)行討論。
情況1 連續(xù)的3點(diǎn)在同一圓弧上，此時(shí)該角必小于π。
情況2 3點(diǎn)位于2條不同圓弧上。不妨設(shè)點(diǎn)A、B位于同一圓弧，點(diǎn) C位于另一圓弧，假設(shè)∠ABC≥π，如圖3（a）所示。此時(shí)顯然有|CO|＞R，根據(jù)∩cover(nu)定義可知應(yīng)有|CO|≤R，故不可能出現(xiàn)∠ABC≥π。
圖3 凸多邊形的內(nèi)角生成情況
情況3 3點(diǎn)位于3條不同圓弧上。如圖3（b）所示，假定A、B分別位于2條圓弧，則根據(jù)∩cover(nu)定義和多邊形生成順序可知點(diǎn)C必定位于圖中陰影區(qū)域，BC’為圓弧在 B點(diǎn)處切線，因此有∠ABC＜∠ABC’＜π。
所以，生成的多邊形中所有內(nèi)角均小于 π，該多邊形為凸多邊形。凸多邊形內(nèi)所有點(diǎn)構(gòu)成的點(diǎn)集合是一個(gè)凸集，凸集具有如下性質(zhì)[19]：設(shè)X為向量空間，集合S?X是凸集，當(dāng)且僅當(dāng)任意xi∈Set，yi≥0，及，i=1,2,…,n，有成立。據(jù)該性質(zhì)及式（7），因 Steiner(nu)為多邊形頂點(diǎn)，屬于該凸多邊形集合，故 Pmove必在凸多邊形內(nèi)部，定理3得證。
步驟5 AUV節(jié)點(diǎn)通過(guò)設(shè)置自身功率，以確保能與最遠(yuǎn)處的nf鄰居進(jìn)行通信，同時(shí)調(diào)整鄰居節(jié)點(diǎn)功率大小以確保鏈接的雙向性，從而全局連通性得以恢復(fù)。
根據(jù)TRA算法的偽代碼描述，TRA算法的時(shí)間復(fù)雜度與失效節(jié)點(diǎn)的鄰居數(shù)有關(guān)，一般而言，當(dāng)水下傳感器網(wǎng)絡(luò)部署規(guī)模很大時(shí)，鄰居數(shù)可視作log(N)。TRA算法的實(shí)現(xiàn)需要的額外代價(jià)與拓?fù)涫У木唧w情況相關(guān)，若單跳鄰居能夠通過(guò)擴(kuò)大功率自愈，則最大代價(jià)為O((logN)2)；若無(wú)法直接愈合，則需要自移動(dòng)節(jié)點(diǎn)修復(fù)拓?fù)?，此時(shí)代價(jià)與鄰居數(shù)相關(guān)，故TRA算法實(shí)現(xiàn)代價(jià)為log(N)。
4 實(shí)驗(yàn)分析
本文利用OMNeT++[20]平臺(tái)設(shè)計(jì)了一個(gè)仿真程序，程序自上而下由應(yīng)用層、路由層、拓?fù)淇刂坪蚆AC層4個(gè)模塊構(gòu)成，其中路由層采用基于最短路的路由算法FA[21]，拓?fù)淇刂颇K實(shí)現(xiàn)了LMST[13]和拓?fù)溆纤惴═RA。實(shí)驗(yàn)環(huán)境如下：N個(gè)源節(jié)點(diǎn)隨機(jī)均勻散布于600m×600m的正方形區(qū)域，S個(gè)匯聚節(jié)點(diǎn)均勻分布于水平面，源點(diǎn)初始能量為 e，以速率 v（服從正態(tài)分布 v～N(μ,σ2）獲取到興趣數(shù)據(jù)分組。當(dāng)隨機(jī)生成的節(jié)點(diǎn)位置無(wú)法滿足連通則忽略并重新生成節(jié)點(diǎn)位置；不考慮AUV節(jié)點(diǎn)移動(dòng)能耗，當(dāng) AUV節(jié)點(diǎn)遷移愈合網(wǎng)絡(luò)后即視作能量為 e的普通節(jié)點(diǎn)；并且忽略節(jié)點(diǎn)接收?qǐng)?bào)文及處理器的能耗。當(dāng)水下傳感器網(wǎng)絡(luò)滿足以下3個(gè)條件則終止本次仿真：出現(xiàn)失效節(jié)點(diǎn)；失效節(jié)點(diǎn)的鄰居無(wú)法自愈拓?fù)溥B通性； AUV節(jié)點(diǎn)數(shù)量耗盡。用于和TRA算法比較的2種算法分別是：不采用拓?fù)溆系牟呗?，?dāng)節(jié)點(diǎn)出現(xiàn)失效生命期即終止，以下簡(jiǎn)稱NONE算法；愈合拓?fù)鋾r(shí)簡(jiǎn)單地把AUV節(jié)點(diǎn)移至nf，以下簡(jiǎn)稱SIMPLE算法。實(shí)驗(yàn)結(jié)果均為500次的平均值，主要參數(shù)如表1所示。
4.1 實(shí)驗(yàn)1
本實(shí)驗(yàn)通過(guò)不斷改變?cè)垂?jié)點(diǎn)數(shù)N（從100變化至500）的取值，觀察自移動(dòng)節(jié)點(diǎn)數(shù)M（分別為2，4，8，10）的變化對(duì)TRA算法所得到路徑平均時(shí)延和單位時(shí)間節(jié)點(diǎn)平均消耗能量的影響，路徑平均時(shí)延指所有源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組過(guò)程中產(chǎn)生時(shí)延的均值，單位時(shí)間節(jié)點(diǎn)平均消耗能量指在整個(gè)網(wǎng)絡(luò)生命期內(nèi)單個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)所產(chǎn)生能耗的單位時(shí)間均值，變化曲線分別如圖4（a）和圖4（b）所示。從圖4可以觀察到以下3個(gè)現(xiàn)象：圖4（a）表明隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)（節(jié)點(diǎn)分布趨于密集）路徑平均時(shí)延出現(xiàn)增長(zhǎng)的趨勢(shì)，這是因?yàn)楫?dāng)源節(jié)點(diǎn)更為密集時(shí)，源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路徑上每跳距離會(huì)相對(duì)減小，但總跳數(shù)會(huì)增加，而每跳都需計(jì)入時(shí)延，該因素占據(jù)主導(dǎo)作用，所以造成路徑平均時(shí)延的增長(zhǎng)；圖4（b）顯示隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)單位時(shí)間節(jié)點(diǎn)平均消耗能量會(huì)呈現(xiàn)出逐漸下降趨勢(shì)，這是由于節(jié)點(diǎn)分布密集使得每跳距離減小，而單跳距離減小能使能耗顯著降低，因此節(jié)點(diǎn)進(jìn)行傳輸或轉(zhuǎn)發(fā)時(shí)所產(chǎn)生能耗也將降低；從圖4還不難發(fā)現(xiàn)，當(dāng)自移動(dòng)節(jié)點(diǎn)數(shù)增加時(shí)，路徑平均時(shí)延和節(jié)點(diǎn)平均能耗都會(huì)降低，這是因?yàn)楫?dāng)自移動(dòng)節(jié)點(diǎn)數(shù)增加后，能對(duì)更多失效節(jié)點(diǎn)位置起到優(yōu)化作用，從而將對(duì)全局拓?fù)涓纳破鸬礁鼮槊黠@的影響。
表1 實(shí)驗(yàn)參數(shù)
4.2 實(shí)驗(yàn)2
圖4 源節(jié)點(diǎn)數(shù)和自移動(dòng)節(jié)點(diǎn)數(shù)對(duì)時(shí)延和能耗的影響
圖5 TRA與SIMPLE的平均路徑時(shí)延比較
為了驗(yàn)證TRA算法中計(jì)算Pmove的必要性，本實(shí)驗(yàn)將比較TRA和SIMPLE算法的路徑平均時(shí)延指標(biāo)，曲線如圖5所示。圖5表明TRA算法中把AUV節(jié)點(diǎn)遷移到位置Pmove能夠在一定程度上改善網(wǎng)絡(luò)的時(shí)延指標(biāo)，與SIMPLE相比最高處路徑平均時(shí)延減小了0.15s，因此對(duì)于時(shí)延較為敏感的水下傳感器網(wǎng)絡(luò)應(yīng)用是較為適用的。本實(shí)驗(yàn)還比較算法TRA與SIMPLE的單位時(shí)間節(jié)點(diǎn)平均消耗能量，如圖6所示，圖6反映了采用算法TRA所得到的單位時(shí)間節(jié)點(diǎn)平均能耗一直小于 SIMPLE，此外隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)TRA和SIMPLE的差距在逐步縮小，這是因?yàn)殡S著N增大時(shí)M并未發(fā)生改變，即自移動(dòng)節(jié)點(diǎn)數(shù)所占比重會(huì)逐漸下降，此時(shí)通過(guò)自移動(dòng)節(jié)點(diǎn)遷移來(lái)改善全局拓?fù)涞哪芰?huì)相對(duì)下降。
圖6 節(jié)點(diǎn)平均能耗比較
4.3 實(shí)驗(yàn)3
本實(shí)驗(yàn)通過(guò)改變自移動(dòng)節(jié)點(diǎn)數(shù)量和節(jié)點(diǎn)初始能量，觀察網(wǎng)絡(luò)生命期的變化情況，曲線如圖7所示。圖7印證了自移動(dòng)節(jié)點(diǎn)數(shù)增多和節(jié)點(diǎn)初始能量的增大有助于網(wǎng)絡(luò)生命期的增長(zhǎng)。此外，3條曲線隨著自移動(dòng)節(jié)點(diǎn)數(shù)增長(zhǎng)而生命期增幅呈現(xiàn)出逐步減小的趨勢(shì)，這是因?yàn)樽砸苿?dòng)節(jié)點(diǎn)數(shù)在水下傳感器網(wǎng)絡(luò)中占據(jù)一定比例時(shí)，隨著時(shí)間推移水下傳感器網(wǎng)絡(luò)中會(huì)出現(xiàn)越來(lái)越多的潛在失效節(jié)點(diǎn)（能量趨近于 0的節(jié)點(diǎn)），而自移動(dòng)節(jié)點(diǎn)數(shù)是相對(duì)較小的，無(wú)法愈合所有的潛在局部失效拓?fù)?，因此通過(guò)愈合拓?fù)鋪?lái)延長(zhǎng)生命期的能力受到了制約。本實(shí)驗(yàn)還比較了TRA、NONE與SIMPLE 3種算法的網(wǎng)絡(luò)生命期，如圖8所示，圖8說(shuō)明以下2個(gè)現(xiàn)象：隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)，3條曲線的網(wǎng)絡(luò)生命期都呈現(xiàn)出上升勢(shì)態(tài)，該現(xiàn)象可用實(shí)驗(yàn)1的結(jié)論來(lái)解釋，因?yàn)楫?dāng)源節(jié)點(diǎn)增多時(shí)節(jié)點(diǎn)平均能耗會(huì)降低，所以網(wǎng)絡(luò)生命期會(huì)增長(zhǎng)； TRA和SIMPLE所獲得網(wǎng)絡(luò)生命期遠(yuǎn)高于未采用拓?fù)溆喜呗缘腘ONE算法，另外采用TRA所獲生命期要高于SIMPLE，最高處當(dāng)N=500時(shí)可達(dá)649s。
圖7 自移動(dòng)節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)生命期的影響
圖8 3種算法的網(wǎng)絡(luò)生命期比較
5 結(jié)束語(yǔ)
本文設(shè)計(jì)了一種基于滿 Steiner樹(shù)問(wèn)題的水下傳感器網(wǎng)絡(luò)拓?fù)溆纤惴?TRA。TRA算法適用于時(shí)延敏感的水下無(wú)線傳感器網(wǎng)絡(luò)，并且在自移動(dòng)節(jié)點(diǎn)的遷移位置選取過(guò)程中考慮了高效能耗問(wèn)題。對(duì)于 TRA算法還有著以下幾個(gè)方面的補(bǔ)充和考慮之處：水下環(huán)境一般認(rèn)為是一種三維環(huán)境，TRA算法雖然是基于二維環(huán)境建模，但本文中若干結(jié)論（如定理3等）在三維環(huán)境依然成立，算法設(shè)計(jì)也很容易推廣至三維環(huán)境；水下傳感器網(wǎng)絡(luò)是一個(gè)多模塊組成的復(fù)雜系統(tǒng)，模塊間的協(xié)同是一個(gè)不容忽視的重要問(wèn)題，如何使得拓?fù)溆吓c其他模塊良好協(xié)作也是 TRA應(yīng)繼續(xù)改進(jìn)的方向；此外，水下傳感器網(wǎng)絡(luò)通常部署于惡劣環(huán)境，因此很多理論上的假設(shè)前提未必能得到滿足，例如節(jié)點(diǎn)的移動(dòng)性以及節(jié)點(diǎn)的信號(hào)覆蓋范圍有可能為不規(guī)則圖形，所以 TRA的設(shè)計(jì)還應(yīng)有機(jī)結(jié)合應(yīng)用場(chǎng)景和實(shí)際部署環(huán)境，這樣才具有更高的實(shí)用價(jià)值。
[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor network∶ a survey [J]. Computer Networks, 2002, 38(4)∶393-422.
[2] ELSON J, ESTRIN D. Sensor Networks∶ a Bridge to the Physical World[M]. Norwell∶ Kluwer Academic Publishers, 2004. 3-20.
[3] 崔莉，鞠海玲，苗勇等. 無(wú)線傳感器網(wǎng)絡(luò)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(1)∶163-174.CUI L, JU H L, MIAO Y, et al. Overview of wireless sensor networks[J]. Journal of Computer Research and Development, 2005,42(1)∶163-174.
[4] AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks∶ research challenges[J]. Ad Hoc Networks, 2005, 3(3)∶257-279.
[5] AKYILDIZ I F, POMPILI D, MELODIA T. Challenges for efficient communication in underwater acoustic sensor networks[J]. ACM SIGBED Review, 2004, 1(2)∶ 3-8.
[6] HEIDEMANN J, YE W, WILLS J, et al. Research challenges and applications for underwater sensor networking[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York,2006. 33-40.
[7] AKYILDIZ I F, POMPILI D, MELODIA T. State-of-the-art in protocol research for underwater acoustic sensor networks[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York, 2006. 7-16.
[8] CHRYSSOSTOMIDIS C. AUV laboratory at MIT sea grant[EB/OL].http∶//auvlab.mit.edu/, 2009.
[9] PETER ?, EDWARD F, NAOMI E L. Cooperative control of mobile sensor networks∶ adaptive gradient climbing in a distributed environment[J]. IEEE Transactions on Automatic Control, 2004, 49(8)∶1292-1302.
[10] IBRAHIM S, CUI J H, AMMAR R. Surface-level gateway deployment for underwater sensor networks[A]. Proc of Military Communications Conference 2007[C]. Sanfrancisco, CA, 2007. 1-7.
[11] CHANG J H, TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2004,12(4)∶ 609-619.
[12] 吳彤. 自組織方法論研究[M]. 北京：清華大學(xué)出版社, 2001.WU T. Self-Organizing Methodology[M]. Beijing∶ Tsinghua University Press, 2001.
[13] LI N, HOU J C, SHA L. Design and analysis of an MST-based topology control algorithm[A]. Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies(INFORCOM 2003)[C]. Sanfrancisco, CA, 2003. 1702-1712.
[14] 越民義. 最小網(wǎng)絡(luò)——斯坦納樹(shù)問(wèn)題[M]. 上?！?上海科學(xué)技術(shù)出版社, 2006.YUE M Y. Minimum Network-Steiner Tree Problem[M]. Shanghai∶Shanghai Science and Technology Press, 2006.
[15] ALSALIH W, AKL S, HASSANEIN H. Placement of multiple mobile data collectors in underwater acoustic sensor networks[A]. Proc of IEEE International Conference on Communications, ICC 2008[C].Beijing, 2008. 19-23.
[16] BORCHERS A, DU D Z. The k-Steiner ratio in graphs[A]. Proc of the Twenty-Seventh Annual ACM Symposium on Theory of Computing[C]. Las Vegas, USA, 1995. 641-649.
[17] MARTINEZ F, PINA J, SOARES J. Algorithm for terminal Steiner trees[J]. Theoretical Computer Science, 2007, 389(1)∶ 133-142.
[18] 劉林峰, 吳家皋, 鄒志強(qiáng)等. 面向節(jié)點(diǎn)失效問(wèn)題的傳感器網(wǎng)絡(luò)拓?fù)渥杂惴╗J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2009, 39(4)∶695-699.LIU L F, WU J G, ZOU Z Q, et al. Topology control 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.
[19] 徐玖平, 李軍. 多目標(biāo)決策的理論與方法[M]. 北京∶ 清華大學(xué)出版社, 2005.XU J P, LI J. Multi-Objective Decision Theory and Method[M]. Beijing∶ Tsinghua University Press, 2005.
[20] ANDRAS VARGA. OMNeT++ -discrete event simulation system user manual[EB/OL]. http∶//www.omnet.org/, 2008.
[21] CHANG J H, TASSIULAS L. Energy conserving routing in wireless ad-hoc networks[A]. Proc of IEEE INFOCOM [C]. Tel Aviv, Israel,2000. 22-31.
猜你喜歡
基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46 基于GCC-nearest時(shí)延估計(jì)的室內(nèi)聲源定位電子制作(2019年23期)2019-02-23 13:21:12 電子制作(2018年23期)2018-12-26 01:01:16 基于改進(jìn)二次相關(guān)算法的TDOA時(shí)延估計(jì)測(cè)控技術(shù)(2018年6期)2018-11-25 09:50:10 冬季歐亞大陸反氣旋活動(dòng)特征及其與中國(guó)氣溫的關(guān)系大氣科學(xué)學(xué)報(bào)(2017年3期)2017-05-30 10:48:04 勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D汽車(chē)維修技師(2017年10期)2017-03-17 02:25:01 FRFT在水聲信道時(shí)延頻移聯(lián)合估計(jì)中的應(yīng)用系統(tǒng)工程與電子技術(shù)(2016年7期)2016-08-21 13:59:18 電測(cè)與儀表(2016年5期)2016-04-22 01:13:46 基于分段CEEMD降噪的時(shí)延估計(jì)研究電測(cè)與儀表(2016年17期)2016-04-11 12:38:28 飛行試驗(yàn)項(xiàng)目生命期研究項(xiàng)目管理技術(shù)(2015年10期)2015-12-26 09:36:04
劉林峰，劉業(yè)
（1. 南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.中國(guó)科學(xué)技術(shù)大學(xué) 蘇州研究院，江蘇 蘇州 215123）
1 引言
地球表面71%被人跡罕至的水域（海洋、湖泊、河流）覆蓋，出于科學(xué)探索、資源開(kāi)采、污染監(jiān)控、戰(zhàn)術(shù)監(jiān)視或海岸線保護(hù)等種種目的，人類(lèi)對(duì)監(jiān)測(cè)這些水域一直有著極大的興趣。在無(wú)線傳感器網(wǎng)絡(luò)[1～3]（WSN, wireless sensor network）被應(yīng)用之前，水下數(shù)據(jù)的感知和收集工作一般通過(guò)有線網(wǎng)絡(luò)來(lái)完成，這種方式代價(jià)高昂并且需要大量工程技術(shù)輔助。適合水下環(huán)境的大量傳感器節(jié)點(diǎn)協(xié)同工作，它們隨機(jī)分布于監(jiān)測(cè)水域，并通過(guò)基于聲通信的無(wú)線方式自組織構(gòu)成水下無(wú)線傳感器網(wǎng)絡(luò)[4～6]（UWSN, underwater wireless sensor network），不僅部署代價(jià)相對(duì)低廉，而且其分布式結(jié)構(gòu)能夠在水下監(jiān)測(cè)應(yīng)用中展現(xiàn)出更高的靈活度。然而，水下傳感器網(wǎng)絡(luò)的設(shè)計(jì)也面臨著多方面的約束和挑戰(zhàn)，主要表現(xiàn)在鏈接時(shí)延明顯且多變、節(jié)點(diǎn)能量有限、帶寬較低、誤碼率高等。此外，水下傳感器節(jié)點(diǎn)極易受到各類(lèi)外力（如海浪和海風(fēng)擾動(dòng)、水下生物觸動(dòng)等）影響發(fā)生位置遷移，甚至可能因此遭受毀壞，從而導(dǎo)致網(wǎng)絡(luò)拓?fù)渥兓l繁、局部網(wǎng)絡(luò)失效概率增高，如何愈合局部失效拓?fù)湟殉蔀樵擃I(lǐng)域的研究熱點(diǎn)之一。
部署于水域場(chǎng)景的水下傳感器網(wǎng)絡(luò)中應(yīng)有4種節(jié)點(diǎn)類(lèi)型：底面節(jié)點(diǎn)、浮游節(jié)點(diǎn)、自移動(dòng)節(jié)點(diǎn)（AUV,autonomous underwater vehicle）[7]和匯聚節(jié)點(diǎn)，其中底面節(jié)點(diǎn)鋪設(shè)于水域底面，由于水域底面地形異常復(fù)雜，可能會(huì)遭遇障礙地勢(shì)而形成通信孤島，該類(lèi)節(jié)點(diǎn)受水域底面摩擦力影響所以位置遷移幅度較小，浮游節(jié)點(diǎn)依靠浮力裝置懸浮在水中（懸浮深度與水域鹽度、浮力裝置屬性相關(guān)），該類(lèi)節(jié)點(diǎn)受外力擾動(dòng)而位移的幅度較大，但發(fā)生位移待穩(wěn)定后仍將處于相同懸浮深度的橫切平面上，自移動(dòng)節(jié)點(diǎn)具備自主的移動(dòng)能力，能夠按照某種策略進(jìn)行位移，承擔(dān)改善網(wǎng)絡(luò)結(jié)構(gòu)和自愈失效拓?fù)涞闹匾饔谩?/p>
在傳統(tǒng)WSN中，由于一般不考慮自移動(dòng)節(jié)點(diǎn)的存在，故通常采用調(diào)大節(jié)點(diǎn)功率的方式來(lái)愈合失效拓?fù)?，該方式無(wú)法改變?nèi)魏喂?jié)點(diǎn)的位置，因此愈合過(guò)程很難改善拓?fù)湫再|(zhì)，并極有可能造成拓?fù)湫再|(zhì)惡化。水下傳感器網(wǎng)絡(luò)中的AUV節(jié)點(diǎn)具備移動(dòng)能力，能夠按照特定策略遷移至指定位置替代失效節(jié)點(diǎn)并承擔(dān)其原角色，由該類(lèi)節(jié)點(diǎn)進(jìn)行的拓?fù)溆喜粌H能夠使得全局拓?fù)浠謴?fù)連通性，還能通過(guò)改變節(jié)點(diǎn)原有位置的方式來(lái)改善全局拓?fù)洌瑥亩哂懈叩膶?shí)用性。目前關(guān)于水下傳感器網(wǎng)絡(luò)的拓?fù)溆涎芯枯^為薄弱，多側(cè)重于AUV節(jié)點(diǎn)設(shè)計(jì)或節(jié)點(diǎn)協(xié)作策略的研究，如文獻(xiàn)[8]設(shè)計(jì)的Odyssey-class AUV能夠到達(dá)水域的任意深度，可以修復(fù)失效的局部拓?fù)?；文獻(xiàn)[9]提出了一種節(jié)點(diǎn)間協(xié)作控制的網(wǎng)絡(luò)管理模式，增強(qiáng)了網(wǎng)絡(luò)的健壯性和自適應(yīng)程度，能夠有效地應(yīng)對(duì)節(jié)點(diǎn)失效情況。然而，AUV節(jié)點(diǎn)遷移至何處才能達(dá)到拓?fù)溆虾屯負(fù)鋬?yōu)化的雙重目標(biāo)，該問(wèn)題尚未見(jiàn)深入研究，尤其對(duì)于時(shí)延較大的水下環(huán)境，AUV節(jié)點(diǎn)遷移策略的研究將有助于全局拓?fù)鋬?yōu)化、網(wǎng)絡(luò)傳輸時(shí)延降低、能耗效率的提升，因此研究該問(wèn)題很有必要。本文將針對(duì)時(shí)延敏感類(lèi)水下應(yīng)用（如水域戰(zhàn)術(shù)監(jiān)視、污染監(jiān)控等），采用 AUV節(jié)點(diǎn)遷移修復(fù)拓?fù)涞牟呗?，提出一種能夠降低傳輸時(shí)延和提高能耗效率的拓?fù)溆纤惴ā?/p>
2 網(wǎng)絡(luò)模型及問(wèn)題描述
2.1 模型構(gòu)建
在實(shí)際應(yīng)用場(chǎng)景中浮游節(jié)點(diǎn)和底面節(jié)點(diǎn)一般都扮演數(shù)據(jù)感知、采集和傳輸?shù)慕巧虼吮疚膶⒃?種節(jié)點(diǎn)歸為水下傳感器節(jié)點(diǎn)。假定有S個(gè)匯聚節(jié)點(diǎn)、N個(gè)水下傳感器節(jié)點(diǎn)和M個(gè)自移動(dòng)節(jié)點(diǎn)隨機(jī)均勻散布于監(jiān)測(cè)水域，其中水下傳感器節(jié)點(diǎn)攜帶有限能量的電池。水下傳感器節(jié)點(diǎn)能夠感知并發(fā)送監(jiān)測(cè)所得數(shù)據(jù)，同時(shí)根據(jù)網(wǎng)絡(luò)拓?fù)錇楫?dāng)前傳輸轄域內(nèi)的鄰居節(jié)點(diǎn)提供報(bào)文接收和轉(zhuǎn)發(fā)服務(wù)，隨著數(shù)據(jù)流量的經(jīng)由，節(jié)點(diǎn)的無(wú)線收發(fā)能耗和通信模塊的閑時(shí)開(kāi)銷(xiāo)使得電池能量不斷降低。初始工作狀態(tài)時(shí)水下傳感器網(wǎng)絡(luò)由水下傳感器節(jié)點(diǎn)保持全局連通，隨后節(jié)點(diǎn)可能由于能量耗盡、外力作用等復(fù)雜因素而導(dǎo)致失效，就需要自移動(dòng)節(jié)點(diǎn)來(lái)愈合拓?fù)洹?/p>
抽象水下傳感器網(wǎng)絡(luò)拓?fù)錇橐粋€(gè)權(quán)重圖G(V,E)，其中 V、E分別表示節(jié)點(diǎn)、鏈接的集合，V={n0, …, nS-1, nS, …, nS+N-1, nS+N, …, nS+N+M-1}，n0, …, nS-1表示匯聚節(jié)點(diǎn)，nS, …, nS+N-1表示N個(gè)水下傳感器節(jié)點(diǎn)，nS+N, …, nS+N+M-1表示M個(gè)自移動(dòng)節(jié)點(diǎn)；標(biāo)記節(jié)點(diǎn) ni的鄰居集合為 Neighbor(ni)，數(shù)量為N(ni)；失效節(jié)點(diǎn)記作nf，替代該節(jié)點(diǎn)的自移動(dòng)節(jié)點(diǎn)記作nAUV；對(duì)于任意i∈[S, S+N+M-1]，節(jié)點(diǎn)ni的當(dāng)前能量記作e(ni)，節(jié)點(diǎn)ni的當(dāng)前覆蓋半徑記作radius(ni)，所有節(jié)點(diǎn)擁有相同的最大傳輸范圍R；節(jié)點(diǎn)ni的最大覆蓋區(qū)域可以表示為cover(ni)={ nj| d(i,j)≤R and nj∈IR2}；定義網(wǎng)絡(luò)連通函數(shù)connectivity(G)∶ G(V,E)→X，X為布爾邏輯數(shù)集合。若節(jié)點(diǎn)ni和nj之間存在通信鏈接則記作(i,j)∈E，鏈接(i,j)的距離記作 d(i,j)，其上時(shí)延記作 delay(i,j)，delay(i,j)[10]表示為式（1）所示形式。
其中，L表示數(shù)據(jù)分組大小，B表示數(shù)據(jù)傳輸率，Vp為水下聲波傳輸速率。鏈接(i,j)上的能耗記作cost(i,j)如式（2）所示。
其中，ω為常系數(shù)，α為能量衰減指數(shù)，當(dāng)在惡劣通信環(huán)境中或有障礙物時(shí)較大，據(jù)實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)一般有α≥2。為便于模型的分析和描述，本文還給出如下假設(shè)：
假設(shè) 1 傳感器節(jié)點(diǎn)的天線以全方位廣播方式進(jìn)行通信，且通信鏈接具有對(duì)稱性；
假設(shè) 2 水下傳感器網(wǎng)絡(luò)的部署獲得定位系統(tǒng)（如GPS）的輔助, 每個(gè)節(jié)點(diǎn)均獲知自己及其鄰居的地理位置；
假設(shè) 3 匯聚節(jié)點(diǎn)能量為+∞，自移動(dòng)節(jié)點(diǎn)因位置移動(dòng)發(fā)生的能耗忽略不計(jì)；
假設(shè) 4 節(jié)點(diǎn)發(fā)生失效前水下傳感器網(wǎng)絡(luò)拓?fù)湟呀?jīng)為近似最優(yōu)結(jié)構(gòu)；
假設(shè)5 M＜＜N，因代價(jià)較高所以水下傳感器網(wǎng)絡(luò)中可供部署的自移動(dòng)節(jié)點(diǎn)數(shù)量一般認(rèn)為很少；
假設(shè)6 水下傳感器網(wǎng)絡(luò)的生命期[11]定義為在傳感器網(wǎng)絡(luò)系統(tǒng)的流量路由過(guò)程中，最先因電池能量耗盡而失效的節(jié)點(diǎn)生命期。
2.2 問(wèn)題描述
當(dāng)有節(jié)點(diǎn)發(fā)生失效后，拓?fù)浣Y(jié)構(gòu)可能不再滿足全局連通性，此時(shí)應(yīng)由自移動(dòng)節(jié)點(diǎn)替代已失效的節(jié)點(diǎn)，與失效節(jié)點(diǎn)的單跳鄰居連接，從而實(shí)現(xiàn)拓?fù)涞闹匦掠?。水下傳感器網(wǎng)絡(luò)拓?fù)淇刂浦袝r(shí)延和能耗是2個(gè)應(yīng)予以首要關(guān)注的因素，因此當(dāng)AUV節(jié)點(diǎn)愈合拓?fù)鋾r(shí)也必須考慮這2個(gè)因素。就該問(wèn)題而言，扮演替代角色的自移動(dòng)節(jié)點(diǎn)的位置選取至關(guān)重要，自移動(dòng)節(jié)點(diǎn)的遷移行為不僅能夠恢復(fù)受損拓?fù)?，更能改善受損拓?fù)涞臅r(shí)延和能耗特性，故不應(yīng)簡(jiǎn)單地讓AUV節(jié)點(diǎn)遷移至失效節(jié)點(diǎn)位置，而應(yīng)重新權(quán)衡并選取更為合適的位置，因此水下傳感器網(wǎng)絡(luò)拓?fù)溆蠁?wèn)題可歸結(jié)為最優(yōu)化網(wǎng)絡(luò)拓?fù)涞腁UV節(jié)點(diǎn)位置選取問(wèn)題。然而最優(yōu)化全局拓?fù)湫枰W(wǎng)絡(luò)尺度上的拓?fù)湫畔⒔换?，這對(duì)于水下傳感器網(wǎng)絡(luò)而言是難以承受和異常復(fù)雜的。因水下傳感器網(wǎng)絡(luò)屬于一種自組織網(wǎng)絡(luò)，自組織理論[12]觀點(diǎn)認(rèn)為全局優(yōu)化目標(biāo)可以通過(guò)局部?jī)?yōu)化的疊加來(lái)實(shí)現(xiàn)（如基于局部視角的拓?fù)淇刂扑惴?LMST[13]），從而該問(wèn)題可以近似地簡(jiǎn)化為通過(guò)選擇AUV節(jié)點(diǎn)遷移位置來(lái)優(yōu)化局部失效拓?fù)洹Ｎ恢眠x取問(wèn)題可以映射到斯坦納最小樹(shù)(SMT, Steiner minimum tree)[14]問(wèn)題，SMT問(wèn)題尋求若干個(gè)Steiner點(diǎn)，使得與給定節(jié)點(diǎn)相連后能夠生成最小連通網(wǎng)絡(luò)。結(jié)合水下環(huán)境特點(diǎn)和水下傳感器網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)，AUV節(jié)點(diǎn)的遷移位置選取需要考慮3項(xiàng)目標(biāo)：恢復(fù)受損拓?fù)涞倪B通性，愈合后局部拓?fù)涞耐ㄐ艜r(shí)延較小，愈合后局部拓?fù)涞耐ㄐ拍芎妮^低。此外，由于水下傳感器網(wǎng)絡(luò)中匯聚節(jié)點(diǎn)是數(shù)據(jù)接收的終點(diǎn)，據(jù)定理1可知接近匯聚節(jié)點(diǎn)的傳感器節(jié)點(diǎn)承擔(dān)較多的通信負(fù)載，因此，AUV節(jié)點(diǎn)還應(yīng)當(dāng)偏向遷移至接近匯聚節(jié)點(diǎn)的位置，以分流部分通信負(fù)載，實(shí)現(xiàn)網(wǎng)絡(luò)系統(tǒng)負(fù)載均衡的目的。這在 SMT問(wèn)題中可以通過(guò)設(shè)置權(quán)重參數(shù)方式來(lái)進(jìn)行調(diào)節(jié)，即賦予距匯聚節(jié)點(diǎn)近的鄰居節(jié)點(diǎn)較高權(quán)重。
定理 1 在節(jié)點(diǎn)均勻分布的情況下，層次較低的節(jié)點(diǎn)可能承擔(dān)的流量負(fù)載期望值較大。
證明 考慮匯聚節(jié)點(diǎn)唯一或多個(gè)[15]的情況，S=1時(shí)和S＞＞1時(shí)層次劃分示意如圖1所示，k表示節(jié)點(diǎn)所處的層次。
圖1 水下傳感器網(wǎng)絡(luò)層次劃分
不妨設(shè)水下傳感器網(wǎng)絡(luò)部署于 A×A的方形區(qū)域，采用節(jié)點(diǎn)可能需要提供直接轉(zhuǎn)發(fā)或間接轉(zhuǎn)發(fā)服務(wù)的節(jié)點(diǎn)數(shù)作為衡量負(fù)載期望值的指標(biāo)，一般情況下可以視作第k層節(jié)點(diǎn)為第k+1及更高層節(jié)點(diǎn)提供轉(zhuǎn)發(fā)服務(wù)。下面分別針對(duì)S=1和S＞＞1情況進(jìn)行討論。
1) 當(dāng)S=1時(shí)，第k層節(jié)點(diǎn)所需承擔(dān)負(fù)載的節(jié)點(diǎn)數(shù)期望值E(k)表示為式（3）所示。
2) 當(dāng)S＞＞1時(shí)，第k層節(jié)點(diǎn)所需承擔(dān)負(fù)載的節(jié)點(diǎn)數(shù)期望值E(k)表示為式（4）所示。
無(wú)論式（3）或式（4）中，k較小時(shí)E(k)較大，因此定理1得證。
連通性是傳感器網(wǎng)絡(luò)的獲取并傳輸數(shù)據(jù)的基本要求，由于水下聲通信的特性，水下傳感器網(wǎng)絡(luò)中傳輸時(shí)延和能耗要明顯高于陸地部署的傳感器網(wǎng)絡(luò)，故本文將連通性、傳輸時(shí)延、傳輸能耗作為問(wèn)題求解的主要目標(biāo)。當(dāng)理想情況下，所有節(jié)點(diǎn)的L、B和Vp都為相同的固定值，水下傳感器網(wǎng)絡(luò)拓?fù)涫У挠夏繕?biāo)obj可表述為如下目標(biāo)：
目標(biāo)1 connectivity(G)=1
目標(biāo)2
目標(biāo)3
目標(biāo)2～目標(biāo)3中ak、bk表示SMT中鏈接的權(quán)重，nu表示失效節(jié)點(diǎn)nf的鄰居節(jié)點(diǎn)，k表示nu所屬的層數(shù)。根據(jù)定理 1結(jié)論權(quán)重系數(shù)的設(shè)置應(yīng)滿足ak+1≤ak≤ak-1，bk+1≤bk≤bk-1。依據(jù)水下傳感器網(wǎng)絡(luò)的真實(shí)部署特點(diǎn)，水下傳感器網(wǎng)絡(luò)的拓?fù)溆蠁?wèn)題是一種特殊的SMT問(wèn)題，主要表現(xiàn)在如下約束：
約束1 傳統(tǒng)SMT問(wèn)題只具有一個(gè)最小網(wǎng)絡(luò)目標(biāo)，而本研究中需兼顧時(shí)延和能耗2種因素，并且Neighbor(nf)在優(yōu)化后均為SMT的葉節(jié)點(diǎn)，從而該問(wèn)題演化為一種攜帶多目標(biāo)的滿Steiner樹(shù)[16]；
約束2 廣義上的SMT可能會(huì)選取多個(gè)Steiner點(diǎn)作為網(wǎng)絡(luò)連接者，但是據(jù)假設(shè)5可知水下傳感器網(wǎng)絡(luò)中AUV數(shù)量極少，故在單次愈合拓?fù)鋾r(shí)僅考慮使用一個(gè)AUV的情況；
約束3 為滿足網(wǎng)絡(luò)連通目標(biāo)，AUV必須位于nf鄰居的覆蓋交集區(qū)域內(nèi)。
綜上分析，水下傳感器網(wǎng)絡(luò)拓?fù)溆蠁?wèn)題的一般形式化描述可歸結(jié)為問(wèn)題1。
問(wèn)題 1 給定水下傳感器網(wǎng)絡(luò)拓?fù)鋵?duì)應(yīng)的無(wú)向圖 G(V,E)和一個(gè)可行的優(yōu)化目標(biāo) obj，當(dāng)出現(xiàn)節(jié)點(diǎn)nf發(fā)生失效后，由一個(gè) AUV節(jié)點(diǎn)遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得Neighbor(nf)∪nf生成一棵滿 Steiner樹(shù)，并且該滿Steiner樹(shù)能符合目標(biāo)1～目標(biāo)3。
3 問(wèn)題轉(zhuǎn)化及近似算法
3.1 問(wèn)題轉(zhuǎn)化
滿Steiner樹(shù)問(wèn)題難以對(duì)多目標(biāo)進(jìn)行優(yōu)化，為了綜合考慮目標(biāo)2和目標(biāo)3，本文提出一種描述節(jié)點(diǎn)ni和nj間時(shí)延和能耗的綜合權(quán)值參數(shù)w(i,j)，給出其元素w(i,j)啟發(fā)式的定義，如式（5）所示。
其中，β、γ為預(yù)設(shè)指數(shù)，權(quán)值 w(i,j)由 delay(i,j)和cost(i,j)2部分決定，由于 delay(i,j)和 cost(i,j)都與d(i,j)相關(guān)，且 L、B都為常量，故最終近似作w(i,j)∝d(i,j)δ（δ≥1）。此時(shí)問(wèn)題1可以轉(zhuǎn)化為問(wèn)題2。
問(wèn)題2 節(jié)點(diǎn)nf發(fā)生失效后，由一個(gè)AUV節(jié)點(diǎn)遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得ckw(u,AUV)最小，其中ck+1≤ck≤ck-1，k表示nu所屬層數(shù)。
定理2 問(wèn)題2是個(gè)NP-hard問(wèn)題。
證明 滿 Steiner樹(shù)問(wèn)題已被證明是一個(gè) NP-完全問(wèn)題[17]，問(wèn)題2可以視作滿Steiner樹(shù)問(wèn)題的一種特例，因此易證問(wèn)題1也是一個(gè)NP-完全問(wèn)題。
3.2 近似算法
為解決問(wèn)題 2，本文設(shè)計(jì)了一種水下傳感器網(wǎng)絡(luò)拓?fù)溆纤惴?TRA(topology recovery algorithm of underwater sensor network)。TRA算法的主要思想是：首先為所有 nu∈Neighbor(nf)在∩cover(nu)域內(nèi)映射到各自的最優(yōu) Steiner位置（記作Steiner(nu)），再對(duì)各Steiner點(diǎn)使用質(zhì)心量算方法獲得近似最優(yōu)解 Pmove。TRA算法具體按照如下步驟1～步驟5進(jìn)行。
步驟1 當(dāng)nf失效后，判斷nu∈Neighbor(nf)之間是否能夠恢復(fù)連通，如能則采用TCS-CA算法[18]恢復(fù)連通性，否則轉(zhuǎn)至步驟2。
步驟2 計(jì)算∩cover(nu)（如圖2（a）所示陰影部分區(qū)域），若∩cover(nu)域?yàn)橐粋€(gè)點(diǎn)，令A(yù)UV節(jié)點(diǎn)遷移至nf，否則轉(zhuǎn)至步驟3。
步驟3 依據(jù)式（6）從nf的鄰居節(jié)點(diǎn)分別映射至交集區(qū)域（如圖 2（b）所示），令映射點(diǎn)所屬層次與鄰居節(jié)點(diǎn)一致，轉(zhuǎn)至步驟4。
Steiner(nu) = { P| P∈∩cover(nu) & min(w(u,P))} (6)其中，w(u,P)表示節(jié)點(diǎn)nu與位置P間的權(quán)值。
圖2 TRA算法
步驟 4 賦予較低層次鄰居的映射點(diǎn)以較高的權(quán)重參數(shù)，采用質(zhì)心量算方法計(jì)算近似最優(yōu)位置Pmove，Pmove的表達(dá)式如式（7）所示。將 AUV節(jié)點(diǎn)移至Pmove，轉(zhuǎn)至步驟5。
其中，du表示鄰居nu所對(duì)應(yīng)映射點(diǎn)的權(quán)值，nu所屬層數(shù)越小則權(quán)值越大，并對(duì)權(quán)值進(jìn)行了歸一化處理，即令根據(jù)步驟 1～步驟 4描述，有定理3成立。
定理3 Pmove必在∩cover(nu)域內(nèi)。
證明 ∩cover(nu)是 N(nf)個(gè)半徑為 R 圓的交集，Steiner位置都位于∩cover(nu)域的邊界，按照逆時(shí)針（或順時(shí)針）順序連接各Steiner位置，生成的多邊形為凸多邊形，可以證明每個(gè)內(nèi)角均小于π。角度大小由連續(xù)3個(gè)點(diǎn)位置決定，因此該結(jié)論可以分以下3種情況進(jìn)行討論。
情況1 連續(xù)的3點(diǎn)在同一圓弧上，此時(shí)該角必小于π。
情況2 3點(diǎn)位于2條不同圓弧上。不妨設(shè)點(diǎn)A、B位于同一圓弧，點(diǎn) C位于另一圓弧，假設(shè)∠ABC≥π，如圖3（a）所示。此時(shí)顯然有|CO|＞R，根據(jù)∩cover(nu)定義可知應(yīng)有|CO|≤R，故不可能出現(xiàn)∠ABC≥π。
圖3 凸多邊形的內(nèi)角生成情況
情況3 3點(diǎn)位于3條不同圓弧上。如圖3（b）所示，假定A、B分別位于2條圓弧，則根據(jù)∩cover(nu)定義和多邊形生成順序可知點(diǎn)C必定位于圖中陰影區(qū)域，BC’為圓弧在 B點(diǎn)處切線，因此有∠ABC＜∠ABC’＜π。
所以，生成的多邊形中所有內(nèi)角均小于 π，該多邊形為凸多邊形。凸多邊形內(nèi)所有點(diǎn)構(gòu)成的點(diǎn)集合是一個(gè)凸集，凸集具有如下性質(zhì)[19]：設(shè)X為向量空間，集合S?X是凸集，當(dāng)且僅當(dāng)任意xi∈Set，yi≥0，及，i=1,2,…,n，有成立。據(jù)該性質(zhì)及式（7），因 Steiner(nu)為多邊形頂點(diǎn)，屬于該凸多邊形集合，故 Pmove必在凸多邊形內(nèi)部，定理3得證。
步驟5 AUV節(jié)點(diǎn)通過(guò)設(shè)置自身功率，以確保能與最遠(yuǎn)處的nf鄰居進(jìn)行通信，同時(shí)調(diào)整鄰居節(jié)點(diǎn)功率大小以確保鏈接的雙向性，從而全局連通性得以恢復(fù)。
根據(jù)TRA算法的偽代碼描述，TRA算法的時(shí)間復(fù)雜度與失效節(jié)點(diǎn)的鄰居數(shù)有關(guān)，一般而言，當(dāng)水下傳感器網(wǎng)絡(luò)部署規(guī)模很大時(shí)，鄰居數(shù)可視作log(N)。TRA算法的實(shí)現(xiàn)需要的額外代價(jià)與拓?fù)涫У木唧w情況相關(guān)，若單跳鄰居能夠通過(guò)擴(kuò)大功率自愈，則最大代價(jià)為O((logN)2)；若無(wú)法直接愈合，則需要自移動(dòng)節(jié)點(diǎn)修復(fù)拓?fù)?，此時(shí)代價(jià)與鄰居數(shù)相關(guān)，故TRA算法實(shí)現(xiàn)代價(jià)為log(N)。
4 實(shí)驗(yàn)分析
本文利用OMNeT++[20]平臺(tái)設(shè)計(jì)了一個(gè)仿真程序，程序自上而下由應(yīng)用層、路由層、拓?fù)淇刂坪蚆AC層4個(gè)模塊構(gòu)成，其中路由層采用基于最短路的路由算法FA[21]，拓?fù)淇刂颇K實(shí)現(xiàn)了LMST[13]和拓?fù)溆纤惴═RA。實(shí)驗(yàn)環(huán)境如下：N個(gè)源節(jié)點(diǎn)隨機(jī)均勻散布于600m×600m的正方形區(qū)域，S個(gè)匯聚節(jié)點(diǎn)均勻分布于水平面，源點(diǎn)初始能量為 e，以速率 v（服從正態(tài)分布 v～N(μ,σ2）獲取到興趣數(shù)據(jù)分組。當(dāng)隨機(jī)生成的節(jié)點(diǎn)位置無(wú)法滿足連通則忽略并重新生成節(jié)點(diǎn)位置；不考慮AUV節(jié)點(diǎn)移動(dòng)能耗，當(dāng) AUV節(jié)點(diǎn)遷移愈合網(wǎng)絡(luò)后即視作能量為 e的普通節(jié)點(diǎn)；并且忽略節(jié)點(diǎn)接收?qǐng)?bào)文及處理器的能耗。當(dāng)水下傳感器網(wǎng)絡(luò)滿足以下3個(gè)條件則終止本次仿真：出現(xiàn)失效節(jié)點(diǎn)；失效節(jié)點(diǎn)的鄰居無(wú)法自愈拓?fù)溥B通性； AUV節(jié)點(diǎn)數(shù)量耗盡。用于和TRA算法比較的2種算法分別是：不采用拓?fù)溆系牟呗?，?dāng)節(jié)點(diǎn)出現(xiàn)失效生命期即終止，以下簡(jiǎn)稱NONE算法；愈合拓?fù)鋾r(shí)簡(jiǎn)單地把AUV節(jié)點(diǎn)移至nf，以下簡(jiǎn)稱SIMPLE算法。實(shí)驗(yàn)結(jié)果均為500次的平均值，主要參數(shù)如表1所示。
4.1 實(shí)驗(yàn)1
本實(shí)驗(yàn)通過(guò)不斷改變?cè)垂?jié)點(diǎn)數(shù)N（從100變化至500）的取值，觀察自移動(dòng)節(jié)點(diǎn)數(shù)M（分別為2，4，8，10）的變化對(duì)TRA算法所得到路徑平均時(shí)延和單位時(shí)間節(jié)點(diǎn)平均消耗能量的影響，路徑平均時(shí)延指所有源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)分組過(guò)程中產(chǎn)生時(shí)延的均值，單位時(shí)間節(jié)點(diǎn)平均消耗能量指在整個(gè)網(wǎng)絡(luò)生命期內(nèi)單個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)所產(chǎn)生能耗的單位時(shí)間均值，變化曲線分別如圖4（a）和圖4（b）所示。從圖4可以觀察到以下3個(gè)現(xiàn)象：圖4（a）表明隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)（節(jié)點(diǎn)分布趨于密集）路徑平均時(shí)延出現(xiàn)增長(zhǎng)的趨勢(shì)，這是因?yàn)楫?dāng)源節(jié)點(diǎn)更為密集時(shí)，源節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的路徑上每跳距離會(huì)相對(duì)減小，但總跳數(shù)會(huì)增加，而每跳都需計(jì)入時(shí)延，該因素占據(jù)主導(dǎo)作用，所以造成路徑平均時(shí)延的增長(zhǎng)；圖4（b）顯示隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)單位時(shí)間節(jié)點(diǎn)平均消耗能量會(huì)呈現(xiàn)出逐漸下降趨勢(shì)，這是由于節(jié)點(diǎn)分布密集使得每跳距離減小，而單跳距離減小能使能耗顯著降低，因此節(jié)點(diǎn)進(jìn)行傳輸或轉(zhuǎn)發(fā)時(shí)所產(chǎn)生能耗也將降低；從圖4還不難發(fā)現(xiàn)，當(dāng)自移動(dòng)節(jié)點(diǎn)數(shù)增加時(shí)，路徑平均時(shí)延和節(jié)點(diǎn)平均能耗都會(huì)降低，這是因?yàn)楫?dāng)自移動(dòng)節(jié)點(diǎn)數(shù)增加后，能對(duì)更多失效節(jié)點(diǎn)位置起到優(yōu)化作用，從而將對(duì)全局拓?fù)涓纳破鸬礁鼮槊黠@的影響。
表1 實(shí)驗(yàn)參數(shù)
4.2 實(shí)驗(yàn)2
圖4 源節(jié)點(diǎn)數(shù)和自移動(dòng)節(jié)點(diǎn)數(shù)對(duì)時(shí)延和能耗的影響
圖5 TRA與SIMPLE的平均路徑時(shí)延比較
為了驗(yàn)證TRA算法中計(jì)算Pmove的必要性，本實(shí)驗(yàn)將比較TRA和SIMPLE算法的路徑平均時(shí)延指標(biāo)，曲線如圖5所示。圖5表明TRA算法中把AUV節(jié)點(diǎn)遷移到位置Pmove能夠在一定程度上改善網(wǎng)絡(luò)的時(shí)延指標(biāo)，與SIMPLE相比最高處路徑平均時(shí)延減小了0.15s，因此對(duì)于時(shí)延較為敏感的水下傳感器網(wǎng)絡(luò)應(yīng)用是較為適用的。本實(shí)驗(yàn)還比較算法TRA與SIMPLE的單位時(shí)間節(jié)點(diǎn)平均消耗能量，如圖6所示，圖6反映了采用算法TRA所得到的單位時(shí)間節(jié)點(diǎn)平均能耗一直小于 SIMPLE，此外隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)TRA和SIMPLE的差距在逐步縮小，這是因?yàn)殡S著N增大時(shí)M并未發(fā)生改變，即自移動(dòng)節(jié)點(diǎn)數(shù)所占比重會(huì)逐漸下降，此時(shí)通過(guò)自移動(dòng)節(jié)點(diǎn)遷移來(lái)改善全局拓?fù)涞哪芰?huì)相對(duì)下降。
圖6 節(jié)點(diǎn)平均能耗比較
4.3 實(shí)驗(yàn)3
本實(shí)驗(yàn)通過(guò)改變自移動(dòng)節(jié)點(diǎn)數(shù)量和節(jié)點(diǎn)初始能量，觀察網(wǎng)絡(luò)生命期的變化情況，曲線如圖7所示。圖7印證了自移動(dòng)節(jié)點(diǎn)數(shù)增多和節(jié)點(diǎn)初始能量的增大有助于網(wǎng)絡(luò)生命期的增長(zhǎng)。此外，3條曲線隨著自移動(dòng)節(jié)點(diǎn)數(shù)增長(zhǎng)而生命期增幅呈現(xiàn)出逐步減小的趨勢(shì)，這是因?yàn)樽砸苿?dòng)節(jié)點(diǎn)數(shù)在水下傳感器網(wǎng)絡(luò)中占據(jù)一定比例時(shí)，隨著時(shí)間推移水下傳感器網(wǎng)絡(luò)中會(huì)出現(xiàn)越來(lái)越多的潛在失效節(jié)點(diǎn)（能量趨近于 0的節(jié)點(diǎn)），而自移動(dòng)節(jié)點(diǎn)數(shù)是相對(duì)較小的，無(wú)法愈合所有的潛在局部失效拓?fù)?，因此通過(guò)愈合拓?fù)鋪?lái)延長(zhǎng)生命期的能力受到了制約。本實(shí)驗(yàn)還比較了TRA、NONE與SIMPLE 3種算法的網(wǎng)絡(luò)生命期，如圖8所示，圖8說(shuō)明以下2個(gè)現(xiàn)象：隨著源節(jié)點(diǎn)數(shù)增長(zhǎng)，3條曲線的網(wǎng)絡(luò)生命期都呈現(xiàn)出上升勢(shì)態(tài)，該現(xiàn)象可用實(shí)驗(yàn)1的結(jié)論來(lái)解釋，因?yàn)楫?dāng)源節(jié)點(diǎn)增多時(shí)節(jié)點(diǎn)平均能耗會(huì)降低，所以網(wǎng)絡(luò)生命期會(huì)增長(zhǎng)； TRA和SIMPLE所獲得網(wǎng)絡(luò)生命期遠(yuǎn)高于未采用拓?fù)溆喜呗缘腘ONE算法，另外采用TRA所獲生命期要高于SIMPLE，最高處當(dāng)N=500時(shí)可達(dá)649s。
圖7 自移動(dòng)節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)生命期的影響
圖8 3種算法的網(wǎng)絡(luò)生命期比較
5 結(jié)束語(yǔ)
本文設(shè)計(jì)了一種基于滿 Steiner樹(shù)問(wèn)題的水下傳感器網(wǎng)絡(luò)拓?fù)溆纤惴?TRA。TRA算法適用于時(shí)延敏感的水下無(wú)線傳感器網(wǎng)絡(luò)，并且在自移動(dòng)節(jié)點(diǎn)的遷移位置選取過(guò)程中考慮了高效能耗問(wèn)題。對(duì)于 TRA算法還有著以下幾個(gè)方面的補(bǔ)充和考慮之處：水下環(huán)境一般認(rèn)為是一種三維環(huán)境，TRA算法雖然是基于二維環(huán)境建模，但本文中若干結(jié)論（如定理3等）在三維環(huán)境依然成立，算法設(shè)計(jì)也很容易推廣至三維環(huán)境；水下傳感器網(wǎng)絡(luò)是一個(gè)多模塊組成的復(fù)雜系統(tǒng)，模塊間的協(xié)同是一個(gè)不容忽視的重要問(wèn)題，如何使得拓?fù)溆吓c其他模塊良好協(xié)作也是 TRA應(yīng)繼續(xù)改進(jìn)的方向；此外，水下傳感器網(wǎng)絡(luò)通常部署于惡劣環(huán)境，因此很多理論上的假設(shè)前提未必能得到滿足，例如節(jié)點(diǎn)的移動(dòng)性以及節(jié)點(diǎn)的信號(hào)覆蓋范圍有可能為不規(guī)則圖形，所以 TRA的設(shè)計(jì)還應(yīng)有機(jī)結(jié)合應(yīng)用場(chǎng)景和實(shí)際部署環(huán)境，這樣才具有更高的實(shí)用價(jià)值。
[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor network∶ a survey [J]. Computer Networks, 2002, 38(4)∶393-422.
[2] ELSON J, ESTRIN D. Sensor Networks∶ a Bridge to the Physical World[M]. Norwell∶ Kluwer Academic Publishers, 2004. 3-20.
[3] 崔莉，鞠海玲，苗勇等. 無(wú)線傳感器網(wǎng)絡(luò)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(1)∶163-174.CUI L, JU H L, MIAO Y, et al. Overview of wireless sensor networks[J]. Journal of Computer Research and Development, 2005,42(1)∶163-174.
[4] AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks∶ research challenges[J]. Ad Hoc Networks, 2005, 3(3)∶257-279.
[5] AKYILDIZ I F, POMPILI D, MELODIA T. Challenges for efficient communication in underwater acoustic sensor networks[J]. ACM SIGBED Review, 2004, 1(2)∶ 3-8.
[6] HEIDEMANN J, YE W, WILLS J, et al. Research challenges and applications for underwater sensor networking[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York,2006. 33-40.
[7] AKYILDIZ I F, POMPILI D, MELODIA T. State-of-the-art in protocol research for underwater acoustic sensor networks[A]. Proc of the 1st ACM International Workshop on Underwater Networks[C]. New York, 2006. 7-16.
[8] CHRYSSOSTOMIDIS C. AUV laboratory at MIT sea grant[EB/OL].http∶//auvlab.mit.edu/, 2009.
[9] PETER ?, EDWARD F, NAOMI E L. Cooperative control of mobile sensor networks∶ adaptive gradient climbing in a distributed environment[J]. IEEE Transactions on Automatic Control, 2004, 49(8)∶1292-1302.
[10] IBRAHIM S, CUI J H, AMMAR R. Surface-level gateway deployment for underwater sensor networks[A]. Proc of Military Communications Conference 2007[C]. Sanfrancisco, CA, 2007. 1-7.
[11] CHANG J H, TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2004,12(4)∶ 609-619.
[12] 吳彤. 自組織方法論研究[M]. 北京：清華大學(xué)出版社, 2001.WU T. Self-Organizing Methodology[M]. Beijing∶ Tsinghua University Press, 2001.
[13] LI N, HOU J C, SHA L. Design and analysis of an MST-based topology control algorithm[A]. Proc of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies(INFORCOM 2003)[C]. Sanfrancisco, CA, 2003. 1702-1712.
[14] 越民義. 最小網(wǎng)絡(luò)——斯坦納樹(shù)問(wèn)題[M]. 上?！?上海科學(xué)技術(shù)出版社, 2006.YUE M Y. Minimum Network-Steiner Tree Problem[M]. Shanghai∶Shanghai Science and Technology Press, 2006.
[15] ALSALIH W, AKL S, HASSANEIN H. Placement of multiple mobile data collectors in underwater acoustic sensor networks[A]. Proc of IEEE International Conference on Communications, ICC 2008[C].Beijing, 2008. 19-23.
[16] BORCHERS A, DU D Z. The k-Steiner ratio in graphs[A]. Proc of the Twenty-Seventh Annual ACM Symposium on Theory of Computing[C]. Las Vegas, USA, 1995. 641-649.
[17] MARTINEZ F, PINA J, SOARES J. Algorithm for terminal Steiner trees[J]. Theoretical Computer Science, 2007, 389(1)∶ 133-142.
[18] 劉林峰, 吳家皋, 鄒志強(qiáng)等. 面向節(jié)點(diǎn)失效問(wèn)題的傳感器網(wǎng)絡(luò)拓?fù)渥杂惴╗J]. 東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2009, 39(4)∶695-699.LIU L F, WU J G, ZOU Z Q, et al. Topology control 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.
[19] 徐玖平, 李軍. 多目標(biāo)決策的理論與方法[M]. 北京∶ 清華大學(xué)出版社, 2005.XU J P, LI J. Multi-Objective Decision Theory and Method[M]. Beijing∶ Tsinghua University Press, 2005.
[20] ANDRAS VARGA. OMNeT++ -discrete event simulation system user manual[EB/OL]. http∶//www.omnet.org/, 2008.
[21] CHANG J H, TASSIULAS L. Energy conserving routing in wireless ad-hoc networks[A]. Proc of IEEE INFOCOM [C]. Tel Aviv, Israel,2000. 22-31.
猜你喜歡
網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46
電子制作(2019年23期)2019-02-23 13:21:12
測(cè)控技術(shù)(2018年6期)2018-11-25 09:50:10
大氣科學(xué)學(xué)報(bào)(2017年3期)2017-05-30 10:48:04
汽車(chē)維修技師(2017年10期)2017-03-17 02:25:01
系統(tǒng)工程與電子技術(shù)(2016年7期)2016-08-21 13:59:18
電測(cè)與儀表(2016年17期)2016-04-11 12:38:28
項(xiàng)目管理技術(shù)(2015年10期)2015-12-26 09:36:04
