有限馬爾可夫鏈的水聲傳感器網絡協作中繼算法

潘志宏，萬智萍，謝海明

1.中山大學 新華學院，廣州 510520

2.廣東移動通信有限責任公司 茂名分公司，廣東 茂名 525000

水下傳感器網絡（Underwater Wireless Sensor Network，UWSN）是一種針對水下傳播特性，采用水聲傳感器節點所組成的水下環境多跳自組織網絡[1-3]，由于水下復雜的環境使得電磁波在水下的應用得到限制，因此在水下采用聲波進行數據傳播是目前廣泛應用的水下通訊方法[4-5]。水下傳感器網絡在海洋資源開發、海洋生態環境保護、航線探索等方面都具有重要應用，早在20世紀90年代，DSP（Digital Signal Processing）芯片及數字通信技術的問世，為水下傳感器網絡的發展奠定了基礎[6]。經過多年的發展，水下傳感器網絡在節點硬件設計和通信算法上得到了更多的改良，然而噪聲高、傳輸速率低、帶寬窄等水下信道特性使得水下通信存在誤碼率高、延遲嚴重等諸多問題。而且由于水下復雜的傳播環境使得水聲節點更換電池設備的難度大，成本高，因此如何有效延長水聲節點有限的工作壽命也成為研究水下傳感器網絡的重要難題[7-8]。

為了解決水下傳感器網絡誤碼率高及能耗大等問題，國內外的專家學者通過開展研究提出了不同的解決方法。張穎等[9]提出一種基于深度和能量的水下三維傳感器網絡分簇路由算法，該算法中繼節點的選擇考慮了水下傳輸特性和能量問題，有效地均衡網絡能耗，延長網絡正常工作輪數。蔣鵬等[10]提出一種基于分簇的水下傳感器網絡覆蓋保持路由算法，簇首間通信時父節點中覆蓋冗余度最高的簇首作為其下一跳路由,對簇內成員采集的數據融合處理后通過時分多址技術多跳路由至Sink節點，能降低網絡能耗，延長網絡生命周期。水下分簇路由雖然減少了節點的平均傳輸能耗，但無法降低節點傳輸數據的平均誤碼率。王慶文等[11]提出一種水下無線傳感器網絡自適應轉發協議，采用自適應概率的方法，傾向于轉發區域內與上一跳節點距離遠和與源節點和目的節點方向矢量距離近的節點轉發分組，從而提高了轉發效率。Yu等[12]提出一種水下傳感器網絡自適應路由協議，該協議通過逐漸改變節點的跳距離來保證傳輸的可靠性，并自適應調整節點的發射功率來提高網絡的能量效率。但基于最短距離的自適應傳輸協議沒有考慮傳輸誤碼率的問題。Javaid等[13]提出一種水下傳感器網絡增強型能源平衡數據傳輸協議，該協議采用能量級來提升節點能量負載均衡性能，通過采用閾值的方法減少匯聚節點數量并消除重復傳輸數據的節點，延長網絡的生命周期。該方法雖然通過減少重傳節點來節省能量，但由于水下傳輸特性的影響，節點存在一定的誤碼率，需要通過重傳來確保終端正確接收數據，盲目減少重傳節點會影響傳輸質量。

由于水下網絡多跳自組織的傳輸特性，某些節點既需要負責數據采集任務，同時又負擔起了中繼轉發的職責，具有較重的能量負擔。為了優先確保采集的數據能夠成功傳輸至目的節點，本文基于能量策略提出了中轉節點的概念，使得中轉節點在剩余能量不足的情況下優先承擔起中繼職責，從而提升網絡的傳輸效率。為了降低誤碼率及提升網絡的生命周期，本文基于馬爾可夫鏈進行協作節點的狀態分析，并以協作節點狀態評價函數來選擇最佳中繼。

1 基于馬爾可夫鏈狀態空間的協作節點狀態分析

對于水下無線傳感器網絡場景，本文假設水下環境是一個三維的監測區域，水聲節點隨機分布于監測區域中。由于受到水下浮游生物等環境介質的影響，水聲節點發送的信號只能傳播一段距離，這里表示為節點的通信半徑，水聲節點采用多跳的方式互相傳遞數據，節點都具有收發數據的功能[5，14]。水下監測區域設有一個基站，水聲節點負責采集數據并發送到目標基站。由于水下傳感器網絡的多跳特性決定了某些節點會充當中繼節點，對其他節點的數據進行協作傳輸，同時這些中繼節點可能還承擔著數據采集任務，具有較重的能量負擔。因此根據能量負載情況，本文將水聲節點分為三類，分別為數據采集節點、中繼節點和中轉節點，如圖1所示。數據采集節點只負責采集數據并將數據發送給鄰居節點，該類節點遠離基站，中繼節點包含了數據采集節點的任務，同時還需要協作其他節點傳輸數據，而中轉節點不采集數據，只負責協助其他節點傳輸數據，這是由于該類節點能量較低，需要優先保證鏈路暢通，延長網絡的工作壽命，哪些節點作為中轉節點將在本文的能量策略中進行討論。其中，為了便于文中討論，根據中繼節點和中轉節點的協作特性，將這兩類節點歸于協作節點這個大類，水下傳感器網絡中的所有協作節點采用集合χ={ }x1,x2,…,xm表示。

圖1 水下數據傳輸二維平面分析圖

對于通信過程中協作節點的信道狀態變化，假設數據采集節點從收集數據，再通過協作節點的幫助傳輸數據至目的節點的這個通信過程可以劃分為T個時隙。其中這T個時隙中包含了中繼通信（數據采集節點與協作節點通信）時隙及中繼協作（協作節點與基站通信）時隙。在中繼通信時隙中，數據采集節點將收集到的數據轉發給協作節點。對于該過程中數據采集節點與協作節點之間的無線信道質量，可以根據協作節點的誤碼率（Symbol Error Rate，SER）進行衡量，因此本文采用有限狀態馬爾科夫鏈（Markov Chain，MC）分析協作節點的SER狀態轉移概率。假設數據采集節點與協作節點之間的無線信道有V個狀態，采用H={h1,h2,…,hV}來表示協作節點誤碼率的馬爾可夫鏈狀態空間，協作節點xi(xi∈χ)在時隙tw(tw∈t)中的接收誤碼率用SERxi(tw)表示，假設協作節點的誤碼率從狀態C1向狀態C2轉移，則協作節點SER的狀態轉移概率表示為：

而在中繼協作時隙，協作節點將數據轉發至目的基站，此時協作節點狀態發生變化的主要是自身的剩余能量。這是由于水下復雜的傳播環境加快了水聲協作節點的能量損耗，協作節點的剩余能量狀態會不斷發生變化，直至耗盡能源。對于協作節點剩余能量狀態的分析，本文假設協作節點的剩余能量有P個狀態，采用En={E1,E2,…,EP}表示，在時隙tq(tq∈t)協作節點的剩余能量本文采用Exi(tq)表示，采用ζa,b(t)表示Exi(tq)從狀態a向狀態b轉移的概率：

2 協作中繼算法

本文提出的中繼協作算法，首先采用一種能量策略的方法來進行中轉節點判定，使剩余能量較少的中轉節點優先負責數據協作轉發任務，確保網絡數據傳輸路由的正常運作。在確定節點所承擔的任務之后，根據馬爾可夫鏈狀態空間所分析的協作節點信道狀態和能量狀態轉移概率，提出協作節點狀態評價函數，節點會將傳播半徑內具有最大評價值的鄰居節點作為下一跳節點。

在t個時隙內對水下傳感器網絡采用基于馬爾可夫模型進行協作節點狀態分析，可以得到中繼通信時的協作節點信道狀態SERxm()t和協作通信時的剩余能量狀態Exi()

t，通過協作節點的這二大狀態，本文可以采取一種協作節點狀態評價函數來為數據采集節點選擇最佳中繼。在提出該方法之前，考慮到協作節點的剩余能量情況，為了保證水下監測范圍內的數據采集節點所收集到的信息能夠被順利傳輸到基站，剩余能量不足的協作節點需要放棄數據采集任務，充當中轉節點的角色。因此，本文在提出最佳中繼的選擇策略之前，先提出了一種基于能量策略的中轉節點判定方法。

2.1 基于能量策略的中轉節點判定方法

假設協作節點xi與基站xBS的距離為d(xi,xBS)，本文采用三維空間的極坐標(ρ,φ,θ)計算xi與xBS的歐幾里德距離：

協作節點 xi在to時刻采集到的數據量假設為Ωxi(to)，需要協作轉發數據量為(to)，則節點 xi成功將數據傳輸至基站所需要消耗的能量為：

其中ex表示單位數據每米的傳輸能耗，(1 -SERxi(t))是考慮到水下傳輸環境存在較高的誤碼率，因此包含了較多的重傳能耗。令Exi(to)表示在to時刻節點xi的剩余能量，決定協作節點是否作為中轉節點取決于Exi(to)與Ec(xi)的比較關系，當Exi(to)≤Ec(xi)，則該協作節點xi放棄采集數據，充當中轉節點。通過該能量策略，防止協作節點xi在將數據傳輸至基站前耗盡自身能量，至少保障了數據采集節點的數據能夠成功到達基站。

2.2 基于最佳中繼選擇的協作節點狀態評價函數

在水下傳感器網絡中，由于節點的傳播半徑有限，不僅是遠離基站的數據采集節點需要選擇協作節點助其轉發數據，與基站的距離間隔大于傳播半徑的協作節點同樣需要其他協作節點的協助。考慮到中繼信道的誤碼率及中繼點的剩余能量決定了數據能否成功轉發至基站，因此，在為節點選擇最佳的下一跳協作點時，誤碼率及傳輸能耗成為了重要的評價標準。

假設水下網絡中有一節點xi，需要轉發Ωxi(t)的數據量至目的節點，xj是xi傳播半徑內的鄰居節點，因此是候選的中繼點。如果在t時刻xj被確定當選為最佳中繼點，則此時xj的信道狀態為SERxj(t)，剩余能量狀態為Exj(t)。在t+1時刻協作節點xj將數據傳輸出去，此時的信道狀態為SERxj(t +1)，剩余能量狀態為Exj(t +1)。則對于候選節點xj，本文所提出的協作節點狀態評價函數為：

其中

根據公式（5），節點xi會對傳播半徑內協作節點的狀態評價函數結果進行比較，選擇函數值最大的協作節點作為最佳的下一跳節點。該協作中繼算法的主要流程如下：

（1）基于馬爾可夫鏈狀態空間進行協作節點狀態分析，根據公式（1）和公式（2）計算能量狀態轉移概率。

（2）根據公式（4）計算中轉節點的能量判定閾值Ec(xi)，比較協作節點的剩余能量與Ec(xi)之間的大小，當小于Ec(xi)時，該協作節點充當中轉節點。

（3）根據公式（5）計算節點傳播半徑內協作節點的狀態評價函數，評價值最大的節點將被作為下一跳節點。

2.3 計算復雜度分析

在本文算法中，首先進行中轉節點判定，根據公式（4），假設計算一個節點傳輸能耗所需要的計算時間為t1，需要判定網絡中的n個節點，因此所需的計算時間為n×t1。接著根據公式（5）計算一個協作節點的評價值，假設計算時間為t2，某一節點的鄰居節點有m個，則所需的計算時間為m×t2，進行評價值最大值比較所需的時間假設為t3。則算法計算時間總開銷為：n×t1+m×t2+t3，計算復雜度則為O()N。

3 實驗結果及分析

為了驗證本文提出的基于有限馬爾可夫鏈的水聲傳感器網絡協作中繼算法的有效性，在仿真實驗部分，本文采用NS2仿真工具，在硬件配置為Intel酷睿i7 6700，主頻3.4 GHz，內存4 GB，操作系統為Windows7的PC機上對算法進行了編程仿真。為了更好地說明本文算法的性能，在實驗過程中本文采用文獻[13]提出的水下傳感器網絡增強型能源平衡數據傳輸協議與文獻[12]提出的水下傳感器網絡自適應路由協議作為對比算法，與本文算法在同一環境下進行仿真實驗，并對實驗結果進行比較分析。

模擬水下監測環境的范圍為1 000 m×1 000 m×1 000 m，水下設定一個固定基站，其他傳感器節點在監測環境內隨機分布，并且節點數量的取值范圍設定為[1 0 0,400]。傳感器節點采用聲波進行通信，節點都具有采集環境數據，以及收發數據的功能。水下網絡的其他實驗參數如表1所示。

表1 水下傳感器網絡參數表

數據包成功投遞率指目的基站最終收到的數據包數量與源節點發送的數據包數量之間的比值，數據包成功投遞率越大，意味著傳輸過程中出現丟包的概率越小，網絡的傳輸性能越好。為了驗證本文算法在提升水下傳感器網絡數據包成功投遞率上的有效性，在逐漸增加節點數量的情況下，本文記錄了實驗過程中各算法的數據包成功投遞率，得到了圖2的結果。從圖2可以看出，本文算法的數據包成功投遞率高于文獻[12]和文獻[13]的算法，文獻[13]提出的增強型能源平衡數據傳輸協議對誤碼率并沒有起到較好的控制效果，而文獻[12]提出的自適應路由協議雖然通過控制節點的跳距離來確保數據得到及時轉發，但是該協議并沒有專注于無線信道質量。而本文算法將誤碼率作為最佳中繼選擇的一個重要的評價標準，因此選擇的中繼節點在傳輸數據包時具有較高的成功率。

圖2 數據包成功投遞率

圖3顯示了在逐漸增加節點數量的條件下網絡的能量消耗情況，從圖中可以看出，當節點數量逐漸增加時，網絡的能量消耗量隨之逐漸增大。其中，當節點數量達到400時，能源平衡數據傳輸協議所消耗的總能量最多，為182.3 J，而自適應路由協議所消耗的總能量為166.8 J，本文算法為158.5 J。雖然能源平衡數據傳輸協議和自適應路由協議都采取了一定的節能策略，但是這兩個算法在成功傳遞數據上比本文算法付出了更多的能量代價。從圖中可以看出，本文算法的網絡平均總能耗分別為文獻[13]和文獻[12]算法的89.4%和94.2%。

圖3 不同節點數量下的網絡能耗

圖4顯示了在不同通信半徑下的網絡能耗情況，從圖中可以看出，隨著節點的通信半徑逐漸增大，網絡的能耗會逐漸減少。這是由于通信半徑的增大使得參與協作傳輸的路由節點個數減少，因此網絡總的能耗降低。從圖4的數據分布情況來看，三種算法受到通信半徑變化的影響，網絡能耗都有明顯的變化趨勢。并且在不同通信半徑下本文算法的網絡能耗都低于能量平衡數據傳輸協議和自適應路由協議。對于在基站位置不同的情況下的網絡能耗情況，本文設置其他實驗條件不變，基站位置在網絡范圍內隨機生成的條件下進行了200組實驗，并且隨機抽取五個實驗結果得到了圖5所顯示的結果。從圖中可以看出，五次實驗的基站坐標都不相同，得到的網絡能耗結果也不相同，這是由于基站坐標變化使得源-目的節點間的傳輸距離也發生了變化，不同傳輸距離所消耗的網絡傳輸能耗不同。從三種算法的對比情況可以看出，即使基站坐標變化，本文算法的網絡能耗量仍然低于對比算法。

圖4 不同通信半徑下的網絡能耗

圖5 不同坐標下的網絡能耗

圖6為算法的網絡生命周期的比較情況，本文以第一個節點的死亡時間作為網絡的生命周期。根據圖中的結果，隨著網絡節點數量的增多，網絡生命周期相應延長，這是由于節點數量的增多使得每個節點的能量負載開始減小，節點壽命逐漸延長。從數據結果可以看出，本文算法所采用的中轉節點判定方法以及協作節點狀態評價函數對延長節點平均壽命起到了較好的效果，其中本文算法的平均網絡生命周期相比文獻[13]和文獻[12]算法分別增加了16.3%和7.1%。

圖6 網絡生命周期

4 結束語

為了減少水下傳感器網絡的誤碼率，提升網絡的能量效率，本文基于有限馬爾可夫鏈對協作節點狀態進行了分析，得到了協作節點的無線信道狀態及剩余能量狀態。為了確保數據采集節點的數據能夠成功傳輸，本文根據轉發任務優先的能量策略對中轉節點進行了判定。為了選擇最佳的中繼節點，本文提出了一種協作節點狀態評價函數，將誤碼率及傳輸能耗作為評價標準，從而提升網絡的信道傳輸質量并延長網絡的生命周期。

：

[1]Shen J，Tan H，Wang J，et al.A novel routing protocol providing good transmission reliability in underwater sensor networks[J].Journal of Internet Technology，2015，16（1）：171-178.

[2]Corporation H P.A multipopulation firefly algorithm for correlated data routing in underwaterwirelesssensor networks[J].InternationalJournalofDistributed Sensor Networks，2013，12（4）：245-253.

[3]Climent S，Sanchez A，Capella J V，et al.Underwater acoustic wireless sensor networks：advances and future trends in physical，MAC and routing layers[J].Sensors，2014，14（1）：795-833.

[4]Lan S L，Xiu-Juan D U，Fan L，et al.Level-based adaptive geo-routing for underwater sensor network[J].Application Research of Computers，2014，21（1）：54-59.

[5]Wahid A，Lee S，Kim D.A reliable and energy-efficient routing protocol for underwater wireless sensor networks[J].International Journal of Communication Systems，2014，27（10）：2048-2062.

[6]Corporation H P.UA-MAC：An underwater Acoustic Channel Access Method for dense mobile underwater sensor networks[J].InternationalJournalofDistributed Sensor Networks，2014，13（1）：84-88.

[7]Chen K，Ma M，Cheng E，et al.A survey on MAC protocols for underwater wireless sensor networks[J].IEEE Communications Surveys&Tutorials，2014，16（3）：1433-1447.

[8]Cao J，Dou J，Dong S.Balance transmission mechanism in underwateracoustic sensornetworks[J].International Journal of Distributed Sensor Networks，2015：1-12.

[9]張穎，孫宏梁，季常剛.基于深度和能量的水下三維傳感器網絡分簇路由算法[J].上海交通大學學報，2015，49（11）：1655-1659.

[10]蔣鵬，阮斌鋒.基于分簇的水下傳感器網絡覆蓋保持路由算法[J].電子學報，2013，41（10）：2067-2073.

[11]王慶文，劉剛，李智,等.水下無線傳感器網絡自適應轉發協議[J].西北工業大學學報，2015（1）：165-170.

[12]Yu H，Yao N，Liu J.An adaptive routing protocol in underwater sparse acoustic sensor networks[J].Ad Hoc Networks，2015，34：121-143.

[13]Javaid N，Shah M，Ahmad A，et al.An enhanced energy balanced data transmission protocol for underwater acoustic sensor networks[J].Sensors，2016，16（4）：1-22.

[14]Khan J U，Cho H S.A distributed data-gathering protocol using AUV in underwater sensor networks[J].Sensors，2015，15（8）.