基於統計移動尺度的移動感知分簇方法

2023-05-21 13:55:21

專利名稱：基於統計移動尺度的移動感知分簇方法
技術領域：
本發明屬於無線通信領域，涉及到移動Ad Hoc網絡中網絡節點的分簇組網，可應用在大型移動Ad Hoc網絡中建立類似地面蜂窩網的分級網絡結構，優化網絡的路由查找、擁塞控制、拓撲維護以及便於網絡擴展。
背景技術：
移動Ad Hoc網絡是一種多跳，無中心且沒有有線基礎設施支持的行動網路，網絡中節點均由移動主機構成。Ad Hoc網絡的組網通信無需依賴於任何預設的網絡設施。結點通過自發的鄰居發現，路由查找算法快速、自動地組成一個獨立的網絡。由於Ad Hoc網絡諸多特性，它在軍事戰場、傳感器網絡以及緊急臨時場合如災難救援等有廣泛的應用前景。與地面蜂窩網和衛星通信系統相比，移動Ad Hoc網絡具有部署方便且迅速，高性 價比，覆蓋範圍廣，傳輸延遲低，抗毀性和易擴展性等特點。同時Ad Hoc網絡也面臨諸多挑戰，其中大規模問題是移動Ad Hoc網絡走向實際應用中不得不解決的至關重要的難題。當網絡包含大量移動通信節點時，拓撲維護、路由開銷和擁塞控制等將消耗大量的有限網絡資源，如能量和無線帶寬等。分簇已經被證明是一種有效的解決上述大規模問題的方法。通過分簇將一個大型的網絡劃分為一個個互相連接的小型網絡從而形成一個多級的網絡結構。因為移動性是Ad Hoc網絡的固有特性，節點的移動會導致網絡拓撲的頻繁改變從而限制網絡容量和帶寬，不僅如此，節點移動還會破壞原先的簇結構，引發頻繁的分簇行為從而佔用有限的網絡資源。因此如何在網絡節點不斷移動的情況下建立一個穩定的分簇結構是移動Ad Hoc網絡分簇算法的一個關鍵難題。目前AdHoc網絡中的移動感知分簇算法主要是基於移動尺度的方法。通過定義合適的移動尺度來衡量節點的移動性，以此來進行簇頭節點的選舉及簇的劃分。因此移動尺度的準確性直接影響到後續分簇結構的穩定性。目前有多種移動尺度被提出來。早期，波士頓大學的Prithwish等人提出了一種累積移動尺度。每個節點發送兩個連續的數據包給它所有鄰居節點，這樣每個節點就能通過前後接收到的數據包的強度差異來判斷它與其鄰居節點是相互靠近還是相互遠離。累積移動尺度定義為節點接收到的來自所有鄰居節點的前後數據包強度的比值之和。分簇算法選舉累積移動尺度大的節點作為簇頭來進行簇的劃分。隨後，新加坡南洋理工大學ZhangYan等人提出一種空間依賴尺度。它定義為兩個節點相對速度大小和方向的夾角餘弦的乘積並以此作為簇頭選舉的依據。東南大學DengS. Z.等人在2011年提出一種基於移動的分簇協議，在該協議中，移動尺度被定義為節點間初始距離及預估的連接時間的歸一化線性加權之和。上述移動尺度均是基於啟發式定義而非理論推導出來的，因此不可避免的存在一些缺陷。例如，它們在定義中只考慮到某些要素如速率、方向或信號接收功率，而沒有綜合考慮影響節點運動的多種因素，所以不能準確反應節點之間的運動關係，此外它們都是通過節點的當前移動狀態計算的，從而不能準確預測節點將來的運動狀態，直接影響到簇結構的穩定性，而且不能滿足簇結構隨節點速度和通信半徑變化自適應調整的需要。

發明內容
本發明的目的在於解決現有Ad Hoc網絡移動感知分簇算法的不足，提出一種基於統計移動尺度的移動感知分簇方法，能夠使分簇算法最終所形成的簇結構更穩定，更能適應節點速度和通信半徑的變化。為實現上述目的，本發明包括如下步驟A.根據Ad Hoc網絡應用環境，選取一個能準確模擬Ad Hoc網絡節點運動的移動模型，即平滑的隨機遊走模型；B.根據選取的平滑隨機遊走模型，得出移動節點的運動速率Vi (t)和方向PW的分布函數柳={ #； !!
m(t、= \<PiO iV2(0 = 0
只N1(J)幸Q』其中，Vitl和約。分別為移動節點i初始速率和方向'N'為當移動節點的運動速率改變時所選取的新的速率變量，服從Vmin到Vmax均勻分布，即V U[vmin，VmaJ #為當移動節點的運動方向改變時所選取的新的方向變量，服從O到2 Ji的均勻分布，即# U
,方向的正弦函數的期望￡Isin(^(i))]及餘弦函數的期望flcosfeO))]；^(0]= ·—
￡[cos(p# ( ))]= cos(< #0) · e—v
￡fsinO,· (0)] = Sinfe0) · e_ht ,其中，Sin(^0)和COS(^10)分別為移動節點i的初始方向(Pm的正弦和餘弦函數；E [Vi (t)]為節點速率隨時間的期望值，琢0蝴.(/))]和￡[Sin@(0)扮別為節點運動方向的正餘弦隨時間的期望值；D.根據所得到的三個期望疋|^(1:)]、￡1^11(約(0)]、￡Icos(只(0)]，構造出任意兩移動節點間距離的期望值H(u(t)的表達式Η(( Λ(i)=^[ b (I) - Hhi (I)]2 + [ λ· (r) - myj (/)]2 ,其中，Ha.j) (t)為任意兩移動節點i，j的距離的期望值，Xi(t)和yi(t)為移動節點i的水平和垂直坐標，帳,(O和A(0為對應的水平和垂直坐標的期望值；E.根據得到的任意兩個移動節點間距離的期望值H(i, j0 (t)，計算每個移動節點i的統計移動尺度SMM (i，t)SMM(U) = D-H" ,,(/),其中，R為每個節點的通信半徑，η為移動節點i的一跳鄰居節點數目；F.根據移動節點的統計移動尺度SMM(i，t)，所有移動節點每隔時間T，0. 5秒，廣播一個Hello數據包，Hello數據包包含了移動節點的節點標識ID和統計移動尺度值的信息；G.根據接收到的來自一跳鄰居節點的Hello包信息，移動節點i將自己的統計移動尺度值SMM (i，t)與其所有一跳鄰居節點的統計移動尺度值作比較，若移動節點i的統計移動尺度值最大，則將節點i選作簇頭，並將i的一跳鄰居節點分配為移動節點i的簇成員，反之，則跳過移動節點i ;如果該節點沒有鄰居節點，那麼它將改變自身的狀態成為簇頭節點；H.對已被選為簇頭或分配為簇成員的其它移動節點執行步驟F中同樣的判斷過程，最終完成簇頭節點的選舉和簇的劃分。上述步驟D中根據所得到的三個期望E [Vi (t)]、可sin(^.(0)]、可cosO#))],構成出任意兩移動節點間距離的期望值H(ij(t)的表達式，按如下步驟進行Dl)考慮一個非常短的時間At，設為1(Γ6秒，在At內將節點速率和方向看作是·不變的，得出Vml-At+ S0 = Sii n(Af){ I )V^-At + S^ n(t) = + At)(2)其中,Irf表示任意兩個節點i與節點j之間的相對速度向量表示任意兩個節點i，j之間的相對距離向量(表示任意兩個節點i與節點j之間的初始距離向量；D2)根據式(I)和(2)，對式(2)兩邊取期望，得出任意兩節點間距離的向量隨時間
期望可4#)]為
成艱Λ+旯
={￡ ￡ |Η (Δ/)| · COS φ (M)]dAt，
￡[Κ' (Δ/)Ι ·sin Ψ (Δ/)Μν}(3)
-C 圳⑷丨·cos (pj (Δ )]4，
￡[|^ (Δθ| · Sin φ} (Ai)Jrfi,} + Stt其中, ,( )和供,(八0分別為移動節點i的速率和方向的分布函數;sin畀(Δ/)和Cos^(AZ)分別為ρ(Δ )的正弦和餘弦函數狀( )|為速度向量5(Δ/)的標量值表示任意兩個節點i, j之間的相對速度向量的期望值表示任意兩個節點i與節點j之間的相對距離向量的期望值；D3)根據物理學中物體的運動距離與運動速度和時間的關係，得出節點i的水平坐標期望浙,(/)和垂直坐標期望》%,(/)
nh, (O = J"。' E[vt (r)] ■ ￡[cos(釣(r))]rfr + xm、4 )
my,(t) = Jo'E[vt(r)] ·E[sin(tpf(t))]c/t + ym( 5 )其中，xi0和yi(l分別表示移動節點i的初始水平和垂直坐標；Xi⑴和(t)表示節點i的水平和垂直坐標；D4)將式(3)展開，並將式(4)和(5)代入，得出任意兩個節點i，j之間的相對距
離向量的期望值￡'[1,(0]:
^4,,)(0]=1* +*
=(J:確艿(Δ )卜 cos φ, (Δ )]心,，￡ ￡[|ν,. (Δ/)| · sin φ (AOJ^i}
+ (xm, ν,ο)-E[\vj(Δ )| ■ cosφ](Δ )ΜΔ,,,(6)
: ￡[|巧(Δ/)| ■ Sin cPj (Δ )];/0 )
=(m.' (O, Hiyz (/)) - (Imj (O, (/))D5)對式(6)兩邊的距離向量取標量，得出任意兩節點間距離的期望值Η(Μ)α)的表達式H(iJ) (O = |(m,, (O, my, (O) — Qrhj (O, m-, (0)| ( 7 )=Sjinh (t) - Otti (/)]2 + fBZri (/) - Itlyj (r)]:上述步驟G所述的若移動節點i的統計移動尺度值最大，則將節點i選作簇頭，並將i的一跳鄰居節點分配為移動節點i的簇成員，按如下步驟進行Gl)移動節點i向其一跳鄰居節點廣播一個JoinRequest消息包的簇邀請，JoinRequest消息包包含節點i的ID標識Node-IDi ；G2)處於未分配狀態的移動節點j收到來自其一跳鄰居節點i的JoinRequest簇邀請消息後，向移動節點i發送一個Accept應答消息包，並將其所屬簇標識( 設置為節點i的ID標識Node-IDi,以表明自身屬於移動節點i所代表的簇，所述的Accept應答消息包，包含移動節點j的ID標識Node-IDj。本發明與現有技術相比較具有如下優點a)本發明由於利用了對移動節點網絡環境準確模擬的移動模型，因此最大程度利用了關於移動節點運動的先驗知識，使得它更能適應移動節點速度或通信半徑的變化。b)本發明由於使用的統計移動尺度是通過任意兩個移動節點間相對距離的期望計算出來的，因此它描述了統計意義上對移動節點間未來關係的預測，更精確的反應了移動節點間的運動關係。c)本發明由於是基於統計移動尺度來進行簇頭選舉和簇的劃分，因此最終形成的簇結構更穩定，簇頭生存時間更長。


圖I是本發明基於統計移動尺度的移動感知分簇方法框圖；圖2是本發明與其它三種分簇方法在節點平均駐留時間下的性能對比圖；圖3本發明與其它三種分簇方法在簇離開率下的性能對比圖；圖4是本發明與其它三種分簇方法在平均簇頭生存時間下的性能對比圖。
具體實施例方式本發明的核心思想是基於對Ad Hoc網絡節點移動模型的分析從理論上推導出一個統計移動尺度來評估移動節點的運動，基於該統計移動尺度來完成簇頭選舉和簇的劃分，最終形成一個更穩定的簇結構。首先選取一個能準確模擬Ad Hoc網絡移動節點運動的移動模型，即平滑的隨機遊走模型，然後根據該移動模型構造出任意兩個節點的距離隨時間的期望，根據得到的期望構造出每個節點的統計移動尺度，最後基於該移動尺度完成簇頭選舉和簇的劃分，生成穩定的簇結構。 參照圖1，為本發明的實現是確定Ad Hoc網絡應用環境，選取節點移動模型，構造出任意兩個節點間距離期望值的表達式；根據得到的期望表達式構造出每個節點的統計移動尺度；最後基於該移動尺度完成簇頭選舉和簇的劃分。具體步驟如下一 .選取移動模型根據Ad Hoc網絡移動節點實際運行環境選取相應移動模型來模擬節點運動。現有多種移動模型被用來模擬Ad Hoc網絡移動節點的運動，如隨機遊走模型、隨機路徑點模型、組移動模型和平滑的隨機遊走模型。平滑的隨機遊走模型是隨機遊走模型的改進模型，由於平滑的隨機遊走模型對節點運動的模擬更真實且產生的節點空間分布更均勻，仿真結果穩定性更高，所以選用平滑的隨機遊走模型來模擬Ad Hoc網絡移動節點的運動。二.構造出任意兩個節點間距離期望值的表達式根據選取的平滑隨機遊走模型，首先得出移動節點的運動速率Vi⑴和方向MO的分布函數；然後根據所得到的分布函數，得出節點運動速率的期望E[Vi(t)]，方向正弦函數的期望￡[如決(0)]以及餘弦函數的期望￡[COSfe(0)];最後根據所得到的三個期望E[Vi(t)]、￡Isin(io,( ))]、￡[cos(p,(/))]，構造出任意兩移動節點間距離的期望值H(i,」)(t)的表達式,具體步驟如下I.獲得移動節點速率及方向分布函數根據平滑隨機遊走模型，節點的運動速率和方向的改變遵從兩個獨立的泊松過程(N1Uhtxn參數為X1和{N2(t)，t>0}參數為λ2。在平滑隨機遊走模型下節點速率及方向分布函數可表示為
rnrml ,. = ν<ο= (f \ = Wm N2(f) = Q( g \MO-jv,順)矣0和_ —^ JV2(Z)^O其中，Vi(^p%分別為移動節點i初始速率和方向-y為當移動節點的運動速率改變時所選取的新的速率變量，服從Vmin到Vmax均勻分布，即V U[vmin，VmaJ #為當移動節點的運動方向改變時所選取的新的方向變量，服從O到2 Ji的均勻分布，即< 11
可表示為^[ViCO] = v 0 ·PiNl(I) = ^+ v^=-P(Niif) ^0)(9)=Vi0
二移動節點的方向的餘弦期望可《 免(/))]可表示為 ￡[cos(^ ( ))]= cos(約。)· PiN1 (0 = 0)
+ f cos ) ·— φ' ■ p(N2 (t) ψ O)CIO)
Jo2π—
= COS(^0)移動節點的方向的正弦期望￡lsin(>;(0)]可表示為
￡[sin(巧(f))] = sin(^l0) ·e_A-'r( Il J3.構造出任意兩節點間距離的期望考慮一個非常短的時間At，設為10_6秒，在At內節點速度和方向可以看作是不變的，因此有VrerAt+ S0 =^in(At)U2)vrd.A/ + l(iJ)C0 = l(M)(r + A0⑴)其中，表示任意兩個節點i與節點j之間的相對速度向量表示任意兩個節點i，j之間的相對距離向量；瓦表示任意兩個節點i與節點j之間的初始距離向量；根據式(12)和(13)，任意兩節點間距離的向量隨時間期望可以表示為
EIS1U) ( )] = Jo E^re, Vm + A
=￡, (Δθ| · cos φ (M)Vm，
]·:￡_(Δ/)卜(14)
— ^^ν,- ΔοΙ -cos^CAi)]^,,
￡ ￡[|ν,·(Δ/)| · sin φ) (M)Idij } + S0其中， #(均和與(均分別為移動節點i的速率和方向的分布函數；Sin^(Ai)和cosg.(Δ )分別為如Δ0的正弦和餘弦函數狀(_|為速度向量 ,(Δ )的標量值；￡[七]表示任意兩個節點
i,j之間的相對速度向量的期望值；￡[!αΛ(0]表示任意兩個節點i與節點j之間的相對距離向量的期望值；
根據運動距離與運動速度和時間的關係，得出節點i的水平坐標期望皿,(O和垂直坐標期望(O ；
nix. (/) = Jo E[vt (r)] ■ ￡[cos(約(r))]f/ τ + .tj(I(15)
my, (0 = Jo E[Vj ( r)] ·(τ))] τ + ymL16J其中，xi0和yi(l分別表示移動節點i的初始水平和垂直坐標A⑴和Ji (t)表示節點i的水平和垂直坐標；E[Vi ( τ )]為移動節點的節點速率隨時間的期望值，￡[ 執(0)]和￡[Smfe(γ))]分別為節點運動方向的正餘弦隨時間的期望值；將式(14)展開，並將式(15)和(16)代入，得出任意兩個節點i，j之間的相對距離·
向量的期望值;1(0]
Ε Κ-η W] = \[取/ +S0
={￡ (Δ/)| ■ COS φ, (At)Wil, ￡ Epi (Δ/)| · sin φ, (AOWai I
+ (Λ· 0, .ν#ο) - Epj (Δθ| ■ COS φ} (Δ )]<4，(17)
■ :噸(Δ/)| . S φ) } — (XJ0，VyO )
=(/ ' ( ), Itiyl (O) - (Ifhj (t), my] (/))對式(17)兩邊的距離向量取標量，得出任意兩節點間距離的期望值Η(Μ)α)的表達式Hlf il(t) = j(mx ( ),Otv ( )) -(mXj ( ), Ot1j (f))| (18)=」[m' (t) -+ [m,, (/) - m、(i)]2其中,I,(0和％(0為節點速率和方向正餘弦的表達式，可以通過式(15)和(16)求出來。三.構造節點統計移動尺度在分簇開始階段，根據得到的任意兩節點間距離期望值的表達式，按如下步驟計算每個節點的統計移動尺度Stepl :每個移動節點i與它們的一跳鄰居節點交換各自初始狀態信息，包括速率vi(l,方向約。和位置(xi0, yi0)；St印2:移動節點i計算自身以及它的一跳鄰居節點j的橫縱坐標期望值/Jfe1(Z)，mXj(t) , IHvj(T)，然後根據式(18)計算自身與其一跳鄰居節點j的相對距離期望值 Η("α)；St印3 :令H' (Μ) (t)=R-H(i,j) (t)，假設移動節點i的一跳鄰居節點數目為n，通過對移動節點i與其所有一跳鄰居節點的H' (M) (t)值求和得到移動節點i的統計移動尺度值SMM(i，t)，=，其中，R為每個節點的通信半徑。從Step3可知，移動節點i的統計移動尺度值越大，表明移動節點i的一跳鄰居集越大且移動節點i與它的一跳鄰居節點的相對距離越小。而一個大的鄰居集與一個小的相對距離意味著移動節點i與它的一跳鄰居節點運動聯繫更緊密。因此，擁有最大統計移動尺度值的節點可以被選作簇頭。四·選舉簇頭並分配簇成員基於統計移動尺度，採用分布式方式來進行簇頭選舉和簇的劃分，它的目的在於選取高穩定的節點作為簇頭從而形成一個穩定的簇結構。具體步驟如下Stepl :每個移動節點i初始時都處於未分配狀態，它們每隔時間T，0. 5秒，廣播一個IntiHello數據包，IntiHello數據包包含了節點的ID標識Node-IDi,初始位置坐標(xi0, yi0)和橫縱坐標期望值U、及mt(t、；
Step2 :根據接收到的來自一跳鄰居節點的IntiHello包信息，每個處於未分配狀態的節點計算它們的統計移動尺度值SMM(i，t)，如果未分配狀態的節點沒有鄰居節點，則將該節點選為簇頭節點；Step3 :所有移動節點每隔時間T，0. 5秒，都向自身的鄰居節點廣播一個Hello數據包，Hello數據包包含了移動節點的節點標識ID和統計移動尺度值的信息；Step4 :根據接收到的來自一跳鄰居節點的Hello包信息，節點i將自身的統計移動尺度值SMM(i，t)與其所有處於未分配狀態的一跳鄰居節點相比較，如果存在一個一跳鄰居節點j滿足SMM(i，t) < SMM(j, t),則移動節點i任保持初始狀態。反之，如果移動節點i具有最大的統計移動尺度值，則它被選為簇頭節點，同時向其鄰居節點廣播一個JoinRequest消息包的簇邀請，JoinRequest消息包包含節點i的ID標識Node-IDi ；Step5 :如果處於未分配狀態的節點j收到來自其鄰居節點i的JoinRequest消息，則它將改變自身狀態成為簇成員節點，同時向鄰居節點i發送一個Accept應答消息包，並將其所屬簇標識CHj設置為節點i的ID標識Node-IDi,以表面自身屬於鄰居節點i所代表的簇，所述的Accept應答消息包，包含移動節點j的ID標識Node-IDj。Step6 :對已被選為簇頭或分配為簇成員的其它移動節點重複執行St印4和Step5，直到所有移動節點都被選作簇頭或被分配為簇成員，最終完成簇的劃分。本發明的效果通過以下仿真進一步說明I.仿真實驗條件本實驗考慮一個包含50個移動節點的Ad Hoc網絡，移動節點初始位置隨機分布在IOOOm乘IOOOm的平面內，移動節點的運動範圍設置為3000m乘3000m的平面，移動節點的移動模型採用平滑的隨機遊走模型，仿真參數配置如表I所示。表I:仿真參數
權利要求
1.一種基於統計移動尺度的移動感知分簇方法，包括如下步驟 A.根據AdHoc網絡應用環境，選取一個能準確模擬Ad Hoc網絡節點運動的移動模型，即平滑的隨機遊走模型； B.根據選取的平滑隨機遊走模型，得出移動節點的運動速率Vi(t)和方向9u)的分布函數
2.根據權利要求I所述的方法，其中所述步驟D中根據所得到的三個期望E[Vi(t)]、
3.按照權利要求I所述的方法，其中步驟G所述的若移動節點i的統計移動尺度值最大，則將節點i選作簇頭，並將i的一跳鄰居節點分配為移動節點i的簇成員，按如下步驟進行 Gl)移動節點i向其一跳鄰居節點廣播一個JoinRequest消息包的簇邀請，JoinRequest消息包包含節點i的ID標識Node-IDi ； G2)處於未分配狀態的移動節點j收到來自其一跳鄰居節點i的JoinRequest簇邀請消息後，向移動節點i發送一個Accept應答消息包，並將其所屬簇標識(^_設置為節點i的ID標識Node-IDi,以表明自身屬於移動節點i所代表的簇，所述的Accept應答消息包，包含移動節點j的ID標識Node-IDj。
全文摘要
本發明公開了一種基於統計移動尺度的移動感知分簇方法，主要解決現有技術無法對Ad Hoc網絡中的網絡節點進行穩定地分簇組網的問題。其實現步驟為(1)確定Ad Hoc網絡應用環境，選取平滑的隨機遊走模型；(2)根據選取的模型構造出任意兩個節點間距離期望值的表達式；(3)根據期望表達式構造出每個節點的統計移動尺度；(4)基於得到的統計移動尺度採用分布式方式選取高穩定的節點作為簇頭並進行簇成員的分配，最終形成穩定的簇結構。本發明能適應移動節點運動速度和通信半徑變化，且所形成的簇結構更加穩定，可用於在大型移動Ad Hoc網絡中建立類似地面蜂窩網的分級網絡結構，優化網絡的路由查找、拓撲維護以及便於網絡擴展。
文檔編號H04W84/18GK102917385SQ201210418878
公開日2013年2月6日 申請日期2012年10月26日 優先權日2012年10月26日
發明者高新波, 彭建華, 李潔, 宗汝, 張建龍, 馮曉峰, 王旭宇, 呂宗庭, 王旭洋 申請人:西安電子科技大學