張文慶， 李旭， 黃文俊

(北京交通大學 電子信息工程學院, 北京 100044)

0 引言

移動自組網絡在分簇結構下可將網絡劃分為多個稱為簇的小區域，縮小路由洪泛范圍，使得路由開銷大大減少，減少節點移動對網絡結構的影響，進而克服平面網絡擴展性差的問題，因此成為自組網絡領域的一個研究熱點[1]。

截止目前，國內外學者對多跳分簇路由協議已進行了大量研究。Max-Min[2]是被提出的第1個多跳分簇算法，該算法提出了在2k輪多跳控制信息交換中實現k跳分簇的算法。DiLoC分簇算法[3]對簇內跳數沒有任何限制，與錨節點(簇首)連接的節點都可以加入該簇。文獻[4]提出了一種穩定的k跳分簇路由算法，該算法從鄰居維護和簇首選舉方面進行改進，增強了網絡拓撲的穩定性。文獻[5]提出一種用于認知無線電網絡的k跳分簇算法，并通過仿真分析表明該算法能夠提升網絡的連通性和魯棒性。以上文獻從協議設計角度對多跳分簇進行了研究，但對協議所適用的簇內跳數取值并未展開研究。

當簇內跳數過大時，簇內節點數量增多，簇頭節點負擔增加，且簇的維護開銷增加，多個節點競爭有限資源，因此節點的平均吞吐量降低[6]；當簇的半徑過小時，會導致簇的數量過多，網絡結構易發生變化，且鄰簇間干擾增加，網絡容量下降，節點的平均吞吐量下降。

文獻[7]研究了移動自組網絡分簇路由協議中簇尺寸對簇的穩定性和維護開銷的影響，提出了基于優化分簇的混合分層路由(HOCR)協議，但該文僅從路由層面研究了簇尺寸對網絡性能的影響。文獻[8]研究了Wimax網狀網絡中的分級式跨層路由，考慮了簇內簇間的路由和時隙分配，并分析了簇大小對網絡性能的影響。但該文中的簇尺寸是簇內節點個數，所研究的網絡內節點個數較少，且未考慮網絡干擾。文獻[9]研究了云小區網絡中信道狀態信息延遲對吞吐量增益的影響，并基于均勻泊松點過程推導了信號干擾噪聲比，以網絡和速率最大化為目標，分析了最佳簇尺寸。文獻[10]分析了媒體介入控制(MAC)層為碼分多址(CDMA)接入的無線傳感器網絡簇內簇間干擾，并分析了簇尺寸對簇間干擾和網絡容量的影響。但以上兩個文獻都未考慮路由層的簇維護消耗。

本文針對大規模多跳移動分簇自組網的簇內跳數優化問題，綜合考慮網絡層路由消耗和MAC層幀結構設計來研究簇內跳數對網絡吞吐量和網絡信道利用率的影響，利用硬核泊松點過程(HCPP)模型分析網絡干擾，并以吞吐量最大化為目標，以信道利用率為約束，得到最優的簇內跳數，最后研究了路徑損耗系數和節點密度等關鍵參數對最優簇內跳數的影響。

1 系統模型

考慮1個有N個節點的分幀分時隙無線網絡(見圖1)。節點的空間分布服從密度為λp的泊松點過程。節點的通信半徑為r，最大移動速度為vmax.節點的MAC層采用協調分布式調度模式，網絡層采用分簇拓撲管理機制。全網節點使用同一頻點收發消息，系統總帶寬為W. 記E(·)為期望值函數。

1.1 MAC層調度

在協調分布式調度模式中，1個MAC層幀分為控制子幀和數據子幀兩部分，子幀又被劃分為多個時隙。每個節點的MAC層通過收發調度信息維護h跳鄰居信息。MAC層采用Mesh Election機制實現控制時隙調度，以保證控制消息的無碰傳輸；數據時隙通過控制消息的3次握手機制實現預約調度[11]。

設控制子幀的時隙個數為C，單個控制時隙最大可傳輸比特數為lc，控制時隙單位時間比特容量為Rc，則1個控制時隙的時長為tc=lc/Rc；數據子幀的時隙個數記為D，單個數據時隙最大可傳輸比特數為ld，數據時隙單位時間比特容量為Rd，則1個數據時隙的時長為td=ld/Rd. 記1個幀的時長為tf，其等于控制子幀與數據子幀的時長總和，

tf=Ctc+Dtd.

(1)

1.2 網絡層分簇

網絡層根據分簇拓撲管理機制，將網絡劃分為簇。簇由一些相互鄰近的節點組成，包括1個簇首節點和若干個簇內成員節點。為方便起見，規定簇首節點維護的鄰居跳數與MAC層所維護的鄰居跳數h一致。由于分簇機制的作用，使每個簇首所維護的h跳鄰居都不會成為新的簇首，分簇機制同樣與HCPP的稀釋過程一致，即簇首節點定期發送簇內廣播報文，簇內成員節點收到廣播報文后會發送給簇首節點響應報文，從而實現簇的形成和維護。

假設1個簇的簇首節點均處于簇的中心，則單個簇的覆蓋范圍可以看作以簇首為中心、簇半徑R=hr的1個圓，由此得到單個簇內的成員節點個數為

nm=λpπR2=λpπh2r2.

(2)

在分簇機制作用下，網絡中的發送節點分布不再服從泊松點過程。HCPP能夠緊密結合分簇機制，對完全隨機分布的節點進行一定程度的稀釋，準確描述出網絡中干擾節點的分布。其主要思路是：如果兩點之間的距離小于1個給定值，則按一定規則去掉其中的1個點，最終得到的就是HCPP. 因此，網絡層簇首節點的分布與HCPP完全契合，得到簇首節點密度[12]為

(3)

根據全網節點數N和節點分布密度λp，以及分簇機制得到的簇首節點密度λl，可以求出在全網覆蓋范圍內的簇首個數為

(4)

每個簇首對應著1個簇，因此網絡中劃分得到的簇的個數等于簇首節點個數。求節點之間的平均跳數距離。根據文獻[13]結論，1個具有N個節點的網絡，單個節點的一跳距離覆蓋范圍內的節點個數為n，則節點間跳數的數學期望為

(5)

假設節點的單跳距離為節點通信半徑，即dinn=r. 根據(5)式可得簇內任意1個節點與簇內其他節點的平均轉發跳數為

(6)

由于單個節點的一跳距離覆蓋范圍內必須有至少1個鄰居，節點密度需要滿足以下條件：

λpπr2≥2.

(7)

在完成網絡簇劃分后，簇首節點共同組成1張簇級網絡。在簇級網絡中，如果兩個簇首節點間距離在(R,2R]范圍內，則兩個簇相鄰。對于1個簇首節點，本文近似認為與其距離第i(1≤i≤h)跳的節點都處于以其為中心、半徑范圍為((i-1)r,ir]的圓環內。記距離1個簇首第i跳的節點所在的圓環面積為

Si=πi2r2-π(i-1)2r2=(2i-1)πr2，

(8)

由此可以求出兩個互為相鄰簇首的節點之間的平均距離dint，即簇級網絡一跳距離的數學期望為

(9)

根據(5)式，在簇級網絡中1個簇首與其他簇首之間的平均轉發跳數距離為

(10)

2 網絡性能分析

下面首先利用HCPP模型對協調分布式調度模式下的Mesh Election機制與3次握手機制進行建模分析，推導出MAC層控制時隙和數據時隙的信號干擾比和容量模型。然后分別從簇內和簇外兩個角度，分析業務量以及調度數據時隙和維護簇結構所需要的開銷。最后結合達到最大吞吐量條件以及由信號干擾比得出的投遞率，得到最大吞吐量的閉式解。

2.1 干擾與容量分析

2.1.1 Mesh Election選舉機制

由于節點維護h跳鄰居的調度信息，在Mesh Election選舉過程中，每個節點都將與h跳范圍內的鄰居節點展開選舉競爭，最終競選成功的發送節點周圍會形成1個半徑為R=hr的圓形干擾清除區域。其他競選成功的發送節點將成為干擾節點，其分布與稀釋半徑為hr的HCPP完全契合。由此得到選舉機制下發送節點密度[12]為

(11)

假設兩個發送節點的距離為s，則它們各自圓形干擾清除區域的聯合面積大小為

(12)

經過選舉算法對原網絡節點的密度進行稀釋后，與接收端相距s的節點能被保留成為發送節點的概率[14]為

(13)

為了反映兩節點的相互作用關系，引入兩兩節點間的空間相關函數[12]g(s)，定義為

(14)

設定發送節點為原點O，d表示接收節點與發送節點的距離，φ表示接收節點所處的方向。則接收節點遭受的干擾強度I的數學期望如下：

(15)

式中：l(s)=s-α為路徑損耗函數，α為路徑損耗指數。

將節點按空間相關性劃分為hr≤s<2hr和s≥2hr兩部分，則平均干擾強度E(I)為兩部分干擾強度的疊加，即

E(I)=E(Ihr≤s<2hr)+E(Is≥2hr)，

(16)

在區間[2R,∞)上，節點互在彼此的排斥區域之外，即兩個節點在空間上獨立無關，由此得到選舉機制下接收端信號干擾比SIRme的數學期望值為

(17)

控制消息容量RC由選舉機制下的SIRme和香農公式計算得到：

RC=Wlog2(1+SIRme).

(18)

2.1.2 3次握手機制

分別以發送節點和接收節點為圓心、半徑為hr作兩個圓形，對于兩個圓形并集范圍內的其他節點進行稀釋，不允許這些節點成為發送節點，從而實現MAC層3次握手機制的干擾消除。發送與接收節點形成的兩個圓形并集的面積Ao為

(19)

由HCPP的密度公式[12]，代入Ao可以得到3次握手機制下的干擾節點密度為

(20)

如圖2所示，假設坐標為x1的干擾發送節點s1位于極坐標平面原點O處，對應的接收節點位于s1的0°方向，用(s,β,θ)表示網絡中的另一干擾通信對的位置；干擾發送節點s2位于原點O的β方向上的x2坐標處，對應的干擾接收節點位于s2的θ方向上。則這兩個通信對的干擾清除區域聯合面積A只是(s,β,θ)的函數。

顯然，如果s2與s1的距離小于R，或s2與s1的接收節點的距離小于R，則這兩個通信對不可能共存。同理，如果s2的接收端位于s1通信對的干擾清除區域內，則這兩個通信對共存概率也為0. 除上述情況之外，兩個通信對共同存在的概率用(21)式計算：

(21)

為簡化符號起見，記余弦定理求邊公式為

(22)

結合上式以及對相關函數g(·)的定義，上述兩個通信對的相關函數整理如下：

(23)

根據文獻[14]，得到3次握手機制接收端信號干擾比SIRth的數學期望值為

(24)

數據消息容量RD由3次握手機制下的SIRth和香農公式計算得到：

RD=Wlog2(1+SIRth).

(25)

2.2 業務量分析

對于需要多跳傳輸的數據業務，不僅需要源節點的發送，還需要中間節點的轉發。為方便起見，假設每個節點均以相同的本地業務包到達速率λ(單位為個/s)發送業務，每個數據包恰好可用1個數據時隙發送。記1個簇單位時間內所需發送的總數據業務量為M，分為簇內業務量Minn和簇間業務量Mint兩部分，

M=Minn+Mint.

(26)

假設1個節點的簇間業務量與總業務量的比例為γ，用以表征簇間業務需求的指標。當每個節點都與整個網絡內所有其他節點有相同的業務通信需求時，業務比例γ等于簇外節點個數與全網節點個數的比值，

γ=1-nm/N，

(27)

單個簇的簇內業務量等于該簇內所有節點的簇內業務量總和：

Minn=nmλhinn.

(28)

單個簇的簇間業務需要由源節點先匯聚到簇首，再由簇首指定路徑后，由路徑上的網關節點和簇成員節點轉發到目的節點所在簇的簇首，最后轉發到簇內目的節點。源節點匯聚到簇首的業務與目的節點所在簇簇首轉發到目的節點業務仍屬于簇內業務，因此簇間業務只需要統計簇首之間轉發的業務量。故單個簇的簇間業務量為

Mint=nmγλhint.

(29)

綜上所述可得1個簇單位時間內所需發送的總數據業務量為

M=nmλ(hinn+γhint).

(30)

2.3 開銷分析

本文分析的開銷主要包括MAC層調度數據時隙開銷和路由層簇維護開銷兩部分。下面分析這兩部分的開銷。

2.3.1 調度數據時隙開銷

調度數據時隙的消耗產生在每次預約數據時隙時，需要3個控制時隙來分別發送請求-授權-確認消息，完成3次握手預約流程。設τ為節點單次能夠預約到的數據時隙個數，可以得到恰好調度1個幀內D個數據時隙所需占用的控制時隙個數為

(31)

2.3.2 簇維護開銷

1個簇的維護開銷可以分為簇內維護開銷Oinn和簇間維護開銷Oint兩部分。記單位時間內簇的總維護開銷Oclu為簇內和簇間維護開銷之和：

Oclu=Oinn+Oint.

(32)

簇內維護開銷是指單位時間內每個簇對自身結構的一次維護過程中所產生的平均控制報文個數，包括兩個部分：簇首節點廣播一次簇更新報文，所有收到簇更新報文的成員節點都將廣播轉發一次該簇更新報文；成員節點以單播形式向簇首回復響應報文。對于距離簇首節點第i跳的成員節點，回復響應報文至其簇首的轉發過程將引發i個控制報文。根據(8)式，可以求出距離簇首第i跳的成員節點個數qi=λpSi. 設簇首節點發送簇更新報文的頻率為finn，根據文獻[15]得出網絡的一跳鏈路平均保持時間為

(33)

式中：v1和v2表示一跳鏈路上兩節點的運行速度。則對于1個h跳簇，其簇內維護頻率應該設為簇內h跳鏈路的保持時間，以保證簇首在鏈路發生變化時能夠及時維護簇結構。因此簇內維護頻率finn=h/Tlink. 由此可以得到每個簇維護一次簇結構的開銷為

(34)

簇間維護開銷是指1個簇與網絡中其他簇之間對表驅動路由進行維護的開銷，與以下3個因素相關：簇間路由維護beacon的廣播頻率fint、簇首個數nl以及簇級網絡中1個簇首與其他簇首之間的平均轉發跳數距離hint. 簇間beacon的廣播頻率fint是簇首為了維護簇級網絡中到其余各簇首的路徑而進行廣播的速率，應設為邊界節點移動出簇的時間倒數，即fint=1/Tlink，因此得到簇間總控制開銷為

Oint=fint(nl-1)hint.

(35)

3 網絡吞吐量分析

本文希望通過優化簇內跳數h，在保證信道利用率條件下，最大化單個網絡節點的本地業務到達速率λ：

(36)

式中：η為單個簇內的信道利用率；η0為期望信道利用率。

在時分多址(TDMA)網絡中，由于1個幀的長度有限，控制時隙和數據時隙的個數設定將直接影響網絡性能。如果控制時隙所占比例過大，則會導致數據時隙即使全部被占滿仍然不能滿足調度所需的情況；如果每個幀中的控制時隙過少，則數據時隙將相應地增多，在滿足調度所需時隙的情況下仍有剩余。當然也存在一種極限情況，使得數據時隙恰好被占滿，既滿足調度需求又沒有空閑時隙，控制時隙恰好滿足調度數據時隙以及簇維護的消耗。這個臨界情況就是本文所希望設計的最優幀結構，即要達到最大網絡吞吐量需要滿足兩個條件：控制時隙恰好全部用于發送消耗；所有數據時隙恰好全部被占用。將這兩個條件轉換成表達式的形式，即：

1)簇維護消耗Oclu+調度所有數據時隙消耗Oschd=控制時隙的個數C；

2)簇內業務量Minn+簇間業務量Mint=最大預約時隙全部數據量D.

對應地，可以得到1個方程組：

(37)

式中：Ptc和Ptd分別為控制時隙和數據時隙的傳輸成功概率。根據2.1節，可以得到四相相移鍵控(QPSK)調制方式下控制時隙和數據時隙的誤碼率分別為

(38)

(39)

則控制時隙和數據時隙的傳輸成功概率分別為

Ptc=(1-Pec)lc，

(40)

Ptd=(1-Ped)ld.

(41)

求解上述方程組，可得節點最大平均吞吐量(單位為bit/s)為

(42)

則單個簇內的信道利用率(單位時間內發送數據的有效時間)為

(43)

根據文獻[11]和文獻[14]可知(36)式的模型問題類型是NP-hard問題，本文只分析了其數值解。

4 仿真結果

4.1 參數設置

下面使用MATLAB工具對提出的性能模型進行分析，通過仿真結果對關系曲線圖的變化趨勢進行討論，給出相應的物理意義和關鍵協議參數的選擇方案。仿真參數設置如下：網絡節點個數N=2 000，節點通信半徑r=100 m，最大移動速度vmax=5 m/s，系統總帶寬W=40 MHz，單個3次握手過程最大可預約時隙數τ=5，控制消息長度lc=3 200 bit，數據包長ld=8 000 bit，信道利用率期望值η0=0.75.

4.2 信號干擾比

信號干擾比反映了網絡可靠性，也決定了網絡容量。圖3給出了控制消息與數據消息的接收信號干擾比變化情況。由圖3可以看出：簇內維護跳數h越大，接收信號干擾比越高，這是因為簇內跳數越大，干擾消除的區域就越大，干擾也越小；在節點密度較小時，隨著節點密度的增加，接收信號干擾比下降。在節點密度超過某個值時信號干擾比基本不變，這是因為在節點密度較小時節點間的距離較大，相互不在對方的稀釋范圍內；隨著節點密度的增加，稀釋后的密度也增加，對接收節點造成干擾的節點增多，從而信號干擾比降低；當整個區域都被稀釋范圍覆蓋后，再增加節點密度，新增的節點都會落在稀釋范圍內而被稀釋掉，因此稀釋后的節點密度不變，即接收節點周圍的干擾節點密度不變，信號干擾比保持不變。

在簇內維護兩跳、節點密度上升至15個/km2時，控制消息接收信號干擾比SIRme已經下降至不足8 dB，數據消息接收信號干擾比SIRth下降至11 dB. 將簇內跳數擴大至3跳以后，控制消息信號干擾比能夠提升至13 dB以上，數據消息信號干擾比提升至15 dB以上。

根據(7)式，原始節點密度需要滿足λp≥2/(πr2)≈63.7個/km2，因此在后續仿真分析中，節點密度取λp≥70個/km2，以滿足節點間的連通性。

4.3 節點平均吞吐量

節點平均吞吐量反映了每個節點的平均發送業務能力，也是評價網絡性能的直接指標。圖4給出了節點平均吞吐量的變化關系圖。由圖4可以看出，當簇內跳數為2時，由于干擾太大，使得吞吐量幾乎為0，在α=4簇內跳數為3跳以上時由于網絡干擾不再是主要限制因素，簇內跳數越大，簇內的節點數增多，每個節點的平均吞吐量下降。當α=3時，簇內最優跳數為4跳。這是因為在路徑損耗α增加時簇間的干擾會減小，此時可通過減小簇內跳數來減小簇內節點個數，從而增加節點的平均吞吐量。另外，吞吐量隨節點密度的增加而降低。因為隨著節點密度的增加，簇內的節點數增多，維護開銷增加，且在信道資源有限情況下，每個節點分得的信道資源下降，造成節點有效吞吐量下降，所以降低節點密度也是增加節點平均吞吐量的一種有效方式。

4.4 信道利用率

信道利用率反映了信道被占用情況，也反映了網絡的有效性。圖5給出了信道利用率的變化情況。由圖5可以看出，在達到最優跳數后，當節點密度較小時，由于網絡負載未達到最大值，在節點密度增加時可通過優化幀結構設計來提高吞吐量，但在節點密度較大時，繼續增加簇內跳數帶來的額外開銷使得信道利用率下降，而且節點密度越高，維護鄰居的開銷越大。當簇內跳數低于最優跳數時，由于簇間干擾太強，使得控制時隙的傳輸成功概率很低，需要更多的控制時隙來重新傳送控制消息，因此信道利用率下降。當簇內跳數為2時，單個簇的信道利用率幾乎為0.

由于信道利用率期望值η0=0.75，在α=3、λp=500個/km2時，雖然4跳時可以取得最優的節點平均吞吐量，但信道利用率最優值小于η0. 對此，可以通過降低節點密度、提升信道利用率來滿足約束條件要求。

5 結論

本文綜合考慮了網絡層和MAC層幀消耗，利用HCPP模型分析簇間干擾，并以吞吐量最大化為目標，推導最優的簇內跳數，最后研究了影響最優跳數的關鍵參數。仿真結果表明：跳數越大、節點密度越小時，網絡干擾越小；簇內跳數的最優值主要取決于路徑損耗和節點密度，路徑損耗增大且節點密度降低時，最優跳數減小，最大節點平均吞吐量增加。

本文重點在于分簇對鏈路干擾和網絡性能的影響，對信道模型的處理比較簡單，后續將考慮更加復雜的信道條件以及移動場景等非穩態因素。