[發明專利]一種GEM路由選擇的改進方法

無效

• 申請號: 201110104047.9
• 申請日: 2011-04-26
• 公開（公告）號: CN102131268A
• 公開（公告）日: 2011-07-20
• 發明（設計）人: 趙國安;張波
• 申請（專利權）人: 上海左岸芯慧電子科技有限公司
• 主分類號: H04W40/02
• 分類號: H04W40/02
• 代理公司: 蘇州市新蘇專利事務所有限公司 32221
• 代理人: 楊曉東

技術領域：

本發明涉及無線路由選擇的方法，尤其涉及一種GEM無線路由選擇的改進方法。

背景技術：

GEM路由是一種適用于數據中心存儲方式的地理路由。GEM路由的基本思想：建立虛擬坐標系統，用來表示實際的網絡拓撲結構，網絡中的節點形成了一個以匯聚節點為根的帶環樹，每個節點用到樹根的跳數距離和角度來表示，節點之間的數據路由通過這個帶環樹實現。無線傳感器網絡最為重要的一個特征就是能量受限，網絡內每個節點通常只攜帶有限、無法更換的電源，同時節點的計算、通信、存儲能力也相當有限。在無線傳感器網絡中，由于網絡內節點資源有限，數據包的傳送需要通過多跳通信方式到達目的地，因此路由選擇算法是網絡層設計的一個主要任務。由于能量有限，以及環境干擾和其他不利因素，傳感器節點會經常受到損壞，加上無線發射裝置發送功率的變化和信號間的干擾，網絡拓撲結構會頻繁變化。

GEM路由選擇方法中，虛擬極坐標系統的建立過程主要主要包括三個步驟：第一，生成樹型結構。匯聚節點設置自己的跳數距離為0，并廣播路由建立消息，該消息包含一個到匯聚節點跳數的域。第二，反饋子樹大小。子樹大小是指子樹中包含的節點數目。第三，確定虛擬角度范圍。匯聚節點首先決定整個虛擬極坐標系統的角度范圍，此角度只是一個邏輯角度，并不表示節點的實際方位。經過上述三個步驟，每個節點都知道自己到匯聚節點的跳數和自己的邏輯角度范圍，這樣就可用跳數，角度范圍唯一表示每個節點。節點在發送消息時，如果目的位置的角度不在自己的角度范圍內，就將消息傳送到父節點，父節點按照同樣的規則處理，直到該消息到達角度范圍包含目的

上述算法需要上層節點轉發消息，開銷比較大。一個改進算法是：節點在向上傳送消息之前首先檢查監控節點是否包含目標位置的角度。如果包含，則直接傳送給該鄰居節點而不再向上傳送。進一步的改進算法是利用環形結構，如果節點檢查到相鄰節點離目標位置更近，就將消息傳送給此鄰居節點，否則才響上層傳送。

但是，目前的改進方法也都存在一定的局限性，沒有充分發揮節點地理位置信息的作用，使傳感器網絡對位置的敏感性得不到充分體現。

發明內容：

本發明要解決的技術問題是提供一種能量開銷比較小，網絡拓撲結構發生變化時，調整過程比較簡單的路由選擇方法。

為解決上述技術問題，本發明提供了如下技術方案：一種GEM路由選擇的改進方法，其將GEM路由選擇方法中的虛擬極坐標轉換為實際極坐標，包括以下步驟：

A.繪制網絡連通圖，節點數據結構為一嵌套結構，第一個8位Id為節點標識碼，緊跟其后的整數Number為該節點兒子個數，以此類推，第二個Id為第一個兒子節點的標識碼，其后的Number為它的兒子節點數目，

匯聚節點對各節點的數據進行處理，將節點間的連接關系以鄰接表的形式表示；

B.進行去環處理，在步驟A生成的鄰接表上通過圖的廣度優先遍歷算法進行去環處理。

作為本發明所述的GEM路由選擇的改進方法的一種優選方案，其中：還包括路由沖突控制步驟，沖突控制基站將網絡中的節點按層級連接關系劃分為不同的區域，相鄰區域確保不在同一時間片內，在此時間片內再為不同的節點劃分不同的時槽，基站分發時槽信息時，將子節點的時槽段信息發給其父節點，父節點在此時間段內保持在偵聽，接收狀態。

作為本發明所述的GEM路由選擇的改進方法的一種優選方案，其還包括路由維護步驟：

C.失效節點為路由節點時，向基站發出撤銷其路由節點功能的報告，同時向自己所有兒子節點發送一個撤銷鏈接的信號，然后作為一般的葉子節點，基站在收到節點要求撤銷路由功能的報告后，根據網絡圖，為申請節點的子樹尋找父節點；

D.失效節點為葉子節點時，主動向其父節點報告自己即將脫離鏈接；或者是父節點在一段時間內不能收到某個子節點的信息，則判斷其被損壞，并逐級報告到基站；

E.當有新節點加入時，新加入節點發送定位請求，周邊節點收到此請求后，向其回送自己的物理坐標和各自路由信息，在收到其他節點的坐標信息后，新節點啟動基于不測距的定位流程計算出自己的物理位置，然后選擇一個距基站最近節點作為父節點加入其子樹。

本發明與現有技術相比，具有以下優點：該路由選擇方法具有較小的能量開銷，網絡拓撲結構發生變化時調整過程比較簡單。

附圖說明：

下面結合附圖對本發明做進一步說明。

圖1：拓撲結構示意圖。

圖2：鄰接表圖。

圖3：鄰接表去環流程。

圖4：無環路鄰接表。

圖5：一級路由示意圖。

圖6：二級路由示意圖。