[發明專利]基于動態聚類的多目標規劃無線傳感網路由算法

無效

• 申請號: 200710070645.2
• 申請日: 2007-08-30
• 公開（公告）號: CN101119303A
• 公開（公告）日: 2008-02-06
• 發明（設計）人: 孟利民;周凱;徐志江
• 申請（專利權）人: 浙江工業大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/28
• 代理公司: 杭州天正專利事務所有限公司
• 代理人: 王兵;王利強

技術領域

本發明涉及無線傳感網絡路由算法，尤其是一種能夠提供自適應分簇，并能在簇內提供Qos保障的無線傳感網絡路由算法。

背景技術

無線傳感器網絡是一種全新的信息獲取和信息處理、傳輸技術，通常包含大量的可自組織成多跳無線網絡的節點。無線傳感網絡具有組網快捷、靈活，且不受有線網絡約束的優點，可用于緊急搜索、災難救助、軍事、醫療等環境中，具有廣泛的應用前景。無線傳感器網絡已經引起了學術界和工業界的高度重視，被稱為是21世紀最有發展前景的技術之一。

路由協議是無線傳感器網絡層的核心技術。在無線傳感器網絡中，節點能量有限，因此路由協議需要高效利用能量，同時傳感器網絡節點數目往往很大，節點只能獲取局部拓撲結構信息，路由協議要能在網絡信息的基礎上選擇選擇合適的路徑。傳感器網絡具有很強的應用相關性，不同應用中的路由協議可能差別很大，沒有一個通用的路由協議。在無線傳感器網絡中提供服務質量(Quality?ofService，Qos)保障意味著需要提供質量可以接受的信道、支持Qos的信道接入協議、識別能夠滿足業務量要求的轉發節點以及在節點實施擁塞控制和管理。由于對無線傳感器網絡可以提供的業務模型缺乏清楚的描述與定義，如何在無線傳感器網絡中提供Qos保障成為一個復雜而全新的課題。

目前，國內外對無線傳感器網絡路由算法進行了深入的研究，但每種算法都只考慮了網絡性能的某一方面，所以需要一種綜合考慮各個因素的路由算法。在當前的研究工作中，針對簇劃分的方法主要有以下3種：粒子群優化算法(ParticleSwarm?Optimization，PSO)、基站擴散方法、節點生成方法。PSO方法中，考慮在未知拓撲的異構網絡中，完全按照節點數目來劃分簇，按照盡量平衡的原則劃分，生成一棵二叉樹，然而這種劃分問題是NP-hard，因此實用性不大，必須改進算法以減少計算復雜度；在基站擴散方法中，作者考慮了能量因素，由Base?Station(BS)發送不同功率的波段進行擴散，從而得到簇劃分，然后進行簇內的簇首選取，最后將選取結果通知BS并注冊。但是由于拓撲結構的不確定性，所得劃分必然很不均勻，而想要提高精度，必須進行細化，這樣就導致復雜度大幅度提高，同時所得的組均處于一個細環中，使得內部路由消耗很大。節點生成的方法是在已知拓撲結構的異構節點網絡中，通過確定簇首與成員節點數目進行擴散，從而形成整個簇。但是其計算復雜度也是相當高的，唯一的優點就是當簇選定之后，相應的內部路由機制也就確定了。

除了以上所述的分簇路由，在平面路由上主要采用的是DSR、AODV、TORA三種。TORA(Temporally-Ordered?Routing?Algorithm)的主要優點是可以支持多路徑路由和多播，因此TORA通常作為底層協議，為不能適應無線環境的多播算法提供服務，但是依賴性強，不支持單向鏈路，網絡開銷較大；DSR(Dynamic?SourceRouting)使用于以中速移動的動態無線網絡中，較低的路由開銷使得它更適合帶寬和能量受限的網絡中。然而，由于DSR數據分組包含整條路由信息，使得數據包顯得更大，不利于無線傳輸。AODV(Ad?hoc?On?Demand?Distance?Vector)是從DSDV(Destination-Sequenced?Distance-Vector)和TORA上發展而來的，它克服了DSDV等算法的缺點，具有良好的性能，但它不支持單向信道并且只為每個源和目的節點維持一條路由。以上三種路有協議都不能很好地支持Qos服務。

發明內容

為了克服現有的無線傳感網路由算法的復雜度高、運算速度慢、能量損耗大、不能有效支持網絡的Qos服務的不足，本發明提供一種減小復雜度、運算速度快、能量損耗較小、能有效滿足用于對網絡的Qos服務要求的基于動態聚類的多目標規劃無線傳感網路由算法。

本發明解決其技術問題所采用的技術方案是：

一種基于動態聚類的多目標規劃無線傳感網路由算法，主要包括以下步驟：

1)、輸入傳感器網絡的基本信息：網絡的節點數目、節點坐標位置和區域邊長，調用一階能耗模型，計算整個網絡傳輸一次數據消耗的能量，其算式為(1)：