一種機會網絡的鏈路預測方法
2023-10-09 01:28:59 1
一種機會網絡的鏈路預測方法
【專利摘要】本發明公開了一種機會網絡的鏈路預測方法，首先對所有可能的節點對進行分類，分成周期性相遇的節點對集合、頻繁非周期性相遇的節點對集合以及非頻繁相遇的節點對集合；然後在每個不同的節點對集合上使用不同的方法進行鏈路預測，使用周期模式挖掘的方法預測周期性相遇的節點對集合，使用J48決策樹方法預測頻繁非周期性相遇的節點對集合，使用複雜網絡中的Adamic-Adar算法預測非頻繁相遇的節點對集合。通過上述方式，本發明解決了單一的鏈路預測方法適用範圍受限的問題，能夠提高機會網絡鏈路預測的精度和召回率，從而提高機會網絡的消息投遞效率和容量。
【專利說明】一種機會網絡的鏈路預測方法
【技術領域】
[0001] 本發明涉及網絡【技術領域】，特別是涉及一種機會網絡的鏈路預測方法。
【背景技術】
[0002] 1、所屬【技術領域】發展歷程 機會網絡是一種由移動自組織網絡發展而來的新型網絡架構，它能夠在分割的網絡條 件下利用節點移動帶來的相遇機會實現報文的逐跳轉發，並最終投遞到目的節點。相遇概 念是指節點之間發生的一次聯繫：當節點進入彼此的通信範圍之內（比如Wi-Fi或者藍牙 協議的點到點通信距離內）時，則建立連結，發生通信，當兩者離開彼此通信範圍時，則鏈路 斷開，停止通信。由於節點的移動性，機會網絡中的相遇是機會性的，而非確定性的，不存在 可靠的端到端通信路徑。
[0003] 如圖1-圖3所示，機會網絡採用"存儲-攜帶-轉發"的工作模式進行多跳的消 息投遞，若當前節點沒有遇到通往目標節點的下一跳節點時，就緩存消息，並隨節點的移動 尋找合適的轉發機會。如圖1中A時刻，不存在源節點S到目的節點D的直接路徑，節點S 將消息轉發給節點3,由其存儲攜帶，到了圖2中的t 2時刻，消息又轉發給了節點4,直到圖 3中的t3時刻，節點4和目的節點D運動到了同一連通區域，就將消息成功轉發。
[0004] 利用機會網絡架構，可以不依賴基礎設施或者僅需要少量的基礎設施在偏遠高速 公路、城市交通、移動社交等場景下實現消息投遞、內容分發、資源共享等功能。但它們的性 能和用戶體驗很大程度上依賴於機會網絡所能提供的網絡傳輸服務。現有的機會網絡仍存 在一些問題：（1)消息投遞的成功率不高，超過生命期或者緩存溢出都會導致消息在投遞 過程中被丟棄，投遞成功率一般在50% ; (2)消息投遞延遲較高，由於網絡動態性導致存儲 攜帶的盲目性較大，可能需要數小時或者數天才能成功投遞消息；（3)多個副本在網絡中 存儲並轉發，這必然會佔用大量的存儲並且導致高能量消耗；（4)由於網絡缺乏實時性，網 絡服務是否可達，服務等待時間也無法預知，顯著降低了用戶體驗。
[0005] 解決以上問題的關鍵在於把握單個節點、鄰接節點以及整個網絡拓撲的動態變化 規律，通過預測的方法來緩解網絡動態性帶來的難題。
[0006] 2、現有技術情況 機會網絡中現有的預測方法可以分為基於上下文的、基於移動模型的和基於社會關係 的預測。多數早期的機會網絡路由方法都使用諸如歷史相遇次數或者持續時間等指標作為 轉發效用，轉發效用更高的節點優先被選作轉發節點。這些方法過於簡單而無法發現更有 價值的相遇規律。基於移動模型的預測方法建模描述人類移動的時空屬性，並據此預測消 息轉發的效用。大多數使用社會關係預測方法都需要從在線的社交網絡應用中導入或者通 過手工配置的方法得到社會關係屬性，也有一些預測方法可以自動檢測社會關係屬性，然 後利用這些社會關係屬性作為消息轉發的效用。現有的這些基於轉發效用的鏈路預測方法 都只能處理一部分的節點對之間的鏈路預測問題，對於相遇模式差異很大的整個機會網絡 來說，單一的鏈路預測方法難以實現整體的性能最優。
[0007] 以東南大學校園內的Wi-Fi跟蹤數據集為例，當兩個節點同時關聯到一個Wi-Fi 接入點的時候，認為兩個節點有一次相遇。統計結果顯示，在所有可能的節點對之間，有相 遇記錄的節點對比例隨著時間增加，最終經過一周的測量，有35%的節點對相遇過，而在相 遇過的節點中，有22%的節點對呈現周期性規律，78%的節點對相遇記錄沒有周期性。顯然 對於周期性的節點對、非周期性的節點對以及未曾相遇過的節點對的未來相遇情況的預測 是不同的問題，現有的單一的預測方法不能處理所有的預測問題，現有方法也沒有探討如 何劃分不同類型的節點對集合，以及在每個節點對集合上如何選擇最優的預測方法。
【發明內容】
[0008] 本發明主要解決的技術問題是：針對現有技術的不足，提供一種機會網絡的鏈路 預測方法，能夠提高機會網絡鏈路預測的精度和召回率，從而提高機會網絡的消息投遞效 率和容量。
[0009] 為解決上述技術問題，本發明採用的一個技術方案是：提供一種機會網絡的鏈路 預測方法，包括以下步驟： (100)時間片劃分：將節點集合上發生的相遇記錄按照長度劃分成一系列等長的時間 片，每個時間片上根據相遇記錄得到一個矩陣； (200)預處理：中心伺服器通過移動通信網絡連接獲取機會網絡中所有節點之間的相 遇記錄，然後使用周期模式挖掘方法在相遇記錄集合中篩選出周期性相遇的節點對集合， 最後對剩下的節點對集合基於相遇頻率閾值進行分類，分成頻繁非周期性相遇的節點對集 合與非頻繁相遇的節點對集合； (300)在線預測：分別使用周期模式挖掘的方法預測周期性相遇的節點對集合，使用決 策樹方法預測頻繁非周期性相遇的節點對集合，使用複雜網絡的方法預測非頻繁相遇的節 點對集合。
[0010] 在本發明一個較佳實施例中，所述步驟（300)中的決策樹方法為J48決策樹方法。
[0011] 在本發明一個較佳實施例中，所述步驟（300)中的複雜網絡的方法為 Adamic-Adar 算法。
[0012] 在本發明一個較佳實施例中，所述步驟（300)中的周期模式挖掘的方法包括： (a) 設Pi」表示節點對（i，j)，Sp (Pj表示節點對Pi」在時間片序列上周期相遇的時 間片集合，即：
【權利要求】
1. 一種機會網絡的鏈路預測方法，其特徵在於，包括以下步驟： (100)時間片劃分：將節點集合上發生的相遇記錄按照長度劃分成一系列等長的時間 片，每個時間片上根據相遇記錄得到一個矩陣； (200)預處理：中心伺服器通過移動通信網絡連接獲取機會網絡中所有節點之間的相 遇記錄，然後使用周期模式挖掘方法在相遇記錄集合中篩選出周期性相遇的節點對集合， 最後對剩下的節點對集合基於相遇頻率閾值進行分類，分成頻繁非周期性相遇的節點對集 合與非頻繁相遇的節點對集合； (300)在線預測：分別使用周期模式挖掘的方法預測周期性相遇的節點對集合，使用決 策樹方法預測頻繁非周期性相遇的節點對集合，使用複雜網絡的方法預測非頻繁相遇的節 點對集合。
2. 根據權利要求1所述的一種機會網絡的鏈路預測方法，其特徵在於，所述步驟（300) 中的決策樹方法為J48決策樹方法。
3. 根據權利要求1所述的一種機會網絡的鏈路預測方法，其特徵在於，所述步驟（300) 中的複雜網絡的方法為Adamic-Adar算法。
4. 根據權利要求1所述的一種機會網絡的鏈路預測方法，其特徵在於，所述步驟（300) 中的周期模式挖掘的方法包括： (a) 設Pij表示節點對（i，j)，Sp (Pij)表示節點對Pij在時間片序列上周期相遇的時 間片集合，即：
其中，P表示周期長度； (b) 設η表示Sp (Pi1)中周期重複的次數，即：
(c) 然後tmd+p就是下一個周期點，S(Pu)上周期重複次數稱為預測tmd+p的周期支持 度，一個節點對上可能有多個不同周期長度的周期模式，如果存在一個周期模式S(P u)使 得tmd+p對應到帶預測時間片tx+1，就預測會相遇五U = 1，否則預測不相遇4+1 = 0。
【文檔編號】H04L12/24GK104378229SQ201410595581
【公開日】2015年2月25日 申請日期:2014年10月30日 優先權日:2014年10月30日
【發明者】張三峰, 李茵 申請人:東南大學