基于串型路由的水聲通信網(wǎng)絡(luò)ALOHA協(xié)議性能分析

汪生泉, 孫大軍, 張友文

(1. 哈爾濱工程大學(xué) 水聲技術(shù)重點實驗室，黑龍江 哈爾濱 150001；2. 哈爾濱工程大學(xué) 水聲工程學(xué)院，黑龍江 哈爾濱 150001)

?

基于串型路由的水聲通信網(wǎng)絡(luò)ALOHA協(xié)議性能分析

汪生泉1,2, 孫大軍1,2, 張友文1,2

(1. 哈爾濱工程大學(xué) 水聲技術(shù)重點實驗室，黑龍江 哈爾濱 150001；2. 哈爾濱工程大學(xué) 水聲工程學(xué)院，黑龍江 哈爾濱 150001)

摘要：針對水下通信網(wǎng)絡(luò)串型路由應(yīng)用，為獲取ALOHA協(xié)議最佳性能，基于現(xiàn)有水聲通信裝備及水聲信道參數(shù)，建立了串型水聲通信網(wǎng)絡(luò)模型。分析了ALOHA協(xié)議在串型水聲通信網(wǎng)絡(luò)的交付率、吞吐量及端對端時延等網(wǎng)絡(luò)性能測度，推導(dǎo)了獲取最佳網(wǎng)絡(luò)性能的網(wǎng)絡(luò)參數(shù)配置條件，并通過NS3仿真軟件對基于串型路由的水聲通信網(wǎng)絡(luò)ALOHA協(xié)議性能進行仿真分析，結(jié)果表明：該協(xié)議在負(fù)載的若干特定點上能夠獲得最佳性能，仿真結(jié)果與理論分析一致，進而為該協(xié)議的實際應(yīng)用提供了理論依據(jù)。

關(guān)鍵詞：ALOHA協(xié)議；串型路由；交付率；吞吐量；端到端時延

由于通信網(wǎng)絡(luò)節(jié)點發(fā)送功率和水聲信道帶寬的限制[1-4]，基于水聲通信網(wǎng)絡(luò)的點對點遠距離穩(wěn)健數(shù)據(jù)交互面臨著極大的挑戰(zhàn)，有效的路由協(xié)議是水聲通信網(wǎng)絡(luò)信息交互性能的關(guān)鍵。串型路由ALOHA協(xié)議[5]在復(fù)雜的水聲通信網(wǎng)絡(luò)中也取得了廣泛的應(yīng)用，深入研究ALOHA協(xié)議在串型路由水聲通信網(wǎng)絡(luò)中的網(wǎng)絡(luò)性能具有重要意義。純ALOHA協(xié)議由于缺少避碰機制，其最大吞吐量僅為0.184[6]。針對ALOHA協(xié)議改進的協(xié)議有很多，如N. Chirdchoo等提出了碰撞避免Aloha(Aloha-CA)和預(yù)先通知Aloha(Aloha-AN)[7]等，在一定程度上提高了網(wǎng)絡(luò)吞吐量。但針對現(xiàn)有水聲通信裝備性能及水聲信道參數(shù)約束下串型路由ALOHA協(xié)議的最優(yōu)網(wǎng)絡(luò)性能參數(shù)配置的理論研究尚無深入研究。本文通過建立串型路由水聲通信網(wǎng)絡(luò)模型，研究ALOHA協(xié)議在串型水聲通信網(wǎng)絡(luò)的交付率、吞吐量及端對端時延等網(wǎng)絡(luò)性能測度，推導(dǎo)出獲取最佳網(wǎng)絡(luò)性能的網(wǎng)絡(luò)參數(shù)配置，從而為ALOHA協(xié)議在串型路由水聲通信網(wǎng)路中的應(yīng)用提供理論支撐。

1水聲通信網(wǎng)絡(luò)串型路由模型

由n個通信節(jié)點構(gòu)成的串型水下通信網(wǎng)絡(luò) (如圖1所示)，其中第1個節(jié)點(編號為1)和最后一個節(jié)點(編號為n)為水面節(jié)點，中間為水下節(jié)點(編號從2～n-1)。相鄰節(jié)點間距離相等，僅節(jié)點1產(chǎn)生數(shù)據(jù)流采用固定間隔發(fā)送數(shù)據(jù)模式，水下節(jié)點僅負(fù)責(zé)轉(zhuǎn)發(fā)，將上一跳節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)給下一跳節(jié)點，節(jié)點n為目的節(jié)點負(fù)責(zé)接收。

圖1　串型路由水聲通信網(wǎng)絡(luò)模型Fig. 1　A model of string underwater sensor networks

對于任意節(jié)點j(1

在該模型下，在水聲信道環(huán)境較好的情況下，在節(jié)點2處會導(dǎo)致數(shù)據(jù)包丟失的原因如下：1)節(jié)點1發(fā)送的前后2個數(shù)據(jù)包的間隙小于數(shù)據(jù)包的發(fā)送時延，造成節(jié)點2轉(zhuǎn)發(fā)節(jié)點1的前一個數(shù)據(jù)包時，節(jié)點1發(fā)出的后一個數(shù)據(jù)包已經(jīng)到達，此時由于節(jié)點2處于發(fā)送狀態(tài)無法接收。2)節(jié)點1發(fā)送的數(shù)據(jù)包與節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包在節(jié)點2處發(fā)生碰撞。

2最優(yōu)網(wǎng)絡(luò)性能測度

作如下假設(shè)：

1)所有數(shù)據(jù)包長度相同，數(shù)據(jù)包調(diào)制/解調(diào)所需時間用Td表示，歸一化為1；

2)節(jié)點之間的平均傳播時延為τ，歸一化后為α=τ/Td；

3)節(jié)點1發(fā)送數(shù)據(jù)包按固定間隔產(chǎn)生，前后2個數(shù)據(jù)包之間的時間間隙為Tinterval，歸一化后為β=Tinterval/Td；

4)網(wǎng)絡(luò)運行時間為Tsim。

2.1碰撞規(guī)律

碰撞規(guī)律定理：節(jié)點1發(fā)送的第k個數(shù)據(jù)包經(jīng)過節(jié)點2、節(jié)點3轉(zhuǎn)發(fā)后再次到達節(jié)點2，如果節(jié)點1發(fā)送的第j個數(shù)據(jù)包(j>k)，與第k個數(shù)據(jù)包在節(jié)點2處沒有發(fā)生碰撞，那么這2個數(shù)據(jù)包也不會在后續(xù)的節(jié)點處發(fā)生碰撞。

證明：

第k個數(shù)據(jù)包的發(fā)送時間是(k-1)β+(k-1)經(jīng)過節(jié)點2、節(jié)點3轉(zhuǎn)發(fā)后再次到達節(jié)點2，被節(jié)點2接收的時間區(qū)間為

(1)

第j個數(shù)據(jù)包發(fā)送時間是(j-1)β+(j-1)，節(jié)點2接收第j個數(shù)據(jù)包的時間區(qū)間為

(2)

結(jié)合式(1)、(2)可得第k個數(shù)據(jù)包與第j個數(shù)據(jù)包碰撞的充要條件:

或

推導(dǎo)后可得

(3)

那么第k個數(shù)據(jù)包與第j個數(shù)據(jù)包不碰撞的充要條件為

(4)

同理可得：如果節(jié)點1發(fā)送的第j個數(shù)據(jù)包(j>k)，與第k個數(shù)據(jù)包在節(jié)點2處沒有發(fā)生碰撞，則第j個數(shù)據(jù)包到達節(jié)點3的時間區(qū)間為

(5)

第k個數(shù)據(jù)包的發(fā)送時間是(k-1)β+(k-1)經(jīng)過節(jié)點2、節(jié)點3、節(jié)點4轉(zhuǎn)發(fā)后再次到達節(jié)點3的時間區(qū)間為

(6)

同上，得到第k個數(shù)據(jù)包與第j個數(shù)據(jù)包在節(jié)點3處不碰撞的充要條件為

(7)

式(4)、(7)完全相同，即如果第k個數(shù)據(jù)包與第j個數(shù)據(jù)包在節(jié)點2處不碰撞，那么第k個數(shù)據(jù)包與第j個數(shù)據(jù)包在節(jié)點3處不碰撞。以此類推，第k個數(shù)據(jù)包與第j個數(shù)據(jù)包在后續(xù)節(jié)點處均不會發(fā)生碰撞，從而命題結(jié)論得證。

碰撞規(guī)律推論：數(shù)據(jù)包的碰撞僅僅會發(fā)生在節(jié)點2處。

2.2網(wǎng)絡(luò)交付率

網(wǎng)絡(luò)的交付率是串型路由水聲通信網(wǎng)絡(luò)關(guān)注的重要指標(biāo)，若相鄰節(jié)點鏈路的交付率為Pj→j+1，則串型網(wǎng)絡(luò)的整體交付率P表達式為

(8)

根據(jù)推論可知當(dāng)j≥2時，Pj→j+1=1，則串型網(wǎng)絡(luò)的整體交付率P表達式為

(9)

2.3網(wǎng)絡(luò)吞吐量

網(wǎng)絡(luò)吞吐量與交付率關(guān)系表達式如下

(10)

(11)

2.3.1當(dāng)0≤β<1時網(wǎng)絡(luò)吞吐量分析

當(dāng)0≤β<1時，節(jié)點1發(fā)送的2個數(shù)據(jù)包之間的間隙小于數(shù)據(jù)包的發(fā)送時間，導(dǎo)致在節(jié)點3發(fā)數(shù)據(jù)包的信號到達節(jié)點2時會和節(jié)點1發(fā)出的數(shù)據(jù)包中的1個或者連續(xù)2個發(fā)生碰撞。

若節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包為第1個包，根據(jù)式(4)可知，節(jié)點1發(fā)出的第j個數(shù)據(jù)包與節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包在節(jié)點2處碰撞的條件為

(12)

當(dāng)α∈[k,k+0.5)，k是大于或等于0的整數(shù)，則節(jié)點1發(fā)出的第k+2個數(shù)據(jù)包至第個2(k+2)個數(shù)據(jù)包，一共涉及k+3個數(shù)據(jù)包中的1個或者連續(xù)2個數(shù)據(jù)包會與節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包在節(jié)點2處碰撞。根據(jù)β取值的不同，碰撞的點也不一樣，圖2是0≤β<1時的碰撞規(guī)律示意圖。

圖2　當(dāng)0≤β<1時的碰撞規(guī)律示意圖Fig. 2　Regular patterns of data packets collisions where 0≤β<1

設(shè)j是自然數(shù)，且j∈[k+2,2(k+2)]。

1)若j是偶數(shù)。

假設(shè)2α=2k+ε,(0≤ε<1)，有

若j=2k+4，則節(jié)點3發(fā)出的數(shù)據(jù)包僅與節(jié)點1發(fā)出的第j個數(shù)據(jù)包數(shù)據(jù)包發(fā)生碰撞是不可能的。原因是節(jié)點1的第j=2k+4個數(shù)據(jù)包與節(jié)點3的數(shù)據(jù)包發(fā)生碰撞的β區(qū)間為

左側(cè)為

右側(cè)為

這與0≤β<1矛盾，因此，j=2k+4時，節(jié)點3的數(shù)據(jù)包是不可能僅與節(jié)點1發(fā)出的第j個數(shù)據(jù)包發(fā)生碰撞的。

2)若j是奇數(shù)。

綜上，將上述0≤β<1，α∈[k,k+0.5)且α>0時的吞吐量表達式如下

(13)

同樣，當(dāng)α∈[k-0.5,k)，k是自然數(shù)。則節(jié)點1發(fā)出的第k+2個數(shù)據(jù)包至第2(k+2)-1個數(shù)據(jù)包中的1個或連續(xù)2個與節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包在節(jié)點2處碰撞。設(shè)j是自然數(shù)，且j∈[k+2,2(k+2)-1]，則吞吐量表達式如下

(14)

2.3.2當(dāng)β≥1時網(wǎng)絡(luò)吞吐量分析

當(dāng)α∈[k-0.5,k+0.5)，k是自然數(shù)。則節(jié)點1發(fā)出的第2～k+2個共計k+1個數(shù)據(jù)包中的1個可能會與節(jié)點3轉(zhuǎn)發(fā)的數(shù)據(jù)包在節(jié)點2處碰撞。

設(shè)j是自然數(shù)，且j∈[2,k+2]。

綜上，將上述β≥1，α∈[k-0.5,k+0.5)時的吞吐量表達式總結(jié)如下

(15)

圖3　β≥1時的碰撞規(guī)律示意圖Fig. 3　Regular patterns of data packets collisions where β≥1

圖4　β∈[0,1),α∈[k,k+0.5)最大吞吐量原理圖Fig. 4　The maximum throughput whereβ∈[0,1),α∈[k,k+0.5)

2.3.3網(wǎng)絡(luò)最大吞吐量分析

1)當(dāng)β∈[0,1)時的最大網(wǎng)絡(luò)吞吐量分析。

①β∈[0,1),α∈[k,k+0.5)時。

根據(jù)式(13)，在β∈[0,1),α∈[k,k+0.5)區(qū)域內(nèi)，節(jié)點碰撞被分為4種碰撞類型，節(jié)點3與第奇數(shù)個包、與第偶數(shù)個包以及與以奇數(shù)開頭的連續(xù)2個包碰撞、與以偶數(shù)開頭的連續(xù)2個包碰撞。各種類型碰撞的吞吐量結(jié)果不同，在相應(yīng)的區(qū)間上隨著β的增大，其吞吐量不斷減小，因此對應(yīng)各個碰撞類型的吞吐量最大值在相應(yīng)區(qū)間最左側(cè)的點處。

設(shè)與以奇數(shù)開頭的連續(xù)2個包碰撞的吞吐量最大值為TP1，則

(16)

設(shè)與第奇數(shù)個包碰撞的最大吞吐量為TP2，則

(17)

設(shè)與以偶數(shù)開頭的連續(xù)2個包碰撞的吞吐量最大值為TP3，則

(18)

設(shè)與第偶數(shù)個包碰撞的吞吐量最大值為TP4，則

(19)

比較式(16)～(19)可知：TP2=TP4>TP1，TP2=TP4>TP3。

②β∈[0,1),α∈[k-0.5,k)時。

圖5　β∈[0,1),α∈[k-0.5,k)時最大吞吐量原理圖Fig. 5　The maximum throughput whereβ∈[0,1),α∈[k-0.5,k)

根據(jù)式(14)，當(dāng)β∈[0,1),α∈[k-0.5,k)，節(jié)點碰撞分為4種類型。即：節(jié)點3與第奇數(shù)個包、與第偶數(shù)個包、與以奇數(shù)開頭的連續(xù)2個包、與以偶數(shù)開頭的連續(xù)2個包碰撞。各種類型的吞吐量在相應(yīng)的區(qū)間上隨著β的增大而減小，因此對應(yīng)各種碰撞類型的最大吞吐量在相應(yīng)區(qū)間最左側(cè)的點處。

設(shè)與以偶數(shù)開頭的連續(xù)2個包碰撞的最大吞吐量為TP5，則

(20)

設(shè)與第偶數(shù)個包碰撞的最大吞吐量為TP6，則

(21)

設(shè)與以奇數(shù)開頭的連續(xù)2個包碰撞的最大吞吐量為TP7，則

(22)

設(shè)與第奇數(shù)個包碰撞的最大吞吐量為TP8，則

(23)

比較式(20)～(23)有

TP6>max{TP5,TP7,TP8}

綜上所述，當(dāng)β∈[0,1)時，吞吐量的最大值是節(jié)點3轉(zhuǎn)發(fā)的包僅與節(jié)點1發(fā)出的第2k+3(最大奇數(shù))個或第2k+2(最大偶數(shù))個數(shù)據(jù)包碰撞的時候達到，其中2個包之間的間隙β取對應(yīng)區(qū)間的最小值。

圖6　β∈[1,+)時最大吞吐量原理圖Fig. 6　The maximum throughput whereβ∈[1,+)

設(shè)碰撞的最大吞吐量為TP9，則

(24)

設(shè)不碰撞的最大吞吐量為TP10，則

(25)

比較式(24)、(25)可知：TP10>TP9。

綜合式(17)、(19)、(21)、(25)，可得以下重要結(jié)論。即在給定α的條件下，網(wǎng)絡(luò)的最大吞吐量為

(26)

3仿真實驗分析

3.1實驗參數(shù)配置

仿真采用NS3仿真軟件進行仿真，仿真參數(shù)配置為：節(jié)點數(shù)量7個，相鄰節(jié)點距離為5 000 m，聲速1 500 m/s，數(shù)據(jù)包長度為2 048 bit，發(fā)送速率為1 024 bit/s，仿真時間為3 600 s。

3.2仿真結(jié)果及分析

仿真不斷改變數(shù)據(jù)包間隙β(即網(wǎng)絡(luò)負(fù)載)，仿真結(jié)果與理論計算結(jié)果對比如圖7～9所示。

1)吞吐量分析

仿真值比理論值稍滯后一點，原因是由于處理時延非常小，在吞吐量理論分析時沒有考慮數(shù)據(jù)包的處理時延造成的偏移。從圖7可以看出，實驗結(jié)果存在2個吞吐量最大值的點，一個在其數(shù)據(jù)包發(fā)送間隙0～1區(qū)間上，另一個在大于1的區(qū)間上，與理論分析一致。

圖7　網(wǎng)絡(luò)吞吐量隨數(shù)據(jù)包發(fā)送間隙β變化曲線Fig. 7　Throughput as the delivering interval β between data packets is varied

2)交付率分析

交付率的仿真值和理論值一致，由于理論分析時沒有考慮數(shù)據(jù)包的處理時延造成的存在仿真值比理論值稍滯后一點。圖中存在三段交付率為1的區(qū)間，其數(shù)據(jù)包發(fā)送間隙β均大于1。很顯然，β值較小的區(qū)間其吞吐量更大。

圖8 交付率隨數(shù)據(jù)包發(fā)送間隙β變化曲線Fig. 8　Delivery rate as the delivering intervalβbetween data packets is varied

3)網(wǎng)絡(luò)時延分析

從圖9可以看出，網(wǎng)絡(luò)時延基本保持在32.4 s左右，很穩(wěn)定，原因是發(fā)送時延、數(shù)據(jù)處理時延以及傳播時延基本是固定不變的。

圖9　端到端時延隨數(shù)據(jù)包發(fā)送間隙β變化曲線Fig. 9　End-to-end delay as the delivering interval β between data packets is varied

4)綜合分析

綜合對比圖7、8可知，在0≤β<1區(qū)間上取得吞吐量最大值的點，所在區(qū)間的交付為0.5，也就是說，節(jié)點1發(fā)送的數(shù)據(jù)包有一半丟失了，盡管吞吐量較大，但節(jié)點消耗的能量較多。在β≥1區(qū)間上取得吞吐量最大值的點，所在區(qū)間恰好是三段交付率為1的區(qū)間的第一段，與0≤β<1區(qū)間上的取得吞吐量最大值的點比較，2個點吞吐量一樣大，但此處交付率為1，沒有造成包的丟失，能耗較小。上述2個點端到端時延基本沒有區(qū)別。

4結(jié)束語

目前ALOHA協(xié)議在功能較為單一水聲通信網(wǎng)絡(luò)中應(yīng)用廣泛，但其實際的最優(yōu)性能與節(jié)點布放以及通信裝備的參數(shù)有著密切的關(guān)系，本文基于水聲通信網(wǎng)絡(luò)的3種性能評價指標(biāo)(即數(shù)據(jù)交付率、吞吐量以及端對端時延)，推導(dǎo)了串型路由條件下獲取最佳網(wǎng)絡(luò)綜合性能的參數(shù)配置條件，仿真實驗驗證了本文的理論分析結(jié)論，該理論分析為該協(xié)議的實際應(yīng)用提供有力的指導(dǎo)依據(jù)。

參考文獻：

[1]周密, 崔勇, 徐興福, 等. 水聲傳感網(wǎng)MAC協(xié)議綜述[J]. 計算機科學(xué), 2011, 38(9): 5-10, 17.

ZHOU Mi, CUI Yong, XU Xingfu, et al. Survey of the MAC protocols on underwater acoustic sensor network[J]. Computer science, 2011, 38(9): 5-10, 17.

[2]DOMINGO M C. Overview of channel models for underwater wireless communication networks[J]. Physical communication, 2008, 1(3): 163-182.

[3]NASRI N, KACHOURI A, ANDRIEUX L, et al. Design considerations for wireless underwater communication transceiver[C]//Proceedings of the 2nd international conference on signals, circuits and systems (SCS). Monastir: IEEE, 2008: 1-5.

[4]CATIPOVIC J A. Performance limitations in underwater acoustic telemetry[J]. IEEE journal of oceanic engineering, 1990, 15(3): 205-216.

[5]ROBERTS L G. ALOHA packet system with and without slots and capture[J]. ACM SIGCOMM computer communication review, 1975, 5(2): 28-42.

[6]BERTSEKAS D P, GALLAGER R. Data networks[M]. 2nd ed. New Jersey: Prentice hall, 1992.

[7]CHIRDCHOO N, SOH W S, CHUA K C. Aloha-based MAC protocols with collision avoidance for underwater acoustic networks[C]//Proceedings of the 26th IEEE international conference on computer communications. Anchorage, AK, USA: IEEE, 2007. -----------------------------------------------------------------------------------------------------------

Performance analysis for ALOHA protocol of underwater acoustic networks with a serial route

WANG Shengquan1,2, SUN Dajun1,2, ZHANG Youwen1,2

(1. Acoustic Science and Technology Laboratory, Harbin Engineering University, Harbin 150001, China; 2. College of Underwater Acoustic Engineering, Harbin Engineering University, Harbin 150001, China)

Abstract：Based on the application of a serial route for underwater acoustic communication networks, in order to optimize the performance of the ALOHA protocol, we designed a serial route underwater acoustic network model that uses available underwater acoustic communication equipment and underwater acoustic channel parameters. We analyzed the performance measurements of the ALOHA protocol in terms of delivery rate, throughput, and end-to-end delay, and deduced the optimal conditions for parameter configuration. The network performance was also appraised via NS3 simulation software. The simulation results suggest that at certain network load points, optimal performance can be achieved. The results of our simulation and theoretical analysis are almost identical, providing a basis for further application of this protocol.

Keywords：ALOHA protocol; serial route; delivery rate; throughput; end-to-end delay

中圖分類號：TN929

文獻標(biāo)志碼：A

文章編號：1006-7043(2016)03-360-08

doi:10.11990/jheu.201501013

作者簡介：汪生泉(1980-), 男, 助理研究員,博士；通信作者：孫大軍，E-mail：sundajun@hrbeu.edu.cn.

基金項目：國家自然科學(xué)基金資助項目(50909029,61471138).

收稿日期：2015-01-12.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160105.1604.004.html

網(wǎng)絡(luò)出版日期：2016-01-05.

孫大軍(1972-), 男, 教授,博士生導(dǎo)師.