[發明專利]一種基于費馬點的移動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
• 代理人: 李靜

1.一種基于費馬點的移動Ad-Hoc網絡路由算法，其特征在于，包括如下步驟：（1）通過信源節點和兩個目的節點組成的三角形的位置信息，計算得到對應的費馬點，即到上述三個頂點的距離之和最小的點，把費馬點或者相鄰位置的傳感器節點作為中繼節點；當信源節點向目的節點傳輸數據時，先把數據沿一條路徑傳輸給中繼節點，然后再由中繼節點將數據分別發送給目的節點；（2）在中繼節點接收并轉發的過程中，當作為中繼的節點移動離開費馬圓時，停止接收數據，并從路由表內重新選擇一個節點作為中繼節點繼續接收并轉發數據；(2a)當計算移動到新位置的中繼節點和費馬點之間的距離大于費馬圓半徑r時，說明此時中繼節點已經不在費馬圓內，取消該節點的中繼標記，停止接收信源節點發送的數據；(2b)從之前建立的路由表內重新檢索，找到離費馬點最近距離的節點作為中繼節點；信源節點向新的中繼節點繼續發送數據，新的中繼節點接收到數據后向兩個目的節點轉發數據，直至目的節點完全接收數據；（3）當信源節點在不斷地移動時，重新計算費馬點的位置，建立新的費馬圓，確定新的中繼節點，繼續接收并轉發數據；（4）目的節點完成數據的接收。

2.根據權利要求1所述的基于費馬點的移動Ad-Hoc網絡路由算法，其特征在于，所述步驟(1)中基于費馬點選擇中繼節點，按照以下步驟進行：(1a)當信源節點和兩個目的節點組成的三角形有一個內角大于120度時，費馬點就是這個鈍角所對應的頂點，也就是這個頂點作為中繼節點，當信源節點是該頂點時，信源節點直接向兩個目的節點發送數據；當一個目的節點就是中繼節點時，信源節點的數據應該先發送給該目的節點，然后由該目的節點再將數據發送給另一個目的節點；(1b)當信源節點和兩個目的節點組成的三角形的所有內角都小于120度時，費馬點就在三角形內，因為無法保證費馬點的位置上剛好有傳感器節點，所以信源節點根據費馬點的位置，建立一個以費馬點位置為圓心，r為半徑的一個圓，我們稱之為費馬圓；(1c)收集費馬圓內的所有節點位置，建立一個路由表，當信源節點向中繼節點發送數據時，選擇路由表內距離費馬點位置最近距離的節點作為中繼節點接收并轉發數據給兩個目的節點。

3.根據權利要求1所述的基于費馬點的移動Ad-Hoc網絡路由算法，其特征在于，所述步驟(1)中節點之間建立路由，按照以下步驟進行：(1d)以費馬點為圓心，r為半徑，搜索所有在范圍內的傳感器節點，把所有搜索到的傳感器節點統一建立在一個路由表中，選擇離費馬點位置最近的一個傳感器節點作為中繼節點，并標記為1，其余節點標記為0；(1e)信源節點先向費馬圓區域發送一個路由請求報文，費馬圓內的傳感器節點接收到信源節點發送的報文，只有轉發標識為1的節點才能繼續轉發報文，其余的節點轉發標識為0，接收到報文以后不做任何處理，中繼節點收到報文后，將數據信息進行重新封裝成2個含有不同目的節點地址的數據報文，然后向兩個目的節點分別進行轉發。

4.根據權利要求1所述的基于費馬點的移動Ad-Hoc網絡路由算法，其特征在于，所述步驟(3)中信源節點移動時的分析方法，按照以下步驟進行：(3a)當信源節點在移動時，它和兩個目的節點就會形成一個新的三角形，根據實際場景內節點需要移動的速率規定一個時間間隔，每隔一段時間計算一次信源節點所在的位置，當新三角形有一個內角大于120度時，重復步驟(1a)；當新三角形內角都不大于120度時，計算此時形成三角形的費馬點的位置，然后計算新的費馬點和中繼節點之間的距離，如果距離小于費馬圓半徑r，說明中繼節點一直屬于最優中繼，不需要做任何改變；如果距離大于等于費馬圓半徑r，說明此時中繼節點已經不屬于最優中繼了，將此節點的標識置為0，并從路由表內刪除該節點的信息；(3b)以新的費馬點為圓心，r為半徑，建立新的費馬圓，按照(1d)步驟重新選擇出最優傳感器節點作為中繼節點，并將標識置為1，向信源節點發送更改中繼節點地址的請求，信源節點根據請求更改路由請求報文。