[發明專利]一種基于費馬點的移動Ad-Hoc網絡路由算法

在審

• 申請號: 201810100318.5
• 申請日: 2018-02-01
• 公開（公告）號: CN110167095A
• 公開（公告）日: 2019-08-23
• 發明（設計）人: 介璽;郭新海;朱林;黃志英;耿琳瑩
• 申請（專利權）人: 西安電子科技大學;中國人民解放軍63886部隊
• 主分類號: H04W40/04
• 分類號: H04W40/04;H04W40/20;H04W40/22;H04W52/02;H04W84/18
• 代理公司: 北京華仲龍騰專利代理事務所(普通合伙) 11548
• 代理人: 李靜

本發明公開了一種基于費馬點的移動Ad?Hoc網絡路由算法，包括如下步驟：通過信源節點和兩個目的節點組成的三角形的位置信息，計算得到對應的費馬點，即到上述三個頂點的距離之和最小的點，把費馬點或者相鄰位置的傳感器節點作為中繼節點；當信源節點向目的節點傳輸數據時，先把數據沿一條路徑傳輸給中繼節點，然后再由中繼節點將數據分別發送給目的節點。本發明對在移動Ad?Hoc網絡中基于節點移動的節能降耗問題進行了針對性的研究，在保證數據傳輸的可靠性的前提下，可以明顯降低數據傳輸的邏輯距離，減少網絡內的傳輸時延，從而達到降低網絡整體能耗的效果。

技術領域

本發明涉及一種算法，具體是一種基于費馬點的移動Ad-Hoc網絡路由算法。

背景技術

移動Ad-Hoc網絡（MANET，MobileAdHocNetwork）是一種特殊的自組織網絡。網絡中的節點地位平等，沒有中心節點的同時具有無線收發功能，因此它可以不依賴基礎設施而臨時組建成一個臨時性自治系統，當節點不在彼此的通信范圍內時，可以借助其它節點作為中繼來實現多跳通信。除了具有無中心性、自組織性等特點，移動Ad-Hoc網絡還具有分布式處理、可移動性等特點，使得它具有可臨時快速組網、抗毀性強、無需基礎設施等優點，現在多用于環境監測、軍事、公共安全、智能家居等領域。

但是移動Ad-Hoc網絡也有很明顯的缺點。一方面網絡內的傳感器節點在能量、計算和存儲能力等方面受到嚴重限制；另一方面節點的可靠性差，在某些領域傳感器節點往往是部署在環境惡劣的地區且無人看管，極其容易被破壞或者自身發生故障。

為了提高節點的可靠性，通常會對所監測區域進行大規模隨機部署。所以，一個傳感器節點收集到的數據（接下來我們稱之為信源節點）如何能夠及時準確的送到匯聚節點，也就是路由方法是移動Ad-Hoc網絡研究中一個非常重要的問題。

現有的Ad-Hoc網絡路由方法有很多，常見的有基于拓撲結構的路由和基于節點位置的路由，其中基于網絡拓撲的路由又分為主動路由和被動路由。在移動Ad-Hoc網絡中，節點是在不斷地移動，其位置信息也在不斷地變化，所以不適合采用基于節點位置的路由協議。在基于網絡拓撲的主動路由方法中，路由信息存儲在路由表中并且每個節點都需要存儲路由表，所以對于任何時間節點都在發生移動的網絡中，將產生大量的路由維護開銷。因此，被動路由在移動Ad-Hoc網絡中有著巨大的優勢。

一個信源節點收集到數據并向匯聚節點傳輸的過程中，一般情況下不可能直接一跳到達，往往需要經過幾跳，為了保證數據能夠完全送達匯聚節點，信源節點至少應該將數據送至兩個節點（我們稱之為目的節點），這樣當一個節點出故障的時候另一個節點可以繼續向匯聚節點傳輸數據。為了實現這樣的操作，可以采用單播路由或者多播路由。其中，多播機制的主要設計目標是實現高效率，盡量減少中繼節點的數量，使總傳輸功率最小化，最大限度地提高網絡的生命周期，還關注其它的包括魯棒性和可擴展性等這類在大規模Ad-Hoc網絡中非常重要的性能。典型的多播機制是基于樹的結構，它假定網絡中的每對節點之間可達性信息可用，并且使用組成員間每對節點之間的可達信息作為虛擬鏈接，以此建立一個能耗高效的樹結構，便于樹結構中的中間節點數據包的發送。

Ad-Hoc按需距離矢量路由（AdhocOn-demandDistanceVectorRouting,AODV）就是一種基于共享樹的多播路由協議，能夠很好的解決上面提到的在傳輸過程中遇到的問題，而且這個機制最初就是在無線自組網中提出的，但是這類算法會為兩個目的節點各自計算出一條路由，如圖1所示。這也意味著算法帶來的能量開銷是單個路由的2倍，如果信源節點傳輸給更多的目的節點，能耗會成倍數的增加。再加上節點在不斷地移動中，在保證數據傳輸可靠性的同時，整個網絡的延時和能耗怎么盡可能的減少，是一個迫切需要解決的問題。

發明內容

本發明的目的在于提供一種基于費馬點的移動Ad-Hoc網絡路由算法，以解決上述背景技術中提出的問題。

為實現上述目的，本發明提供如下技術方案：