[發(fā)明專利]基于蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由方法

在審

• 申請?zhí)枺?/td>: 201710234320.7
• 申請日: 2017-04-12
• 公開（公告）號: CN107124747A
• 公開（公告）日: 2017-09-01
• 發(fā)明（設(shè)計）人: 鄒霞
• 申請（專利權(quán)）人: 鄒霞
• 主分類號: H04W40/10
• 分類號: H04W40/10;H04W40/24;H04W84/18;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由方法，屬于生物仿真和網(wǎng)絡(luò)通信領(lǐng)域。

背景技術(shù)

仿生優(yōu)化算法是模擬自然界中生物進(jìn)化或者群體行為的隨機(jī)搜索算法的統(tǒng)稱，可以用來解決現(xiàn)實(shí)中的許多優(yōu)化問題，是人工智能研究領(lǐng)域中一個重要的分支。目前比較流行的仿生優(yōu)化算法包括遺傳算法、蟻群算法、微粒群算法、神經(jīng)網(wǎng)絡(luò)算法和人工免疫算法等。蟻群優(yōu)化算法具有并行分布式計算、正反饋、魯棒性等特點(diǎn)，被廣泛地應(yīng)用在許多領(lǐng)域，諸如旅行商問題(Traveling Salesman Problem，TSP)、二次分配問題(Quadratic Assignment Problem，QAP)、工件排序問題、車輛調(diào)度問題、圖著色問題和網(wǎng)絡(luò)通信中的路由問題等。

蟻群優(yōu)化算法是一種群體搜索方法，通常用來解決特定的組合優(yōu)化問題，傳感器網(wǎng)絡(luò)的QoS最優(yōu)路徑問題可以由包含有限個節(jié)點(diǎn)和有限邊的圖來表述。蟻群優(yōu)化算法的目標(biāo)就是遍歷該圖來建立一條最優(yōu)路徑，在螞蟻遍歷圖的過程中，螞蟻利用信息素濃度和啟發(fā)式信息這些局部信息以一定的概率去選擇下一個節(jié)點(diǎn)。螞蟻通過揮發(fā)信息素，修改了路徑上的信息素濃度，使得螞蟻可以間接地交換路徑傾向性信息，從而實(shí)現(xiàn)相互協(xié)調(diào)合作的目的，最終每只螞蟻分別建立一個近似最優(yōu)解。蟻群算法的主要優(yōu)點(diǎn)有正反饋、分布式并行處理、魯棒性好、易與其他啟發(fā)式算法結(jié)合，主要缺點(diǎn)是搜索時間長、容易陷入局部最優(yōu)解。

發(fā)明內(nèi)容

鑒于上述現(xiàn)有技術(shù)的不足之處，本發(fā)明的目的在于提供一種基于蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由方法，包括以下步驟：

步驟一、初始化參數(shù)，生成所需網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

步驟二、設(shè)置當(dāng)前迭代次數(shù)l=l+1，設(shè)置每條鏈路信息素增量，將M只螞蟻置于源節(jié)點(diǎn)s，生成禁忌表，并將源節(jié)點(diǎn)放入禁忌表中；

步驟三、如果螞蟻m沒有完成搜索，由當(dāng)前節(jié)點(diǎn)v_i選擇下一跳節(jié)點(diǎn)v_j，同時判斷從源節(jié)點(diǎn)s到v_j所經(jīng)過的路徑是否符合所有約束條件，同時更新節(jié)點(diǎn)的剩余能量值；如果節(jié)點(diǎn)v_j不存在，則螞蟻死亡，停止搜索；如果節(jié)點(diǎn)v_j恰好為目的節(jié)點(diǎn)t，則完成搜索；否則將v_j放入螞蟻m的禁忌表中，繼續(xù)搜索；

步驟四、重復(fù)執(zhí)行步驟三，直到所有放置在源節(jié)點(diǎn)的M只螞蟻全部完成搜索為止，記錄從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)t的所有合格路徑；

步驟五、更新所有鏈路的信息素；

步驟六、如果l<L，則轉(zhuǎn)到步驟六，否則執(zhí)行步驟七；

步驟七、輸出結(jié)果，結(jié)束。

優(yōu)選的，上述步驟一具體為設(shè)網(wǎng)絡(luò)中共有N個節(jié)點(diǎn)，設(shè)置每條鏈路的度量值和每個節(jié)點(diǎn)的剩余能量值，確定約束條件的值。

優(yōu)選的，上述步驟一還包括刪除不滿足條件的鏈路，生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。設(shè)螞蟻數(shù)量為M，從源節(jié)點(diǎn)處開始搜索，最大迭代次數(shù)為L，源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)為t。信息素濃度鄰接矩陣初始化為，確定權(quán)重值，確定信息素強(qiáng)度系數(shù)Q。

相比現(xiàn)有技術(shù)，本發(fā)明提供的基于蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由方法，將蟻群算法應(yīng)用于ZigBee路由，具有以下優(yōu)點(diǎn)：

1、ZigBee傳感器節(jié)點(diǎn)能力有限。ZigBee節(jié)點(diǎn)體積小，存儲能力、處理能力和能量都很有限，所以就要求路由算法要盡量簡單，來減少節(jié)點(diǎn)的能耗。蟻群算法中每個個體只是進(jìn)行簡單的功能實(shí)現(xiàn)，因此可以節(jié)省網(wǎng)絡(luò)資源，延長網(wǎng)絡(luò)壽命。

2、蟻群算法具有較高的魯棒性。其自組織、自適應(yīng)和動態(tài)尋優(yōu)的特征使得該算法能對網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化有很好的適應(yīng)性。不會因?yàn)榫W(wǎng)絡(luò)中的某個節(jié)點(diǎn)移動、失效或者有新節(jié)點(diǎn)的加入，影響到整個網(wǎng)絡(luò)的尋路過程。

3、蟻群算法收斂快。蟻群算法的正反饋機(jī)制，使較優(yōu)路徑上積累更多的信息素，這樣就可以迅速區(qū)分解的優(yōu)劣，極大地加快了收斂速度，同時保障了ZigBee網(wǎng)絡(luò)的實(shí)時性。

附圖說明

圖1為網(wǎng)絡(luò)模型示意圖；

圖2為本發(fā)明基于蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由方法流程示意圖。