[發明專利]一種基于改進和聲搜索算法的無線傳感器網絡路由方法

有效

• 申請號: 201410097200.3
• 申請日: 2014-03-17
• 公開（公告）號: CN103916927B
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 董燕;曾冰
• 申請（專利權）人: 華中科技大學
• 主分類號: H04W40/04
• 分類號: H04W40/04;G06F17/10
• 代理公司: 華中科技大學專利中心42201
• 代理人: 梁鵬

技術領域

本發明屬于無線傳感器網絡技術領域，具體涉及一種改進和聲搜索算法的路由方法。

背景技術

無線傳感器網絡（Wireless Sensor Network，WSN）與傳統的因特網以及最近幾年發展迅猛的無線自組網（MobileAd Hoc Network）都有著很大程度上的不同。在傳統的因特網和Ad Hoc網絡中，每個網絡節點通常情況下是一臺個人電腦或者移動設備，用戶使用因特網和Ad Hoc網主要是用來獲取網絡共享信息，所以不管是因特網還是AdHoc網絡，路由協議設計的目的主要是為了提高服務質量，而不必考慮用戶消耗多少能量。無線傳感網絡則不同，無線傳感網絡是在檢測區域（通常情況下環境十分惡劣或者人無法到達）內散播大量的微型傳感器節點，這些傳感節點并沒有固定的ID，而是通過自組織的方式組成一個傳感器網絡。無線傳感器網絡一經問世，便獲得了社會各界的青睞，應用在軍事，醫療，環境等各個領域。

路由算法在無線傳感器網絡中發揮著重要作用，它對各節點的能耗、整個網絡的生命周期以及通信質量起著關鍵性的作用。因此，路由算法的研究受到越來越多的關注。由于傳感器網絡具有能量受限、資源受限、拓撲結構變化頻繁等特點，因此，傳統的路由機制不能適應無線傳感網絡，必須設計與之相應的路由算法。

至今，用于無線傳感器網絡的路由協議主要包括：平面路由協議（Flooding協議、SPIN協議、MTE協議、Directed Diffusion協議）、層次路由協議（LEACH協議）、基于位置信息的路由協議（GAF協議、GEAR協議）以及基于數據流和QoS的路由協議。

目前，基于智能優化算法的路由方法在無線傳感器網絡技術領域也有了一些應用，主要是基于蟻群算法（Ant Colony Optimization,ACO）的路由方法和基于蜂群算法（Bee Colony Optimization,BCO）的路由方法。

無線傳感網絡路由協議的研究已經逐漸成為熱點，路由協議的研究從簡單到復雜，從以數據為中心到高質量要求，并向著智能化方向發展，如何建立高效、自適應的傳感路由算法成為當前研究的一個熱點。

和聲搜索算法是2001年韓國學者Geem等人提出的一種新穎的智能優化算法。算法模擬了音樂演奏中樂師們憑借自己的記憶，通過反復調整樂隊中各樂器的音調，最終達到一個美妙的和聲狀態的過程。和聲搜索算法有很強的全局搜索能力，易于收斂到全局最優解，其流程圖如圖1所示，執行步驟如下所示：

Step1：初始化算法相關參數。

初始化HMS（和聲記憶庫的大小，即種群容量大小）、HMCR（選擇概率）、PAR（調整概率）、BW（調整帶寬）、評價次數eval_No_max。

Step2：和聲記憶庫（Harmony Memory,HM）初始化。

在此步驟中，式（1）所示的HM通過在內產生一組隨機數來初始化，其中1≤i≤n。從而根據式（2）得到第j個解向量的第i個變量值：

上式中，j＝1,2,…,HMS，Random(0,1)是0到1之間的隨機數。

Step3：計算和聲庫中各和聲的適應度。

Step4：設置eval_No＝0。

Step5：即興演奏候選和聲。

Step5.1：在此步驟中，一個新的和聲向量由三個規則產生：

①記憶選擇；

②隨機選擇；

③音高調整。

產生一個候選和聲被稱之為即興演奏，先通過規則①和②確定是記憶選擇還是隨機選擇，具體如下所示：

式中，P₁為0到1之間的隨機數，x_rand(i),j表示在HM的第j列分量中隨機選擇一個分量，Ω_j表示第j個分量的定義域。

Step5.2：每個經過記憶選擇得到的音調將被進一步檢驗決定是否需要音高調整，此操作使用PAR參數，音高調整決策如下所示：

式中，P₂為0到1之間的隨機數。

Step5.3：計算候選和聲的適應度值f(π)；

Step5.4：更新HM。

依據目標函數值，如果候選和聲向量優于HM中最差的向量，則新向量取代HM中最差的和聲向量，否則不操作。

Step6：檢查是否停止迭代。