基于滿Steiner樹問題的水下無線傳感器網(wǎng)絡拓撲愈合算法研究

劉林峰，劉業(yè)

（1. 南京郵電大學 計算機學院，江蘇 南京 210003；2.中國科學技術大學 蘇州研究院，江蘇 蘇州 215123）

1 引言

地球表面71%被人跡罕至的水域（海洋、湖泊、河流）覆蓋，出于科學探索、資源開采、污染監(jiān)控、戰(zhàn)術監(jiān)視或海岸線保護等種種目的，人類對監(jiān)測這些水域一直有著極大的興趣。在無線傳感器網(wǎng)絡[1～3]（WSN, wireless sensor network）被應用之前，水下數(shù)據(jù)的感知和收集工作一般通過有線網(wǎng)絡來完成，這種方式代價高昂并且需要大量工程技術輔助。適合水下環(huán)境的大量傳感器節(jié)點協(xié)同工作，它們隨機分布于監(jiān)測水域，并通過基于聲通信的無線方式自組織構成水下無線傳感器網(wǎng)絡[4～6]（UWSN, underwater wireless sensor network），不僅部署代價相對低廉，而且其分布式結構能夠在水下監(jiān)測應用中展現(xiàn)出更高的靈活度。然而，水下傳感器網(wǎng)絡的設計也面臨著多方面的約束和挑戰(zhàn)，主要表現(xiàn)在鏈接時延明顯且多變、節(jié)點能量有限、帶寬較低、誤碼率高等。此外，水下傳感器節(jié)點極易受到各類外力（如海浪和海風擾動、水下生物觸動等）影響發(fā)生位置遷移，甚至可能因此遭受毀壞，從而導致網(wǎng)絡拓撲變化頻繁、局部網(wǎng)絡失效概率增高，如何愈合局部失效拓撲已成為該領域的研究熱點之一。

部署于水域場景的水下傳感器網(wǎng)絡中應有4種節(jié)點類型：底面節(jié)點、浮游節(jié)點、自移動節(jié)點（AUV,autonomous underwater vehicle）[7]和匯聚節(jié)點，其中底面節(jié)點鋪設于水域底面，由于水域底面地形異常復雜，可能會遭遇障礙地勢而形成通信孤島，該類節(jié)點受水域底面摩擦力影響所以位置遷移幅度較小，浮游節(jié)點依靠浮力裝置懸浮在水中（懸浮深度與水域鹽度、浮力裝置屬性相關），該類節(jié)點受外力擾動而位移的幅度較大，但發(fā)生位移待穩(wěn)定后仍將處于相同懸浮深度的橫切平面上，自移動節(jié)點具備自主的移動能力，能夠按照某種策略進行位移，承擔改善網(wǎng)絡結構和自愈失效拓撲的重要作用。

在傳統(tǒng)WSN中，由于一般不考慮自移動節(jié)點的存在，故通常采用調大節(jié)點功率的方式來愈合失效拓撲，該方式無法改變任何節(jié)點的位置，因此愈合過程很難改善拓撲性質，并極有可能造成拓撲性質惡化。水下傳感器網(wǎng)絡中的AUV節(jié)點具備移動能力，能夠按照特定策略遷移至指定位置替代失效節(jié)點并承擔其原角色，由該類節(jié)點進行的拓撲愈合不僅能夠使得全局拓撲恢復連通性，還能通過改變節(jié)點原有位置的方式來改善全局拓撲，從而具有更高的實用性。目前關于水下傳感器網(wǎng)絡的拓撲愈合研究較為薄弱，多側重于AUV節(jié)點設計或節(jié)點協(xié)作策略的研究，如文獻[8]設計的Odyssey-class AUV能夠到達水域的任意深度，可以修復失效的局部拓撲；文獻[9]提出了一種節(jié)點間協(xié)作控制的網(wǎng)絡管理模式，增強了網(wǎng)絡的健壯性和自適應程度，能夠有效地應對節(jié)點失效情況。然而，AUV節(jié)點遷移至何處才能達到拓撲愈合和拓撲優(yōu)化的雙重目標，該問題尚未見深入研究，尤其對于時延較大的水下環(huán)境，AUV節(jié)點遷移策略的研究將有助于全局拓撲優(yōu)化、網(wǎng)絡傳輸時延降低、能耗效率的提升，因此研究該問題很有必要。本文將針對時延敏感類水下應用（如水域戰(zhàn)術監(jiān)視、污染監(jiān)控等），采用 AUV節(jié)點遷移修復拓撲的策略，提出一種能夠降低傳輸時延和提高能耗效率的拓撲愈合算法。

2 網(wǎng)絡模型及問題描述

2.1 模型構建

在實際應用場景中浮游節(jié)點和底面節(jié)點一般都扮演數(shù)據(jù)感知、采集和傳輸?shù)慕巧虼吮疚膶⒃?種節(jié)點歸為水下傳感器節(jié)點。假定有S個匯聚節(jié)點、N個水下傳感器節(jié)點和M個自移動節(jié)點隨機均勻散布于監(jiān)測水域，其中水下傳感器節(jié)點攜帶有限能量的電池。水下傳感器節(jié)點能夠感知并發(fā)送監(jiān)測所得數(shù)據(jù)，同時根據(jù)網(wǎng)絡拓撲為當前傳輸轄域內的鄰居節(jié)點提供報文接收和轉發(fā)服務，隨著數(shù)據(jù)流量的經(jīng)由，節(jié)點的無線收發(fā)能耗和通信模塊的閑時開銷使得電池能量不斷降低。初始工作狀態(tài)時水下傳感器網(wǎng)絡由水下傳感器節(jié)點保持全局連通，隨后節(jié)點可能由于能量耗盡、外力作用等復雜因素而導致失效，就需要自移動節(jié)點來愈合拓撲。

抽象水下傳感器網(wǎng)絡拓撲為一個權重圖G(V,E)，其中 V、E分別表示節(jié)點、鏈接的集合，V={n0, …, nS-1, nS, …, nS+N-1, nS+N, …, nS+N+M-1}，n0, …, nS-1表示匯聚節(jié)點，nS, …, nS+N-1表示N個水下傳感器節(jié)點，nS+N, …, nS+N+M-1表示M個自移動節(jié)點；標記節(jié)點 ni的鄰居集合為 Neighbor(ni)，數(shù)量為N(ni)；失效節(jié)點記作nf，替代該節(jié)點的自移動節(jié)點記作nAUV；對于任意i∈[S, S+N+M-1]，節(jié)點ni的當前能量記作e(ni)，節(jié)點ni的當前覆蓋半徑記作radius(ni)，所有節(jié)點擁有相同的最大傳輸范圍R；節(jié)點ni的最大覆蓋區(qū)域可以表示為cover(ni)={ nj| d(i,j)≤R and nj∈IR2}；定義網(wǎng)絡連通函數(shù)connectivity(G)∶ G(V,E)→X，X為布爾邏輯數(shù)集合。若節(jié)點ni和nj之間存在通信鏈接則記作(i,j)∈E，鏈接(i,j)的距離記作 d(i,j)，其上時延記作 delay(i,j)，delay(i,j)[10]表示為式（1）所示形式。

其中，L表示數(shù)據(jù)分組大小，B表示數(shù)據(jù)傳輸率，Vp為水下聲波傳輸速率。鏈接(i,j)上的能耗記作cost(i,j)如式（2）所示。

其中，ω為常系數(shù)，α為能量衰減指數(shù)，當在惡劣通信環(huán)境中或有障礙物時較大，據(jù)實驗統(tǒng)計數(shù)據(jù)一般有α≥2。為便于模型的分析和描述，本文還給出如下假設：

假設 1 傳感器節(jié)點的天線以全方位廣播方式進行通信，且通信鏈接具有對稱性；

假設 2 水下傳感器網(wǎng)絡的部署獲得定位系統(tǒng)（如GPS）的輔助, 每個節(jié)點均獲知自己及其鄰居的地理位置；

假設 3 匯聚節(jié)點能量為+∞，自移動節(jié)點因位置移動發(fā)生的能耗忽略不計；

假設 4 節(jié)點發(fā)生失效前水下傳感器網(wǎng)絡拓撲已經(jīng)為近似最優(yōu)結構；

假設5 M＜＜N，因代價較高所以水下傳感器網(wǎng)絡中可供部署的自移動節(jié)點數(shù)量一般認為很少；

假設6 水下傳感器網(wǎng)絡的生命期[11]定義為在傳感器網(wǎng)絡系統(tǒng)的流量路由過程中，最先因電池能量耗盡而失效的節(jié)點生命期。

2.2 問題描述

當有節(jié)點發(fā)生失效后，拓撲結構可能不再滿足全局連通性，此時應由自移動節(jié)點替代已失效的節(jié)點，與失效節(jié)點的單跳鄰居連接，從而實現(xiàn)拓撲的重新愈合。水下傳感器網(wǎng)絡拓撲控制中時延和能耗是2個應予以首要關注的因素，因此當AUV節(jié)點愈合拓撲時也必須考慮這2個因素。就該問題而言，扮演替代角色的自移動節(jié)點的位置選取至關重要，自移動節(jié)點的遷移行為不僅能夠恢復受損拓撲，更能改善受損拓撲的時延和能耗特性，故不應簡單地讓AUV節(jié)點遷移至失效節(jié)點位置，而應重新權衡并選取更為合適的位置，因此水下傳感器網(wǎng)絡拓撲愈合問題可歸結為最優(yōu)化網(wǎng)絡拓撲的AUV節(jié)點位置選取問題。然而最優(yōu)化全局拓撲需要網(wǎng)絡尺度上的拓撲信息交互，這對于水下傳感器網(wǎng)絡而言是難以承受和異常復雜的。因水下傳感器網(wǎng)絡屬于一種自組織網(wǎng)絡，自組織理論[12]觀點認為全局優(yōu)化目標可以通過局部優(yōu)化的疊加來實現(xiàn)（如基于局部視角的拓撲控制算法 LMST[13]），從而該問題可以近似地簡化為通過選擇AUV節(jié)點遷移位置來優(yōu)化局部失效拓撲。位置選取問題可以映射到斯坦納最小樹(SMT, Steiner minimum tree)[14]問題，SMT問題尋求若干個Steiner點，使得與給定節(jié)點相連后能夠生成最小連通網(wǎng)絡。結合水下環(huán)境特點和水下傳感器網(wǎng)絡的設計目標，AUV節(jié)點的遷移位置選取需要考慮3項目標：恢復受損拓撲的連通性，愈合后局部拓撲的通信時延較小，愈合后局部拓撲的通信能耗較低。此外，由于水下傳感器網(wǎng)絡中匯聚節(jié)點是數(shù)據(jù)接收的終點，據(jù)定理1可知接近匯聚節(jié)點的傳感器節(jié)點承擔較多的通信負載，因此，AUV節(jié)點還應當偏向遷移至接近匯聚節(jié)點的位置，以分流部分通信負載，實現(xiàn)網(wǎng)絡系統(tǒng)負載均衡的目的。這在 SMT問題中可以通過設置權重參數(shù)方式來進行調節(jié)，即賦予距匯聚節(jié)點近的鄰居節(jié)點較高權重。

定理 1 在節(jié)點均勻分布的情況下，層次較低的節(jié)點可能承擔的流量負載期望值較大。

證明 考慮匯聚節(jié)點唯一或多個[15]的情況，S=1時和S＞＞1時層次劃分示意如圖1所示，k表示節(jié)點所處的層次。

圖1 水下傳感器網(wǎng)絡層次劃分

不妨設水下傳感器網(wǎng)絡部署于 A×A的方形區(qū)域，采用節(jié)點可能需要提供直接轉發(fā)或間接轉發(fā)服務的節(jié)點數(shù)作為衡量負載期望值的指標，一般情況下可以視作第k層節(jié)點為第k+1及更高層節(jié)點提供轉發(fā)服務。下面分別針對S=1和S＞＞1情況進行討論。

1) 當S=1時，第k層節(jié)點所需承擔負載的節(jié)點數(shù)期望值E(k)表示為式（3）所示。

2) 當S＞＞1時，第k層節(jié)點所需承擔負載的節(jié)點數(shù)期望值E(k)表示為式（4）所示。

無論式（3）或式（4）中，k較小時E(k)較大，因此定理1得證。

連通性是傳感器網(wǎng)絡的獲取并傳輸數(shù)據(jù)的基本要求，由于水下聲通信的特性，水下傳感器網(wǎng)絡中傳輸時延和能耗要明顯高于陸地部署的傳感器網(wǎng)絡，故本文將連通性、傳輸時延、傳輸能耗作為問題求解的主要目標。當理想情況下，所有節(jié)點的L、B和Vp都為相同的固定值，水下傳感器網(wǎng)絡拓撲失效的愈合目標obj可表述為如下目標：

目標1 connectivity(G)=1

目標2

目標3

目標2～目標3中ak、bk表示SMT中鏈接的權重，nu表示失效節(jié)點nf的鄰居節(jié)點，k表示nu所屬的層數(shù)。根據(jù)定理 1結論權重系數(shù)的設置應滿足ak+1≤ak≤ak-1，bk+1≤bk≤bk-1。依據(jù)水下傳感器網(wǎng)絡的真實部署特點，水下傳感器網(wǎng)絡的拓撲愈合問題是一種特殊的SMT問題，主要表現(xiàn)在如下約束：

約束1 傳統(tǒng)SMT問題只具有一個最小網(wǎng)絡目標，而本研究中需兼顧時延和能耗2種因素，并且Neighbor(nf)在優(yōu)化后均為SMT的葉節(jié)點，從而該問題演化為一種攜帶多目標的滿Steiner樹[16]；

約束2 廣義上的SMT可能會選取多個Steiner點作為網(wǎng)絡連接者，但是據(jù)假設5可知水下傳感器網(wǎng)絡中AUV數(shù)量極少，故在單次愈合拓撲時僅考慮使用一個AUV的情況；

約束3 為滿足網(wǎng)絡連通目標，AUV必須位于nf鄰居的覆蓋交集區(qū)域內。

綜上分析，水下傳感器網(wǎng)絡拓撲愈合問題的一般形式化描述可歸結為問題1。

問題 1 給定水下傳感器網(wǎng)絡拓撲對應的無向圖 G(V,E)和一個可行的優(yōu)化目標 obj，當出現(xiàn)節(jié)點nf發(fā)生失效后，由一個 AUV節(jié)點遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得Neighbor(nf)∪nf生成一棵滿 Steiner樹，并且該滿Steiner樹能符合目標1～目標3。

3 問題轉化及近似算法

3.1 問題轉化

滿Steiner樹問題難以對多目標進行優(yōu)化，為了綜合考慮目標2和目標3，本文提出一種描述節(jié)點ni和nj間時延和能耗的綜合權值參數(shù)w(i,j)，給出其元素w(i,j)啟發(fā)式的定義，如式（5）所示。

其中，β、γ為預設指數(shù)，權值 w(i,j)由 delay(i,j)和cost(i,j)2部分決定，由于 delay(i,j)和 cost(i,j)都與d(i,j)相關，且 L、B都為常量，故最終近似作w(i,j)∝d(i,j)δ（δ≥1）。此時問題1可以轉化為問題2。

問題2 節(jié)點nf發(fā)生失效后，由一個AUV節(jié)點遷移至位置Pmove∩∈cover(nu)（其中nu∈Neighbor(nf)），使得ckw(u,AUV)最小，其中ck+1≤ck≤ck-1，k表示nu所屬層數(shù)。

定理2 問題2是個NP-hard問題。

證明 滿 Steiner樹問題已被證明是一個 NP-完全問題[17]，問題2可以視作滿Steiner樹問題的一種特例，因此易證問題1也是一個NP-完全問題。

3.2 近似算法

為解決問題 2，本文設計了一種水下傳感器網(wǎng)絡拓撲愈合算法 TRA(topology recovery algorithm of underwater sensor network)。TRA算法的主要思想是：首先為所有 nu∈Neighbor(nf)在∩cover(nu)域內映射到各自的最優(yōu) Steiner位置（記作Steiner(nu)），再對各Steiner點使用質心量算方法獲得近似最優(yōu)解 Pmove。TRA算法具體按照如下步驟1～步驟5進行。

步驟1 當nf失效后，判斷nu∈Neighbor(nf)之間是否能夠恢復連通，如能則采用TCS-CA算法[18]恢復連通性，否則轉至步驟2。

步驟2 計算∩cover(nu)（如圖2（a）所示陰影部分區(qū)域），若∩cover(nu)域為一個點，令AUV節(jié)點遷移至nf，否則轉至步驟3。

步驟3 依據(jù)式（6）從nf的鄰居節(jié)點分別映射至交集區(qū)域（如圖 2（b）所示），令映射點所屬層次與鄰居節(jié)點一致，轉至步驟4。

Steiner(nu) = { P| P∈∩cover(nu) & min(w(u,P))} (6)其中，w(u,P)表示節(jié)點nu與位置P間的權值。

圖2 TRA算法

步驟 4 賦予較低層次鄰居的映射點以較高的權重參數(shù)，采用質心量算方法計算近似最優(yōu)位置Pmove，Pmove的表達式如式（7）所示。將 AUV節(jié)點移至Pmove，轉至步驟5。

其中，du表示鄰居nu所對應映射點的權值，nu所屬層數(shù)越小則權值越大，并對權值進行了歸一化處理，即令根據(jù)步驟 1～步驟 4描述，有定理3成立。

定理3 Pmove必在∩cover(nu)域內。

證明 ∩cover(nu)是 N(nf)個半徑為 R 圓的交集，Steiner位置都位于∩cover(nu)域的邊界，按照逆時針（或順時針）順序連接各Steiner位置，生成的多邊形為凸多邊形，可以證明每個內角均小于π。角度大小由連續(xù)3個點位置決定，因此該結論可以分以下3種情況進行討論。

情況1 連續(xù)的3點在同一圓弧上，此時該角必小于π。

情況2 3點位于2條不同圓弧上。不妨設點A、B位于同一圓弧，點 C位于另一圓弧，假設∠ABC≥π，如圖3（a）所示。此時顯然有|CO|＞R，根據(jù)∩cover(nu)定義可知應有|CO|≤R，故不可能出現(xiàn)∠ABC≥π。

圖3 凸多邊形的內角生成情況

情況3 3點位于3條不同圓弧上。如圖3（b）所示，假定A、B分別位于2條圓弧，則根據(jù)∩cover(nu)定義和多邊形生成順序可知點C必定位于圖中陰影區(qū)域，BC’為圓弧在 B點處切線，因此有∠ABC＜∠ABC’＜π。

所以，生成的多邊形中所有內角均小于 π，該多邊形為凸多邊形。凸多邊形內所有點構成的點集合是一個凸集，凸集具有如下性質[19]：設X為向量空間，集合S?X是凸集，當且僅當任意xi∈Set，yi≥0，及，i=1,2,…,n，有成立。據(jù)該性質及式（7），因 Steiner(nu)為多邊形頂點，屬于該凸多邊形集合，故 Pmove必在凸多邊形內部，定理3得證。

步驟5 AUV節(jié)點通過設置自身功率，以確保能與最遠處的nf鄰居進行通信，同時調整鄰居節(jié)點功率大小以確保鏈接的雙向性，從而全局連通性得以恢復。

根據(jù)TRA算法的偽代碼描述，TRA算法的時間復雜度與失效節(jié)點的鄰居數(shù)有關，一般而言，當水下傳感器網(wǎng)絡部署規(guī)模很大時，鄰居數(shù)可視作log(N)。TRA算法的實現(xiàn)需要的額外代價與拓撲失效的具體情況相關，若單跳鄰居能夠通過擴大功率自愈，則最大代價為O((logN)2)；若無法直接愈合，則需要自移動節(jié)點修復拓撲，此時代價與鄰居數(shù)相關，故TRA算法實現(xiàn)代價為log(N)。

4 實驗分析

本文利用OMNeT++[20]平臺設計了一個仿真程序，程序自上而下由應用層、路由層、拓撲控制和MAC層4個模塊構成，其中路由層采用基于最短路的路由算法FA[21]，拓撲控制模塊實現(xiàn)了LMST[13]和拓撲愈合算法TRA。實驗環(huán)境如下：N個源節(jié)點隨機均勻散布于600m×600m的正方形區(qū)域，S個匯聚節(jié)點均勻分布于水平面，源點初始能量為 e，以速率 v（服從正態(tài)分布 v～N(μ,σ2）獲取到興趣數(shù)據(jù)分組。當隨機生成的節(jié)點位置無法滿足連通則忽略并重新生成節(jié)點位置；不考慮AUV節(jié)點移動能耗，當 AUV節(jié)點遷移愈合網(wǎng)絡后即視作能量為 e的普通節(jié)點；并且忽略節(jié)點接收報文及處理器的能耗。當水下傳感器網(wǎng)絡滿足以下3個條件則終止本次仿真：出現(xiàn)失效節(jié)點；失效節(jié)點的鄰居無法自愈拓撲連通性； AUV節(jié)點數(shù)量耗盡。用于和TRA算法比較的2種算法分別是：不采用拓撲愈合的策略，當節(jié)點出現(xiàn)失效生命期即終止，以下簡稱NONE算法；愈合拓撲時簡單地把AUV節(jié)點移至nf，以下簡稱SIMPLE算法。實驗結果均為500次的平均值，主要參數(shù)如表1所示。

4.1 實驗1

本實驗通過不斷改變源節(jié)點數(shù)N（從100變化至500）的取值，觀察自移動節(jié)點數(shù)M（分別為2，4，8，10）的變化對TRA算法所得到路徑平均時延和單位時間節(jié)點平均消耗能量的影響，路徑平均時延指所有源節(jié)點到匯聚節(jié)點發(fā)送數(shù)據(jù)分組過程中產生時延的均值，單位時間節(jié)點平均消耗能量指在整個網(wǎng)絡生命期內單個節(jié)點傳輸數(shù)據(jù)所產生能耗的單位時間均值，變化曲線分別如圖4（a）和圖4（b）所示。從圖4可以觀察到以下3個現(xiàn)象：圖4（a）表明隨著源節(jié)點數(shù)增長（節(jié)點分布趨于密集）路徑平均時延出現(xiàn)增長的趨勢，這是因為當源節(jié)點更為密集時，源節(jié)點到匯聚節(jié)點的路徑上每跳距離會相對減小，但總跳數(shù)會增加，而每跳都需計入時延，該因素占據(jù)主導作用，所以造成路徑平均時延的增長；圖4（b）顯示隨著源節(jié)點數(shù)增長單位時間節(jié)點平均消耗能量會呈現(xiàn)出逐漸下降趨勢，這是由于節(jié)點分布密集使得每跳距離減小，而單跳距離減小能使能耗顯著降低，因此節(jié)點進行傳輸或轉發(fā)時所產生能耗也將降低；從圖4還不難發(fā)現(xiàn)，當自移動節(jié)點數(shù)增加時，路徑平均時延和節(jié)點平均能耗都會降低，這是因為當自移動節(jié)點數(shù)增加后，能對更多失效節(jié)點位置起到優(yōu)化作用，從而將對全局拓撲改善起到更為明顯的影響。

表1 實驗參數(shù)

4.2 實驗2

圖4 源節(jié)點數(shù)和自移動節(jié)點數(shù)對時延和能耗的影響

圖5 TRA與SIMPLE的平均路徑時延比較

為了驗證TRA算法中計算Pmove的必要性，本實驗將比較TRA和SIMPLE算法的路徑平均時延指標，曲線如圖5所示。圖5表明TRA算法中把AUV節(jié)點遷移到位置Pmove能夠在一定程度上改善網(wǎng)絡的時延指標，與SIMPLE相比最高處路徑平均時延減小了0.15s，因此對于時延較為敏感的水下傳感器網(wǎng)絡應用是較為適用的。本實驗還比較算法TRA與SIMPLE的單位時間節(jié)點平均消耗能量，如圖6所示，圖6反映了采用算法TRA所得到的單位時間節(jié)點平均能耗一直小于 SIMPLE，此外隨著源節(jié)點數(shù)增長TRA和SIMPLE的差距在逐步縮小，這是因為隨著N增大時M并未發(fā)生改變，即自移動節(jié)點數(shù)所占比重會逐漸下降，此時通過自移動節(jié)點遷移來改善全局拓撲的能力將會相對下降。

圖6 節(jié)點平均能耗比較

4.3 實驗3

本實驗通過改變自移動節(jié)點數(shù)量和節(jié)點初始能量，觀察網(wǎng)絡生命期的變化情況，曲線如圖7所示。圖7印證了自移動節(jié)點數(shù)增多和節(jié)點初始能量的增大有助于網(wǎng)絡生命期的增長。此外，3條曲線隨著自移動節(jié)點數(shù)增長而生命期增幅呈現(xiàn)出逐步減小的趨勢，這是因為自移動節(jié)點數(shù)在水下傳感器網(wǎng)絡中占據(jù)一定比例時，隨著時間推移水下傳感器網(wǎng)絡中會出現(xiàn)越來越多的潛在失效節(jié)點（能量趨近于 0的節(jié)點），而自移動節(jié)點數(shù)是相對較小的，無法愈合所有的潛在局部失效拓撲，因此通過愈合拓撲來延長生命期的能力受到了制約。本實驗還比較了TRA、NONE與SIMPLE 3種算法的網(wǎng)絡生命期，如圖8所示，圖8說明以下2個現(xiàn)象：隨著源節(jié)點數(shù)增長，3條曲線的網(wǎng)絡生命期都呈現(xiàn)出上升勢態(tài)，該現(xiàn)象可用實驗1的結論來解釋，因為當源節(jié)點增多時節(jié)點平均能耗會降低，所以網(wǎng)絡生命期會增長； TRA和SIMPLE所獲得網(wǎng)絡生命期遠高于未采用拓撲愈合策略的NONE算法，另外采用TRA所獲生命期要高于SIMPLE，最高處當N=500時可達649s。

圖7 自移動節(jié)點數(shù)對網(wǎng)絡生命期的影響

圖8 3種算法的網(wǎng)絡生命期比較

5 結束語

本文設計了一種基于滿 Steiner樹問題的水下傳感器網(wǎng)絡拓撲愈合算法 TRA。TRA算法適用于時延敏感的水下無線傳感器網(wǎng)絡，并且在自移動節(jié)點的遷移位置選取過程中考慮了高效能耗問題。對于 TRA算法還有著以下幾個方面的補充和考慮之處：水下環(huán)境一般認為是一種三維環(huán)境，TRA算法雖然是基于二維環(huán)境建模，但本文中若干結論（如定理3等）在三維環(huán)境依然成立，算法設計也很容易推廣至三維環(huán)境；水下傳感器網(wǎng)絡是一個多模塊組成的復雜系統(tǒng)，模塊間的協(xié)同是一個不容忽視的重要問題，如何使得拓撲愈合與其他模塊良好協(xié)作也是 TRA應繼續(xù)改進的方向；此外，水下傳感器網(wǎng)絡通常部署于惡劣環(huán)境，因此很多理論上的假設前提未必能得到滿足，例如節(jié)點的移動性以及節(jié)點的信號覆蓋范圍有可能為不規(guī)則圖形，所以 TRA的設計還應有機結合應用場景和實際部署環(huán)境，這樣才具有更高的實用價值。

[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ǎng)絡研究進展[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]. 北京：清華大學出版社, 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)絡——斯坦納樹問題[M]. 上海∶ 上海科學技術出版社, 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] 劉林峰, 吳家皋, 鄒志強等. 面向節(jié)點失效問題的傳感器網(wǎng)絡拓撲自愈算法[J]. 東南大學學報（自然科學版），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] 徐玖平, 李軍. 多目標決策的理論與方法[M]. 北京∶ 清華大學出版社, 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.