基于免疫連通模型與Dijkstra算法的垃圾桶區(qū)域化管理控制系統(tǒng)?

陳 立 鹿順航 曾志輝?

(1.江西工業(yè)工程職業(yè)技術學院信息工程學院，江西 萍鄉(xiāng) 337000；2.河南理工大學電氣工程與自動化學院，河南 焦作 454003)

在日常生活中，垃圾桶的身影無處不在，垃圾桶的廣泛應用在帶來便捷、環(huán)境保護的同時也帶來了很多麻煩，在社區(qū)諸多地方垃圾桶因垃圾裝滿后沒有得到及時處理而造成環(huán)境二次污染，尤其是不可回收垃圾、有害垃圾，雖然目前很多智能垃圾桶的出現(xiàn)解決了這些問題，但由于其信息傳輸慢，功耗大，特別是在復雜的環(huán)境中，會出現(xiàn)信號丟失、軟件錯誤等故障，并不能很好地對垃圾桶實現(xiàn)監(jiān)測和管理。為了解決這一問題，設計一種基于免疫連通模型與Dijkstra 算法的垃圾桶區(qū)域化管理控制系統(tǒng)。

該系統(tǒng)主要由子系統(tǒng)節(jié)點、總站節(jié)點和系統(tǒng)管理后臺組成。子系統(tǒng)利用人體感應模塊檢測垃圾桶周圍是否有人，利用超聲波傳感器測距檢測垃圾桶內部剩余多少空間、利用紅外線傳感器檢測垃圾桶是否裝滿、通過電機驅動模塊實現(xiàn)對壓縮板以及對垃圾蓋的控制。利用LoRa 組網技術，構建了一種垃圾桶區(qū)域化管理控制系統(tǒng)。

汪華斌等[1]采用ZigBee 技術實時監(jiān)控城市的垃圾信息，但沒有設計垃圾桶的防溢出功能，且并沒有考慮傳輸距離的問題，范晨陽等[2]提出了利用NB-lot技術解決傳輸距離問題，并設計了垃圾桶的防溢出功能，但并沒有實現(xiàn)對垃圾車的調度。基于以上考慮，為了解決垃圾桶裝滿后沒有得到及時處理而造成環(huán)境二次污染的問題，提出一種基于免疫連通模型與Dijkstra 算法的垃圾桶區(qū)域化管理控制系統(tǒng)，利用系統(tǒng)管理后臺來監(jiān)視城市垃圾桶垃圾，并設計了垃圾桶的防溢出功能，有效地解決了垃圾桶垃圾溢出問題，并利用LoRa 技術實現(xiàn)垃圾桶的區(qū)域化管理，合理地調度垃圾車，有效地節(jié)約垃圾車資源。

1 系統(tǒng)總體框架設計

垃圾桶區(qū)域化管理控制系統(tǒng)共包括3 部分，即子系統(tǒng)節(jié)點、總站節(jié)點和系統(tǒng)管理后臺。系統(tǒng)框架圖如圖1 所示。

圖1 系統(tǒng)總體框架

LoRa 節(jié)點與垃圾桶連接構成子系統(tǒng)節(jié)點，子系統(tǒng)節(jié)點利用多傳感器技術，采集垃圾桶內部的剩余容量信息，并通過電機驅動模塊實現(xiàn)垃圾桶防溢出、垃圾蓋自動開閉等功能，通過無線LoRa 技術發(fā)送至LoRa 總站；LoRa 總站與微處理器連接構成總站節(jié)點，起監(jiān)視、合理派送垃圾車的作用。垃圾桶的模型圖如下圖所示:

系統(tǒng)管理后臺和總站節(jié)點設置在垃圾站，總站節(jié)點將信息處理后上傳至系統(tǒng)管理后臺，系統(tǒng)管理后臺通過JAVA 技術開發(fā)實現(xiàn)數(shù)據(jù)監(jiān)控、系統(tǒng)報表、數(shù)據(jù)分析和滿溢提醒等功能。系統(tǒng)的具體結構如圖2 所示。

圖2 系統(tǒng)具體結構圖

2 基于免疫連通模型的Dijkstra 算法設計

2.1 信號采集

系統(tǒng)利用多傳感器技術采集信息，其中人體感應模塊檢測垃圾桶周圍是否有人、紅外檢測模塊檢測垃圾桶是否裝滿、超聲波測距模塊用于檢測垃圾桶內部剩余多少空間。信息處理模塊對采集的信息進行處理并發(fā)送至LoRa 子站主控板，LoRa 子站主控板控制根據(jù)信息處理模塊發(fā)送的信息控制電機驅動模塊，并對垃圾桶內部的剩余容量信息進行處理后發(fā)送至總站節(jié)點。

2.2 Dijkstra 算法設計

Dijkstra(迪杰斯特拉)算法常用來尋找?guī)嘤邢驁D中節(jié)點之間的最短路徑。針對本系統(tǒng)，本系統(tǒng)可利用Dijkstra 算法減少垃圾站與垃圾桶之間信息傳遞所消耗的能量。

利用Dijkstra 算法求解最短路徑，簡要步驟如下:

(1)設未確定的最短路徑節(jié)點集合、已確定的最短路徑節(jié)點集合分別為X和Y，并設起始點到其他所有節(jié)點的最短路徑值為T，并利用權圖的鄰接矩陣對T進行過初始化。

(2)若起始點s到點i的最短路徑的長度為T[i]，把i從X放到Y中。

(3)利用節(jié)點i更新數(shù)組T中起始點s到數(shù)組Y中的節(jié)點k對應的路徑值。

(4)重復步驟1、2 直至找到起始點s到所有節(jié)點的最短路徑值。

路徑質量常用來評估傳輸穩(wěn)定性和可靠性，當路徑質量低于闕值時，表示節(jié)點發(fā)生故障。將子系統(tǒng)節(jié)點Ni和總站節(jié)點T之間的路徑質量Q定義為子系統(tǒng)節(jié)點和總站節(jié)點剩余能量與距離的歸一化權重和，定義為:

式中:λ為權重系數(shù)，滿足λ1＋λ2＝1；Ei表示子系統(tǒng)節(jié)點Ni的剩余能量；Esi表示節(jié)點的初始能量；Di表示子系統(tǒng)節(jié)點Ni與總站節(jié)點的路徑長度。

2.3 區(qū)域化免疫連通模型設計

目前，對免疫連通模型運用在無線傳感器網絡的研究有:運用遺傳樣本優(yōu)化和蒙特卡洛評價函數(shù)最大化傳輸效率，基于二進制和概率模型的集中免疫泰森多路徑優(yōu)化傳輸[3]，多目標免疫協(xié)同進化算法[4]，泰森盲區(qū)多邊形傳輸控制[5]，基于免疫連通模型的多路徑傳輸選擇算法[6]。基于以上考慮，區(qū)域化免疫連通模型構建如下:

抗體:垃圾桶與垃圾站之間的連通路徑保證網絡連通性和傳輸可靠性。

抗原:垃圾站監(jiān)控區(qū)域內所有的垃圾桶。

抗體抗原親和力評價函數(shù)f:垃圾桶與垃圾站之間網絡傳輸可靠性的保證能力。單條路徑質量評價函數(shù)定義為式(2)。

式中:pi為第i條傳輸路徑，qi為該路徑鏈的質量，w為路徑鏈的數(shù)量。相應的M條傳輸路徑的質量評價函數(shù)為式(3)。

抗體編碼規(guī)則:垃圾站檢測區(qū)域內的所有的垃圾桶以二進制編碼，二進制編碼位數(shù)為垃圾桶數(shù)量的最小值。

抗原/抗體(基因)變異規(guī)則:二進制數(shù)0 隨機變?yōu)?，二進制數(shù)1 隨機變?yōu)?，抗原變異后的節(jié)點須在上一節(jié)點的射頻覆蓋范圍內，抗體的變異須在垃圾站和垃圾桶之間保持連通性，沒有連通的抗體無效。

變異種群設置:最初隨機建立w個有效抗體，保持垃圾站和垃圾桶之間的連通性。抗體的變異按照自適應遺傳算法[7]中交叉概率Pc與變異概率Pm進行變異生成新的抗體群，Pc和Pm由式(4)和式(5)給出。

式中:fmax為抗體中路徑的最大值，favg為抗體中路徑質量的平均值，fd為變異抗體的評價值，fc為耦合交叉抗體的評價值，k1，k2，k3，k4為常數(shù)。

2.4 基于免疫連通模型的Dijkstra 算法

利用Dijkstra 算法選擇最短路徑傳輸，子系統(tǒng)節(jié)點和總站節(jié)點容易產生多條最短路徑，通過免疫機制來選擇合適的最短路徑，還有效彌補了Dijkstra 算法中剩余節(jié)點能量對通信的影響，以及解決了節(jié)點意外故障對數(shù)據(jù)傳輸?shù)挠绊憽Ｋ惴▓?zhí)行流程圖如圖3 所示。

圖3 基于免疫連通模型的Dijkstra 算法

算法執(zhí)行步驟如下:

首先，算法根據(jù)垃圾桶數(shù)，垃圾桶位置，通信距離和檢測區(qū)域大小，建立能量矩陣，建立初始抗體群，對抗原抗體進行二進制編碼。子系統(tǒng)節(jié)點根據(jù)式(1)判斷節(jié)點的通信質量，選擇從垃圾桶到垃圾站的w條傳輸路徑作為w個抗體。

用式(2)對所有的抗體成員進行評價，挑選出a個抗體作為初始抗體成員群，即C＝{p(1)，p(2)，…，p(a)}。用式(3)對選擇出的路徑進行評價，篩選出滿足條件的路徑，并對這些路徑進行Dijkstra 算法求解，選出新的路徑組成優(yōu)秀抗體群。

判斷優(yōu)秀抗體群的剩余能量是否小于節(jié)點剩余能量最小值，選出滿足條件的抗體節(jié)點，并對選出的抗體節(jié)點進行抗體節(jié)點變異，根據(jù)抗體節(jié)點變異的規(guī)則，對抗體群里的節(jié)點按照式(4)、式(5)進行變異。用式(3)變異后的新抗體進行評價，評價后與原抗體混合比較，選擇全局最優(yōu)的路徑，并循環(huán)執(zhí)行上述步驟直至迭代次數(shù)超過預先設計值。

子系統(tǒng)節(jié)點利用該算法對發(fā)送的信息進行處理后發(fā)送至總站節(jié)點，可有效地解決節(jié)點意外故障對數(shù)據(jù)傳輸?shù)挠绊懀_到信息最優(yōu)化傳輸和減少節(jié)點能耗的目的。

3 垃圾桶防溢出功能設計

垃圾桶經常存在垃圾溢出現(xiàn)象，因此需要給垃圾桶設計防溢出功能，即利用垃圾桶內部的LoRa 子站主控板根據(jù)信息檢測系統(tǒng)檢測到的信息控制電機驅動系統(tǒng)完成壓縮板自動壓縮和垃圾蓋自動關閉。

垃圾桶防溢出設計的流程圖如圖4 所示。

圖4 垃圾桶防溢出流程圖

具體實施過程如下:

步驟1 人體感應傳感器及電機驅動模塊在垃圾桶的頂部，人體感應傳感器檢測到垃圾桶周圍1 m 有人且時間持續(xù)3 s 以上時，電機驅動模塊控制垃圾蓋打開。

步驟2 人體感應模塊檢測到垃圾桶周圍1 m沒人且時間持續(xù)4 s 以上時，電機驅動模塊控制垃圾蓋關閉，反之執(zhí)行步驟1。

步驟3 紅外傳感器位于垃圾桶的入口處，當垃圾蓋關閉后，判斷垃圾桶入口處紅外傳感器是被遮住，被遮住后執(zhí)行步驟5，否之，執(zhí)行步驟1。

步驟4 入口處的紅外傳感器被遮住后，電機驅動模塊控制垃圾桶頂部壓縮板自動下壓后上升。

步驟5 當垃圾桶入口處紅外傳感器再次被遮住時，垃圾蓋保持關閉，否之執(zhí)行步驟1。

步驟6 當垃圾桶內部的垃圾被回收后，系統(tǒng)將被復位。

4 實驗結果與分析

4.1 實驗設置

為了驗證該系統(tǒng)能夠實現(xiàn)信息最優(yōu)化傳輸和減少節(jié)點能耗以及是否能夠合理節(jié)約垃圾車資源，進行相關實驗驗證，對運用該算法的區(qū)域化管理系統(tǒng)與普通的區(qū)域化管理系統(tǒng)進行了實驗對比。

實驗將子系統(tǒng)節(jié)點隨機部署在1 000 m?1 000 m的模擬區(qū)域內，并將節(jié)點初始能量設置成E0＝2 J；網絡延遲值設置為5；節(jié)點密度為200；速度為15 m/s。實驗分別從網絡壽命、傳輸延遲和垃圾車利用率三方面驗證。其中實驗制作的垃圾桶模型圖如圖5(a)、5(b)所示。

圖5 垃圾桶模型圖

系統(tǒng)的實物圖如圖6、圖7 所示。

圖6 子系統(tǒng)節(jié)點實物圖

圖7 總站節(jié)點實物圖

4.2 數(shù)據(jù)收集及分析

(1)網絡壽命

通過計算存活節(jié)點的數(shù)量從而得出網絡的效率，獲得子系統(tǒng)節(jié)點的平均通信輪回次數(shù)，當75%的子系統(tǒng)節(jié)點能量耗完時，網絡可認為完全死亡。

圖8 顯示了本系統(tǒng)和普通的區(qū)域化管理系統(tǒng)的平均輪回次數(shù)的對比，根據(jù)圖8 可知，本系統(tǒng)的平均輪回次數(shù)比普通區(qū)域化管理系統(tǒng)的次數(shù)多，即本系統(tǒng)比普通系統(tǒng)的網絡壽命更長。

圖8 網絡壽命

(2)傳輸延遲

傳輸延遲是指包的接收時間與發(fā)送時間差，包括路由延遲以及數(shù)據(jù)傳輸延遲的平均值。

圖9 顯示了本系統(tǒng)和普通的區(qū)域化管理系統(tǒng)的平均傳輸延遲的對比，根據(jù)圖9 可知，本系統(tǒng)的平均延遲時間比普通區(qū)域化管理系統(tǒng)的時間短。

圖9 傳輸延遲

(3)垃圾車利用率

假設每個子系統(tǒng)節(jié)點即垃圾桶裝滿垃圾需要10 s，設置同樣的垃圾桶數(shù)量，比較普通系統(tǒng)和本系統(tǒng)使用垃圾車的數(shù)量，使用垃圾車的數(shù)量越少，垃圾車的利用率越高，

圖10 顯示了本系統(tǒng)和普通區(qū)域化管理系統(tǒng)的垃圾車利用率對比，根據(jù)圖10 可知垃圾車利用率隨子系統(tǒng)節(jié)點數(shù)的增加而升高，無論子系統(tǒng)節(jié)點少或者多，本系統(tǒng)的傳垃圾車利用率比普通系統(tǒng)高。

圖10 傳輸可靠性

5 結語

所提出的一種基于免疫連通模型與Dijkstra 算法的垃圾桶區(qū)域化管理控制系統(tǒng)，不僅可以解決在社區(qū)諸多地方垃圾桶因垃圾裝滿后沒有得到及時處理的問題，還可以提高信息最優(yōu)化傳輸以及減少節(jié)點的能耗，合理地使用垃圾車資源，實現(xiàn)垃圾站對垃圾桶準確監(jiān)測和管理。