[發明專利]一種基于元胞自動機的GAF路由方法

有效

• 申請號: 201410166158.6
• 申請日: 2014-04-24
• 公開（公告）號: CN103957573B
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 于秦;姜微;安寧;冷甦鵬;毛玉明
• 申請（專利權）人: 電子科技大學
• 主分類號: H04W40/10
• 分類號: H04W40/10;H04W40/32;H04W84/18
• 代理公司: 成都宏順專利代理事務所(普通合伙)51227
• 代理人: 周永宏

技術領域

本發明屬于無線通信技術領域，具體涉及一種GAF路由方法。

背景技術

GAF(geographical adaptive fidelity)算法是ad hoc網絡中的一種路由算法，它以節點的地理位置作為分簇的依據，之后GAF算法被引入到無線傳感器網絡中，加入了節點睡眠機制，成為一種經典的分簇節能路由算法。該算法把被監測區域劃分為虛擬單元格，每個傳感器節點均勻撒落在相應劃入的虛擬格子內，并以地理位置信息作為劃分依據。一個周期內，每個虛擬格子內通過簇頭選舉過程產生一個簇頭節點。在傳感器網絡工作工程中，只有簇頭節點保持工作狀態，其他同一虛擬格子內的節點均進入睡眠狀態，節約能量消耗。

GAF算法作為一種較新的路由算法，自身存在許多有待改進的不完善之處，主要問題在于：(1)GAF算法中每個虛擬格內的節點需要跟相鄰虛擬格內的任意節點保證通信，而四邊形的虛擬單元格結構限制了節點和對角邊上的節點之間的通信，這樣會增加路由跳數而增大能量消耗。近年來以蜂窩形即正六邊形的虛擬格形狀對無線傳感器網絡進行區域劃分的方法被提出，提高了能量的使用效率，增長了網絡生存時間。(2)GAF算法是一種分簇節能路由算法，但在進行簇頭選舉時沒有考慮節點的剩余能量，而是隨機地選擇簇頭，對節點的負載均衡方面的問題沒有優化措施，這樣可能會導致簇頭負擔更多的通信和數據處理任務，消耗更多的能量，最終提前死亡。因此，應當使擁有更多剩余能量的節點擔任簇頭。研究人員提出了GAF簇頭選舉改進算法，提出兩種簇頭選擇方法：完全型簇頭選擇算法與隨機型簇頭選擇算法，改進的簇頭選舉算法增長了網絡生存時間，避免網絡分隔。(3)GAF算法中規定節點均勻分布在規則的虛擬格子中，限制了節點的分布，而實際的應用場景當中，節點往往是隨機分布或分布很不規則，可能會出現某些虛擬格子中沒有節點分布而某些虛擬格子中出現過多節點的情況。

發明內容

針對現有技術存在的上述問題，本發明提出了一種基于元胞自動機的GAF路由方法。

本發明的技術方案是：一種基于元胞自動機的GAF路由方法，包括如下步驟：

S1：對無線傳感器網絡進行虛擬單元格劃分，網絡中的節點都維護自身的地理位置信息；

S2：建立元胞自動機模型，包括元胞空間、元胞鄰居模型、元胞的狀態集和元胞自動機狀態轉換規則的確定；

S3：執行基于元胞自動機的簇頭選舉方法，選舉出簇頭節點；

S4：當節點若收到鄰居節點已經成為簇頭的信息，則直接進入睡眠狀態；同樣通過元胞自動機狀態轉換規則競爭簇頭不成功的節點也進入睡眠狀態；

S5：當選為簇頭的節點設置定時器T_a，代表節點處在活動狀態的時間，當T_a超時，所述節點重新加入簇頭競爭中，回到發現狀態；簇頭競選失敗的節點進入睡眠狀態，設置定時器T_s，定時器超時后由睡眠狀態回到發現狀態的節點再次與虛擬單元格內其他節點交換信息，以確定自己是否能夠成為簇頭。

進一步的，步驟S1所述的網絡中的節點自身的地理位置信息表示方法如下：

設節點P的位置坐標為(x,y)，則沿x軸方向節點所在虛擬單元格的編號x_loc由公式x_loc＝(int)x/grid_size計算得出，其中，grid_size為正方形虛擬單元格的邊長；沿y軸方向節點所在虛擬單元格的編號y_loc由公式y_loc＝(int)y/grid_size計算得出；節點在網絡中所在虛擬單元格編號grid_ID由公式grid_ID＝(y_loc*grid_X+x_loc)計算得出，其中，grid_X表示網絡中沿x軸方向虛擬單元格的數量。

進一步的，步驟S2所述的建立元胞自動機模型的具體過程如下：

網絡中每個虛擬單元格即為一個元胞空間，在以一個虛擬單元格為單元的元胞空間內，通過不規則元胞自動機鄰居元胞的劃分方法確定鄰居節點：

節點有睡眠狀態、發現狀態和活動狀態三個狀態，用00表示睡眠狀態，01表示發現狀態，11表示活動狀態；

設t時刻元胞(i,j)的狀態為Q_i,j^(t)，其鄰居節點狀態之和定義為N_i,j^(t)＝∑Q_i,j^(t)，其中某節點的鄰居節點是指在該節點單跳通信范圍內的節點；