移動P2P網絡拓撲構造策略范文

本站小編為你精心準備了移動P2P網絡拓撲構造策略參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

移動p2p網絡已經成為近年來研究熱點領域之一。作為一種新興的移動數據共享方式，移動P2P網絡為人們在無基礎設施支持的環境下提供了一種數據傳輸的解決方案，在軍事戰場、搶險救災以及用戶信息共享等領域具有十分廣闊的應用前景。但是，與傳統P2P系統相比，移動P2P網絡具有節點移動頻繁、移動設備資源受限、無線連接的不可靠以及有限的通信帶寬等特點，這些都給在移動環境中構建P2P系統帶來了巨大挑戰。在移動P2P網絡中，由于節點移動頻繁，覆蓋層無法保持相對持久的穩定性，會導致覆蓋層與底層物理網絡出現拓撲不匹配的情況，即拓撲匹配問題，這不但會引起資源查找和數據傳輸效率低下，而且也會導致較高的網絡維護開銷，浪費寶貴的無線帶寬資源，因此，如何解決拓撲匹配問題，建立高效的資源查找策略是移動P2P網絡研究的核心內容之一。

1相關工作

目前，針對移動P2P網絡覆蓋層拓撲結構以及資源查找策略，許多研究人員對此展開了深入的研究。文獻［3］提出了一個跨層設計的具有拓撲匹配的覆蓋網，利用MAC層多播來定期廣播維護消息，收到維護消息后每個節點比較該節點與鄰居節點間的距離以及各鄰居節點間的最大距離，根據結果刪除距離較長的冗余連接。這一方法雖然解決了拓撲匹配問題，但卻需要廣播大量的維護消息來維護拓撲，因而浪費了寶貴的網絡帶寬資源。文獻［4］建立了一個基于移動內容服務器的移動P2P網絡，通過移動內容服務器管理節點位置信息和一部分共享內容信息。進行查詢時，由移動內容服務器推薦可能的資源擁有者列表及相關的路由信息，從而使查詢節點可以較快地獲得資源信息。這種方法可以較好地避免洪泛所帶來的網絡開銷過大的缺點，但是移動內容服務器存在單點失效的風險。文獻［5］提出了一個基于超節點的移動P2P網絡框架RobP2P，建立了一個雙層結構，上層由穩定的可靠性高的超級節點組成，下層由普通節點組成。雖然該文獻旨在建立一個健壯的、高效的移動P2P網絡，但是，其資源查找仍然是采用洪泛方式，仍然存在網絡開銷過大、耗費節點電量的缺點。文獻［6］構造了具有雙層結構的覆蓋網，通過引入錨節點，建立了基于地理位置信息的覆蓋網并提出相應的資源查找算法，但該方法中如何選取合理的錨節點是一個關鍵問題。文獻［7，8］構建了具有層次結構的Chord環，雖然充分利用了節點異構性強的特點，有利于網絡負載平衡，但是由于覆蓋網的構建通常沒有考慮到移動節點的物理位置，會出現覆蓋網上的鄰居節點可能在物理網絡中相距甚遠，因而大大增加了資源查找時延。通過以上分析可以看出，覆蓋網拓撲結構是整個移動P2P網絡的基礎，只有構建設計合理、健壯的移動P2P網絡拓撲結構，才能提高資源查找的效率，減少因環境變化帶來的性能衰減。因此本文從移動P2P體系結構入手，提出了一種具有拓撲匹配的覆蓋網構造方法，并在此基礎上，提出了相應的資源查找策略，主要目的是提高資源搜索效率，減少用戶訪問時延，降低網絡開銷，提高服務質量。

2基于網格坐標自治域的移動P2P覆蓋網拓撲構造

2.1分層虛擬網格坐標自治域的建立定義1虛擬網格坐標自治域是一個邏輯的二維笛卡爾坐標空間，x軸和y軸將該平面劃分成四個象限，以x軸的右半軸開始沿逆時針方向分別將四個象限命名為1、2、3和4象限。定義2分層虛擬網格坐標自治域是虛擬網格坐標自治域的擴展，將每個象限繼續劃分為四個子象限，以此類推，逐層劃分，就形成了分層虛擬網格坐標自治域。網絡中所有節點最終都要映射到虛擬網格坐標自治域中，為建立虛擬網格坐標自治域，將第一個進入該系統的節點n0確定為引導節點，以n0為原點建立虛擬網格坐標自治域，如圖1所示。整個區域Z可以看做一個大正方形區域，作為第0級網格坐標自治域，將整個區域Z按笛卡爾坐標象限劃分成四個象限，分別定義為Z1、Z2、Z3、Z4，作為第一級網格坐標自治域。按相同方法，可以將每級坐標自治域繼續劃分成更小的子區域，直到所劃分的網格坐標自治域邊長L小于D/槡2為止(這里D表示虛擬網格坐標自治域距離閾值，下文作詳細介紹);將這些最小的正方形區域定義為單位網格坐標自治域，凡是位于同一個單位網格坐標自治域內的任意兩個節點間都是可以相互通信的。如圖1所示，以第一象限Z1為例，坐標自治域從第一級劃分開始，直至第三級，這里，分別對每層自治域的第一象限命名為Z1、Z11、Z111。這里的網格區域用符號Zxxxx表示，其中xxxx從最左邊開始分別表示每一級所屬的第x象限(按笛卡爾坐標象限劃分方法，其值為1、2、3、4)。

2.2構建基于網格坐標自治域的覆蓋網考慮到無基礎設施支持的MANET網絡中，移動節點通常沒有固定的IP地址，無法使用基于IP地址前綴的方法來構建拓撲匹配的覆蓋網，因此，本文將采用更為通用的通信時延作為距離的度量單位，構建具有物理位置感知的移動P2P覆蓋網絡，能夠有效避免因拓撲不一致而產生的繞路現象，從而降低用戶訪問時延，提高網絡工作效率。通常，在物理網絡中，距離較近的節點之間的通信時延也較短。因此，為了構建具有拓撲匹配的移動P2P覆蓋網，將物理網絡中節點之間的時延按著比例映射成為虛擬網格坐標自治域中的距離。例如，物理網絡中節點間通信的傳播時延為1ms可以等價于覆蓋邏輯空間中的1個距離單位，那么，兩個節點ni和nj之間的時延也可以按相同比例映射成覆蓋網上的距離d(ni，nj)。假設兩個節點間的最大通信時延為F(即在該時延F范圍內，兩節點位于彼此的通信范圍，可以直接通信)，那么映射到覆蓋邏輯空間中就有一個距離閾值。已知第一個加入到網絡的節點n0為引導節點，其坐標為(0，0)。n1為第二個加入到P2P網絡的節點，按著前文所述的映射規則，將n0與n1的通信時延映射成為覆蓋網中的距離d(n0，n1)，在虛擬網格坐標自治域中，n1可以選擇在以引導節點n0為中心，以d為半徑的圓周上任意位置，為計算方便，設n1的覆蓋網坐標為(0，d)。第三個加入節點n2的坐標根據n0(0，0)與n1(0，d)的覆蓋網坐標以及n2與n0、n1的通信時延映射成為覆蓋網中的距離d(n2，n0)和d(n2，n1)來確定，有兩個待選位置，分別為pv和pw，如圖1所示。任選一個位置pv作為n2的坐標，這種方法是根據旋轉原則，不會破壞節點在虛擬網格自治域中的相對位置。此時，系統初始化過程完成，取消引導節點。當前三個節點的坐標確定后，其他后續加入節點的虛擬坐標，可以根據已知節點的覆蓋網距離和已知節點的坐標計算獲得。例如，當節點n3要加入移動P2P網絡，如圖1所示，通過n3與之間的通信時延計算出其覆蓋網距離，并且坐標為已知條件，則根據三角函數可以計算出n3的覆蓋網坐標n3(x，y)，根據坐標位置與單位網格坐標自治域的四個頂點坐標(邏輯坐標確定后，由于各個單位自治域邊長為已知，則單位網格坐標自治域的四個頂點坐標就已經確定下來)進行對比，將其劃分到相應的自治域內。圖1中的節點n3位于第一級的第1象限，第二級的第3象限，第三級的第4象限，則n3的標志符表示為(Z134，n3(x，y))，其中Z134是節點n3所在的網格坐標自治域，n3(x，y)為節點n3的覆蓋網坐標。這種映射機制能夠保證物理網絡中距離較近的節點在覆蓋網中也距離較近，從而建立起具有拓撲匹配的移動P2P覆蓋網。

2.3節點移動性處理為了減少節點移動所帶來的擾動，當節點在單位網格坐標自治域內小范圍移動時，對節點的相關信息可以不作修改;只有當節點移出所屬的單位網格坐標自治域時，才更新節點信息，并分配其新的虛擬坐標，這樣可以大幅度減少拓撲維護信息，降低網絡開銷，節省寶貴的無線帶寬資源。更進一步，考慮到那些位于網格自治域邊緣的節點，隨著節點移動，會出現節點在不同網格自治域間來回切換的情況，如果頻繁更新信息，會造成網絡開銷過大。為了解決這一問題，本文引入一個閾值區域，如圖2中所示的灰色地帶，假設位于Z112網格自治域的節點要離開Z112進入到閾值區域(a點)，隨著節點移動，即使節點已經移動到Z113網格自治域時(b點)，但是并不對該節點進行信息更新，直到節點離開閾值區域(c點)，再更新節點的位置信息。通過引入閾值區域，能夠有效減少節點移動性擾動所帶來的通信維護開銷。2.4索引節點的選取在每個單位網格坐標自治域內選出一個索引節點(索引節點選取方法由文獻［9］給出)，然后在上一級網格坐標自治域內重新選出索引節點，直至第0級。當新節點加入網絡時，要將其所共享的資源信息列表發送給其所在的網格自治域的索引節點，即單位網格自治域內的索引節點是需要存儲其域內所有節點的資源索引信息、節點標志、區域標志等。考慮到更高一級的索引節點如果維護其域內全部資源和節點的信息，會導致索引節點維護信息量過大，因此本文規定，較高一級的節點只維護粗略的信息，這里引入一個布爾變量，標志該區域是否有該資源，這樣可以大大降低高級的索引節點信息維護量。考慮到系統容錯性和健壯性，同時選取一個備份索引節點。當索引節點失效時，可以利用備份索引節點進行資源搜索。

3資源查找策略(RSHIN)

下面，針對文中提出的網格坐標自治域結構，提出基于分層索引節點的資源查找策略RSHIN(resourcesearchingstrategybasedonhierarchicalindexnode)。具體查找過程如下:a)當節點S需要查找某一資源R時，S首先向其自身所在的單位網格坐標自治域索引節點I發出資源查尋請求。如果索引節點I保存有存儲資源R的源節點D的信息，則索引節點I將節點D的標志信息發送給S，S與D建立連接;否則轉b)。b)如果索引節點I沒有關于資源R的相關索引信息，則將查詢請求轉發給上一級索引節點，若仍然沒有則再往上一級索引節點進行查詢，逐級往上直至查詢到頂級索引節點為止。若某一級索引節點存有資源R的信息，則轉c)。若均沒有，則本次查找失敗。c)如果某一級索引節點存有資源R(表示該資源的布爾值為l)的信息，則該索引節點向其子區域的索引節點發出查詢，逐級往下直至找到擁有該資源的詳細索引信息的單位自治域內的索引節點為止，然后按著逆向步驟，則該級索引節點將節點D的標志信息發送給S，S與D建立連接。最終完成移動P2P網絡資源查找與共享。下面給出RSHIN算法的偽代碼描述。設拓撲結構劃分深度為depth，m=depth，B是自治域索引節點存儲資源的布爾值(0不存在，1存在);F表示是否為單位自治域(0是，1否)。

4仿真實驗與結果分析

為了驗證本文所提出的資源查找策略RSHIN的有效性，本文采用NS-2作為仿真實驗平臺，進行了仿真實驗。實驗場景參數設置:節點隨機分布在4000m×4000m的區域內，節點移動速度為0～10m/s，節點通信半徑為200m。移動節點個數在120～600，節點移動模型符合隨機路點模型［10］，假設節點停留時間為10s。無線通信帶寬為2Mbps，MAC層采用802．11協議。假設每個節點擁有10個共享資源，資源大小為512Byte，發送速率為300kbps，發送節點和接收節點隨機產生，每秒產生10個節點。文獻［11］提出的CAR資源查找策略采用了基于地理位置信息的哈希索引結構，為了評價本文提出的查找策略，將RSHIN與CAR策略進行仿真實驗，并對結果作出分析。首先考察不同節點密度對資源查找平均路徑長度的影響。資源查找路徑長度可以用跳數來度量。移動節點個數為120～600，每隔60取一個值，仿真實驗結果如圖3所示。可以看出，隨著節點數量的增加，RSHIN查找策略的平均查找路徑長度明顯小于CAR的查找策略，主要是由于RSHIN采用層級遞進的查詢策略，并根據節點的坐標與網格坐標自治域信息，可以快速定位到資源節點的位置，因此提高了資源查找效率。接下來考察不同節點密度對資源查找成功率的影響。如圖4所示，隨著節點數量不斷增加，兩種算法的查找成功率都有所提升，但本文所提出的RSHIN查找策略要優于CAR算法。本文通過采取后備索引節點，當含有資源的葉子節點對應的資源節點失效時，資源查詢信息快速地通過其域內的后備索引節點找到目的節點，從而可以有效降低索引節點失效而導致的性能下降，并且大大提高了資源查找成功率。

5結束語

本文提出了一種具有拓撲匹配的網格坐標自治域結構，充分考慮了物理網絡中節點之間的位置關系，將物理鄰近的節點劃分到相同或者相鄰的單位網格坐標自治域內，即保證物理鄰近的節點在覆蓋網上也鄰近，從而可以有效減少由于拓撲不匹配而產生的網絡性能下降等問題。考慮到節點移動擾動，引入閾值區域，可以有效降低網絡維護開銷。針對該拓撲結構，提出基于索引節點的資源查找策略RSHIN。仿真實驗結果表明，該資源查找策略可以有效提升網絡查找效率，降低數據訪問延遲，提高了網絡可用性及可擴展性。下一步工作中將主要研究如何進一步減少信息的冗余與節點能量的消耗問題。

作者：周欣欣 高越 宋人杰 余鎮危 單位：東北電力大學 信息工程學院 中國礦業大學( 北京) 機電與信息工程學院