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

有效

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

1.一種基于元胞自動機的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)，其中某節點的鄰居節點是指在該節點單跳通信范圍內的節點；

狀態轉換規則函數f，即定義如下：

如果則其中，變量energy代表本節點剩余能量，avr_energy代表本節點及所有鄰居節點的平均剩余能量；

當節點當前狀態為01，即為發現狀態時，節點通過與同一虛擬單元格內鄰居節點交換信息判定自身的剩余能量與平均剩余能量之間的關系；當節點剩余能量大于或等于平均剩余能量時，下一時刻節點狀態變為11，即進入活動狀態，成為簇頭；當節點剩余能量小于平均剩余能量時，下一時刻節點狀態變為00，即進入睡眠狀態；

當節點進入活動狀態時證明競爭簇頭成功，成為虛擬單元格的簇頭，擔任通信任務，設置cluster＝1，所述cluster表示節點當選簇頭，設置定時器T_c，記錄節點擔任簇頭的時長，計時器超時后節點回到狀態01，即發現狀態，進入下一輪簇頭的競爭中；進入睡眠狀態的節點開啟計時器T_s，記錄節點睡眠的時長，并將睡眠/工作狀態標志sleepflag置為0；

如果則節點當前狀態為00，若sleepflag為1，則該節點在下一時刻的狀態轉換為發現狀態“01”，否則節點仍保持為睡眠狀態；

如果則節點當前狀態為11，即節點處于活動狀態，擔任簇頭，若cluster為1，則保持活動狀態，否則cluster＝0，節點處于活動時間超時，回到發現狀態。

2.根據權利要求1所述的基于元胞自動機的GAF路由方法，其特征在于，avr_energy定義為：其中，N為鄰居節點數量，E表示本節點的剩余能量，E_n表示本節點的鄰居節點的剩余能量。

3.根據權利要求1所述的基于元胞自動機的GAF路由方法，其特征在于，S3所述的選舉出簇頭節點的具體過程如下：

初始狀態時，所有節點均處于發現狀態，每個節點向鄰居元胞節點發送消息通告自己的剩余能量信息，是否為簇頭節點，即發送消息M＝(E_p,cluster)，E_p為節點剩余能量，cluster標志位表示節點是否為簇頭節點；節點根據收到的鄰居的信息，按照狀態規則函數f決定是否能夠成為簇頭。