一種行動網路中自組建路由的方法及裝置的製作方法
2023-09-20 21:40:25 2
專利名稱：一種行動網路中自組建路由的方法及裝置的製作方法
技術領域：
本發明涉及行動網路通信領域，尤其涉及一種行動網路中自組建路由的方法及裝置。
背景技術：
目前行動網路查找路由的方法主要有一下兩種1、在對等網絡中固定每個節點維 護一個本地知識庫，根據維護的本地知識庫進行資源的本地查找，本地知識庫僅對本域內 的節點進行維護；2、當網絡中存在資源管理設備時，由伺服器發起設備向資源管理設備發 起服務查找請求；當網絡中不存在資源管理設備時，先通過伺服器發起設備在本地查找，未 查找到時向建立好對等連接的設備發起服務查找請求。在實現本發明過程中，發明人發現現有技術中至少存在如下問題方法1中，不適 應整個網絡，並且也沒有考慮節點的移動性對路由機制帶來的影響；方法2中沒有考慮到 行動網路的移動性帶來的拓撲適配問題，造成路由的效率較低。
發明內容
本發明的實施例提供了一種行動網路中自組建路由的方法及裝置，克服網絡適配 問題，適合整體網絡中路由的查找。本發明實施例提供了一種行動網路中自組建路由的方法，包括超級節點A根據接收的路由查找請求確定目標節點，並獲得與目標節點之間的距 罔；根據確定的所述超級節點A與所述目標節點之間的距離確定所述目標節點在所 述超級節點A的第i個動態拓撲環內，i為大於等於0的整數；若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目標節點之間距離 最近的是所述超級節點A，則組建超級節點A與目標節點之間的路由為超級節點A到目標節
點ο本發明實施例還提供了一種行動網路中自組建路由的裝置，包括距離確定模塊，用於確定行動網路中的超級節點A與目標節點之間的距離；拓撲環確定模塊，用於根據距離確定模塊確定的所述超級節點A與所述目標節點 之間的距離確定所述目標節點在所述超級節點A的第i個動態拓撲環內，i為大於等於0的 整數；組建路由模塊，用於若所述超級節點A的第i個動態拓撲環內的超級節點中與所 述目標節點之間距離最近的是所述超級節點A，則組建超級節點A與目標節點之間的路由 為超級節點A到目標節點。由上述本發明的實施例提供的技術方案可以看出，其採用超級節點的動態拓撲環 機制構造網絡拓撲，克服了網絡適配問題，適合整體網絡中路由的查找。
為了更清楚地說明本發明實施例的技術方案，下面將對實施例描述中所需要使用 的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對於本 領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他 的附圖。圖1為本發明實施例所述的一種行動網路中自組建路由方法的流程示意圖；圖2(a)為本發明實施例所述的一種行動網路中自組建路由方法中在超級節點A 的第i個動態拓撲環內的超級節點中與目標節點D最近的是超級節點A的示意圖，圖中
「 ο 」表示超級節點，「 · 」表示目標節點，「___」和「 ^一 均表示超級節點與目標
節點之間的距離；圖2(b)為本發明實施例所述的一種行動網路中自組建路由方法中在超級節點A 的第i個動態拓撲環內的超級節點中與目標節點D最近的是超級節點B的示意圖，圖中
「 ο 」表示超級節點，「 · 」表示目標節點，「___」和《 -一 ，,均表示超級節點與目標
節點之間的距離；圖2(c)為本發明實施例所述的一種行動網路中自組建路由方法中在超級節點B 的第j個動態拓撲環內的超級節點中與目標節點D最近的是超級節點C的示意圖，圖中
「 ο 」表示超級節點，「 · 」表示目標節點，「___」和「 -一 ，,均表示超級節點與目標
節點之間的距離；圖3 (a)為本發明實施例所述的一種行動網路中自組建路由方法中步驟15中在超 級節點B的第j個動態拓撲環內的超級節點中與目標節點D最近的是超級節點B的網絡架 構圖；圖3(b)為本發明實施例所述的一種行動網路中自組建路由方法中步驟15中在超 級節點B的第j個動態拓撲環內的超級節點中與目標節點D最近的是超級節點C，且根據超 級節點C與所述目標節點D之間的距離確定的超級節點C的第k個動態拓撲環內的超級節 點中與所述目標節點D之間距離最近的是超級節點C的網絡架構圖；圖4為本發明實施例所述的一種行動網路中自組建路由方法中實時檢測節點移 出動態拓撲環或行動網路的概率，並更新路由的方法示意圖；圖5為本發明實施例所述的一種行動網路中自組建路由裝置的結構示意圖。
具體實施例方式下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完 整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於 本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他 實施例，都屬於本發明保護的範圍。移動P2P (Peer-to-Peer，對等網絡)是一種作為共享和管理網絡中海量信息資源 的分布式計算模式，主要是各個節點之間通過直接交換來共享資源和服務，P2P中每個用戶 就是一個節點，數據傳輸通過節點進行，不需要很多的中央伺服器，但為了保證數據傳輸質 量，P2P會自動分析每個節點的硬體資源，讓有較大帶寬和高速計算機或終端擔任「超級節 點」，一定數量的超級節點和數千萬的普通節點，共同組成了 P2P，超級節點和普通節點都是
6可以移動的，一旦超級節點失效(超級節點移出另一超級節點的第i個動態拓撲環或者移 出P2P網絡)，那麼超級節點就變回普通節點，這時P2P再將其它功能強大的普通節點設置 為超級節點。。本發明實施例提供了一種行動網路中自組建路由的方法，如圖1所示，包括步驟11、超級節點A接收路由查找請求，確定目標節點D，其中目標節點D可以是 超級節點，也可以是普通節點；行動網路中超級節點A的動態拓撲環的半徑為當i等於0時，所述動態拓撲環的內半徑= 0，外半徑Rtl = ρ ；當i大於等於1時，所述動態拓撲環的內半徑A = PtfH^外半徑Ri = Pti ；其中i為大於等於0的整數，t為變量，表示動態拓撲環的增長因子；ρ為常量；ρ 和t都根據行動網路通信質量確定；步驟12、根據延時測量獲得超級節點A與目標節點D之間的距離是Cl1 ；步驟13、獲得Cl1在ri和Ri之間，則確定目標節點D在超級節點的第i個動態拓撲 環內，並判斷在超級節點A的第i個動態拓撲環內的超級節點中與目標節點D最近的是否 是超級節點A，若是，則執行步驟14，若否則執行步驟15 ；步驟14、如圖2(a)所示，在超級節點A的第i個動態拓撲環內的超級節點中與目 標節點D最近的是超級節點A，則組建超級節點A與目標節點D之間的路由為超級節點A到 目標節點D。步驟15、如圖2(b)所示，在超級節點A的第i個動態拓撲環內的超級節點中與目 標節點D最近的是超級節點B，即超級節點B與目標節點D之間的距離d2小於Cl1，那麼超級 節點A將路由查找請求發送給超級節點B，超級節點B重複執行超級節點A的步驟11-步 驟13，直到可以執行步驟14，則確定超級節點A與目標節點D之間的路由為超級節點A到 超級節點B到目標節點D，具體的網絡架構圖如圖3(a)所示；具體地，超級節點B接收路由查找請求，確定目標節點D，並根據延時測量獲得超 級節點與目標節點之間的距離d2，d2在超級節點B的動態拓撲環內徑Tj和外徑Rj之間，則 確定目標節點D在超級節點B的第j個動態拓撲環內；判斷在超級節點B的第j個動態拓 撲環內的超級節點中與目標節點D最近的是否是超級節點B，若是，則確定超級節點A與目 標節點D之間的路由是超級節點A到超級節點B到目標節點D ；若如圖2(c)所示，在超級 節點B的第j個動態拓撲環內的超級節點中與目標節點D最近的是超級節點C，那麼超級節 點B將路由查找請求發送給超級節點C，超級節點C重複執行上述過程，直到根據超級節點 C與所述目標節點D之間的距離確定的超級節點C的第k個動態拓撲環內的超級節點中與 所述目標節點D之間距離最近的是超級節點C，則組建超級節點A與目標節點D之間的路 由為超級節點A到超級節點B到超級節點C到目標節點D，具體的網絡架構圖如圖3(b)所 示，j和k均為大於等於0的整數。如圖4所示，上述方法中還可以包括實時檢測節點移出動態拓撲環或行動網路的 概率，即實時檢測節點的失效率，並更新路由的過程步驟41、根據超級節點B運動的速度確定超級節點B移出所述超級節點A的第i 個動態拓撲環的概率，包括
其中ν表示超級節點B運動的速度，同理，根據超級節點C運動的速度確定的超級節點C移出所述超級節點B的第j 個動態拓撲環的概率也可通過上述公式獲得。步驟42、若獲得的超級節點B移出所述超級節點A的第i個動態拓撲環的概率或 超級節點C移出所述超級節點B的第j個動態拓撲環的概率超過預定值，所述預定值是根 據網絡通信質量或用戶需求確定，則增大或減小所述超級節點A的第i個動態拓撲環的半 徑或所述超級節點B的第j個動態拓撲環的半徑，具體通過調整ρ的值來增大或減小動態 拓撲環的半徑。步驟43、根據超級節點A或B或C運動的速度確定所述超級節點A或B或C移出 行動網路的概率，具體當i = j = k時包括
其中 j*表示所述超級節點
A或B或C的動態拓撲環的總環數。步驟44、若獲得的超級節點A或B或C移出行動網路的概率超過特定值，所述特定 值是根據網絡通信質量或用戶需求確定，則重新確定所述超級節點A或B或C與所述目標 節點D之間的路由，具體地，若獲得的超級節點A移出行動網路的概率超過特定值，則重新 執行圖1中的步驟11，直到重新確定超級節點A與目標節點之間的路由；若獲得的超級節 點B移出行動網路的概率超過特定值，則重新執行圖1中的步驟15，無需重新確定超級節點 A與超級節點B之間的路由，若獲得的超級節點C移出行動網路的概率超過特定值，則重新 獲得超級節點C與目標節點D之間的路由，無需重新確定超級節點A到超級節點B到超級 節點C之間的路由，以此類推，後續的超級節點亦然。本發明實施例採用超級節點的動態拓撲環機制構造網絡拓撲，由於各個參數都是 底層實際的物理距離，克服了網絡適配問題，通過實時獲取超級節點移出拓撲環或移動網 絡的概率，並相應進行調整，降低了節點頻繁移動對網絡的影響，適合整體網絡中路由的查 找。本領域普通技術人員可以理解實現上述實施例方法中的全部或部分流程，是可以 通過電腦程式來指令相關的硬體來完成，所述的程序可存儲於一計算機可讀取存儲介質 中，該程序在執行時，可包括如上述各方法的實施例的流程。其中，所述的存儲介質可為磁 碟、光碟、只讀存儲記憶體(Read-Only Memory, ROM)或隨機存儲記憶體(Random Access Memory, RAM)等。本發明實施例還提供了一種行動網路中自組建路由的裝置，如圖5所示，包括距離確定模塊51，用於確定行動網路中的超級節點A與目標節點之間的距離；拓撲環確定模塊52，用於根據距離確定模塊51確定的所述超級節點A與所述目標 節點之間的距離確定所述目標節點在所述超級節點A的第i個動態拓撲環內，i為大於等 於0的整數；具體地，所述超級節點A的第i個動態拓撲環的半徑，包括
當i等於0時，所述動態拓撲環的內半徑A = 0，外半徑Rtl = ρ ；當i大於等於1時，所述動態拓撲環的內半徑A = PtfH^外半徑Ri = Pti ；其中t為變量，表示網絡拓撲環的增長因子；ρ為常量；P和t都根據行動網路通信
質量確定。組建路由模塊53，用於若所述超級節點A的第i個動態拓撲環內的超級節點中與 所述目標節點之間距離最近的是所述超級節點A，則組建超級節點A與目標節點之間的路 由為超級節點A到目標節點，那麼行動網路中自組建路由的裝置就是超級節點A ；具體地，還用於若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目 標節點之間距離最近的是超級節點B，則組建超級節點A與目標節點之間的路由為超級節 點A到超級節點B到目標節點，那麼行動網路中自組建路由的裝置就是超級節點A和超級 節點B ；或者超級節點A將所述路由請求發送超級節點B，若根據所述超級節點B與所述目 標節點之間的距離確定的超級節點B的第j個動態拓撲環內的超級節點中與所述目標節點 之間距離最近的是超級節點C，則超級節點B將所述路由請求發送超級節點C，直到根據所 述超級節點C與所述目標節點之間的距離確定的超級節點C的第k個動態拓撲環內的超級 節點中與所述目標節點之間距離最近的是超級節點C，組建超級節點A與目標節點之間的 路由為超級節點A到超級節點B到超級節點C到目標節點，j和k均為大於等於0的整數， 超級節點B和C的動態拓撲環的半徑與超級節點A的動態拓撲環的半徑的確定方式相同。上述裝置中，還包括概率確定模塊，用於根據所述超級節點B或C運動的速度確定所述超級節點B移 出所述超級節點A的第i個動態拓撲環或所述超級節點B的第j個動態拓撲環的概率以及 所述超級節點A或B或C移出行動網路的概率；具體地，超級節點B移出所述超級節點A的第i個動態拓撲環的概率，包括 其中ν表示超級節點A或B運動的速度；超級節點C移出所述超級節點B的第j 個動態拓撲環的概率也由此確定；所述超級節點A或B或C移出行動網路的概率，當i = j = k時包括 其中j *表示所述超級節點A或B或C的動態拓撲環的總環數。調整模塊，若所述概率確定模塊確定的所述超級節點B或C移出所述超級節點A 的第i個動態拓撲環或所述超級節點B的第j個動態拓撲環的概率超過預定值，則增大或 減小所述超級節點A的第i個動態拓撲環的半徑或所述超級節點B的第j個動態拓撲環得 半徑；若所述概率確定模塊確定的所述超級節點A或B或C移出行動網路的概率超過特定 值，則所述超級節點A或B或C重新確定與所述目標節點之間的路由，所述預定值和特定值 都根據網絡通信質量或用戶需求確定；具體地，若獲得的超級節點A移出行動網路的概率超過特定值，則重新確定超級 節點A與目標節點之間的路由；若獲得的超級節點B移出行動網路的概率超過特定值，則重新確定超級節點B與目標節點之間的路由，無需重新確定超級節點A與超級節點B之間的 路由；若獲得的超級節點C移出行動網路的概率超過特定值，則重新確定超級節點C與目標 節點之間的路由，無需重新確定超級節點A與超級節點C之間的路由，即超級節點A到超級 節點B到超級節點C。上述裝置中包含的各模塊的處理功能的具體實現方式在之前的方法實施例中已 經描述，在此不再重複描述。本發明實施例採用超級節點的動態拓撲環機制構造網絡拓撲，由於各個參數都是 底層實際的物理距離，克服了網絡適配問題，通過實時獲取超級節點移出拓撲環或移動網 絡的概率，並相應進行調整，降低了節點頻繁移動對網絡的影響，適合整體網絡中路由的查 找。以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此， 任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換， 都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求的保護範圍 為準。
權利要求
一種行動網路中自組建路由的方法，其特徵在於，包括超級節點A根據接收的路由查找請求確定目標節點，並獲得與目標節點之間的距離；根據確定的所述超級節點A與所述目標節點之間的距離確定所述目標節點在所述超級節點A的第i個動態拓撲環內，i為大於等於0的整數；若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目標節點之間距離最近的是所述超級節點A，則組建超級節點A與目標節點之間的路由為超級節點A到目標節點。
2.根據權利要求1所述的方法，其特徵在於，還包括若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目標節點之間距離最近 的是超級節點B，則組建超級節點A與目標節點之間的路由為超級節點A到超級節點B到目 標節點；或者超級節點A將所述路由請求發送超級節點B，若根據所述超級節點B與所述目 標節點之間的距離確定的超級節點B的第j個動態拓撲環內的超級節點中與所述目標節點 之間距離最近的是超級節點C，則超級節點B將所述路由請求發送超級節點C，直到根據所 述超級節點C與所述目標節點之間的距離確定的超級節點C的第k個動態拓撲環內的超級 節點中與所述目標節點之間距離最近的是超級節點C，組建超級節點A與目標節點之間的 路由為超級節點A到超級節點B到超級節點C到目標節點，j和k均為大於等於0的整數。
3.根據權利要求1所述的方法，其特徵在於，所述超級節點A的第i個動態拓撲環的半 徑、超級節點B的第j個動態拓撲環的半徑或者超級節點C的第k個動態拓撲環的半徑，當 i = j = k時包括當i等於0時，所述動態拓撲環的內半徑A = 0，外半徑Rtl = ρ ；當i大於等於1時，所述動態拓撲環的內半徑A = Pti^,外半徑Ri = Pti ；其中t為變量，表示動態拓撲環的增長因子；ρ為常量；ρ和t都根據行動網路通信質量 確定。
4.根據權利要求1或2所述的方法，其特徵在於，還包括根據所述超級節點B或C運動的速度確定所述超級節點B或C移出所述超級節點A的 第i個動態拓撲環或所述超級節點B的第j個動態拓撲環的概率，以及所述超級節點A或 B或C移出行動網路的概率，若所述超級節點B或C移出所述超級節點A的第i個動態拓 撲環或所述超級節點B的第j個動態拓撲環的概率超過預定值，則增大或減小所述超級節 點A或B的第i個或第j個動態拓撲環的半徑；若所述超級節點A或B或C移出行動網路 的概率超過特定值，則所述超級節點A或B或C重新確定與所述目標節點之間的路由，所述 預定值和特定值都根據網絡通信質量或用戶需求確定。
5.根據權利要求4所述的方法，其特徵在於，所述超級節點A或B移出所述超級節點A 或B的第i或j個動態拓撲環內的概率，當i = j時包括 表示超級節點A或B運動的速度；所述超級節點A或B移出行動網路的概率，包括 或B的動態拓撲環的總環數。
6.一種行動網路中自組建路由的裝置，其特徵在於，包括距離確定模塊，用於確定行動網路中的超級節點A與目標節點之間的距離；拓撲環確定模塊，用於根據距離確定模塊確定的所述超級節點A與所述目標節點之間 的距離確定所述目標節點在所述超級節點A的第i個動態拓撲環內，i為大於等於0的整 數；組建路由模塊，用於若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目 標節點之間距離最近的是所述超級節點A，則組建超級節點A與目標節點之間的路由為超 級節點A到目標節點。
7.根據權利要求6所述的裝置，其特徵在於，所述組建路由模塊，還用於若所述超級節 點A的第i個動態拓撲環內的超級節點中與所述目標節點之間距離最近的是超級節點B，則 組建超級節點A與目標節點之間的路由為超級節點A到超級節點B到目標節點；或者超級 節點A將所述路由請求發送超級節點B，若根據所述超級節點B與所述目標節點之間的距 離確定的超級節點B的第j個動態拓撲環內的超級節點中與所述目標節點之間距離最近的 是超級節點C，則超級節點B將所述路由請求發送超級節點C，直到根據所述超級節點C與 所述目標節點之間的距離確定的超級節點C的第k個動態拓撲環內的超級節點中與所述目 標節點之間距離最近的是超級節點C，組建超級節點A與目標節點之間的路由為超級節點A 到超級節點B到超級節點C到目標節點，j和k均為大於等於0的整數。
8.根據權利要求6或7所述的裝置，其特徵在於，所述拓撲環確定模塊中所述超級節點 A的第i個動態拓撲環的半徑、所述組建路由模塊中所述超級節點B的第j個動態拓撲環 的半徑或者所述組建路由模塊中所述超級節點C的第k個動態拓撲環的半徑，當i = j = k時包括當i等於0時，所述動態拓撲環的內半徑= 0，外半徑Rtl = ρ ；當i大於等於1時，所述動態拓撲環的內半徑A = Pti^,外半徑Ri = Pti ；其中t為變量，表示網絡拓撲環的增長因子；ρ為常量；ρ和t都根據行動網路通信質量 確定。
9.根據權利要求6或7所述的裝置，其特徵在於，還包括概率確定模塊，用於根據所述超級節點B或C運動的速度確定所述超級節點B或C移 出所述超級節點A的第i個動態拓撲環或所述超級節點B的第j個動態拓撲環的概率，以 及所述超級節點A或B或C移出行動網路的概率；調整模塊，若所述概率確定模塊確定的所述超級節點B或C移出所述超級節點A的第 i個動態拓撲環或所述超級節點B的第j個動態拓撲環的概率超過預定值，則增大或減小 所述超級節點A或B的第i個或第j個動態拓撲環的半徑；若所述概括確定模塊確定的所 述超級節點A或B或C移出行動網路的概率超過特定值，則所述超級節點A或B或C重新 確定與所述目標節點之間的路由，所述預定值和特定值都根據網絡通信質量或用戶需求確 定。
10.根據權利要求9所述的裝置，其特徵在於，概率確定模塊中所述超級節點A或B移 出所述超級節點A或B的第i或j個動態拓撲環內的概率，當i = j時包括 其中V表示超級節點A或B運動的速度； 所述超級節點A或B移出行動網路的概率，當i = j時包括 其中j *表示所述超級節點A或B的動態拓撲環的總環數。
全文摘要
一種行動網路中自組建路由的方法及裝置，首先，超級節點A根據接收路由查找請求確定目標節點，並獲得與目標節點之間的距離；然後，根據確定的所述超級節點A與所述目標節點之間的距離確定所述目標節點在所述超級節點A的第i個動態拓撲環內；最後，若所述超級節點A的第i個動態拓撲環內的超級節點中與所述目標節點之間距離最近的是所述超級節點A，則組建超級節點A與目標節點之間的路由為超級節點A到目標節點。本發明實施例採用超級節點的動態拓撲環機制構造網絡拓撲，克服了網絡適配問題，適合整體網絡中路由的查找。
文檔編號H04W40/20GK101895958SQ20101013702
公開日2010年11月24日 申請日期2010年3月30日 優先權日2010年3月30日
發明者樂冠, 宋美娜, 屈海濤, 張曉奇, 楊健, 羅耀平, 許可, 陳輝 申請人:華為終端有限公司;北京郵電大學