基于Vicsek模型的DSDAC算法在電子?xùn)艡诟采w問題應(yīng)用研究

王振滔 樓浩棟 鄭溫昊 王雨澤 索文騰 程宇軒

摘要：在傳感器電子?xùn)艡诟采w大體分為區(qū)域覆蓋、點(diǎn)覆蓋、柵欄覆蓋三類，需要解決傳感器部署和傳感器調(diào)度等問題。為了提高電子?xùn)艡诘谋O(jiān)控質(zhì)量，采用多層?xùn)艡趤碓黾优R界點(diǎn)被檢測到的幾率。本文研究基于Vicsek 模型基礎(chǔ)上，采用DSDAC算法覆蓋算法，在保證測試網(wǎng)絡(luò)連通的情況下進(jìn)行仿真研究。本文將對(duì) Vicsek 模型作相關(guān)介紹和分析，然后對(duì)現(xiàn)有基于 Vicsek 模型的DSDAC覆蓋算法進(jìn)行理論分析和實(shí)驗(yàn)仿真，并得出仿真結(jié)果。

關(guān)鍵詞：電子?xùn)艡?DSDAC算法;Vicsek 模型

1 引言

無線傳感器電子?xùn)艡诟采w主要目的是起到優(yōu)化和部署傳感器網(wǎng)絡(luò)資源，通過保證網(wǎng)絡(luò)連通的情況下進(jìn)行監(jiān)控目標(biāo)區(qū)域。其中，無線傳感器電子?xùn)艡诘木W(wǎng)絡(luò)部署的主要任務(wù)就是利用最少的傳感器網(wǎng)絡(luò)資源實(shí)現(xiàn)最大化最優(yōu)的覆蓋效果。在實(shí)際應(yīng)用工程中，研發(fā)機(jī)構(gòu)為了節(jié)約成本，大多采用低價(jià)位低性能的基本完成需求的傳感器硬件，這類傳感器無論在計(jì)算性能、通信性能、感應(yīng)性能、能量提供等諸多性能受到限制。因此大大增加集中控制模式實(shí)現(xiàn)網(wǎng)絡(luò)覆蓋局限性和困難性，尤其針對(duì)拓展和增容傳感器網(wǎng)絡(luò)，由于瓶頸所限難以實(shí)施。

傳感器電子?xùn)艡诓捎玫姆植际剿惴?，傳感器網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)需要實(shí)時(shí)互換采集的信息，系統(tǒng)啟用后要保障傳感網(wǎng)絡(luò)實(shí)時(shí)連通。本文研究Vicsek模型是多智能監(jiān)控系統(tǒng)中比較經(jīng)典的一致性模型，模型系統(tǒng)中每個(gè)監(jiān)測個(gè)體節(jié)點(diǎn)，能夠智能的根據(jù)系統(tǒng)領(lǐng)域中個(gè)體節(jié)點(diǎn)的信息自適應(yīng)的更新本身的實(shí)時(shí)信息，通過系統(tǒng)各個(gè)節(jié)點(diǎn)的自適應(yīng)信息更新最終使整個(gè)系統(tǒng)達(dá)到信息一致化。由于Vicsek模型的分布式特點(diǎn)，可以應(yīng)用解決無線傳感器網(wǎng)絡(luò)電子?xùn)艡诘母采w問題。

2 Vicsek模型

Vicsek模型是由 Vicsek 等人于1995的文獻(xiàn)[1]中提出了一種由 N 個(gè)有自治性能的網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)組成的離散型系統(tǒng)，系統(tǒng)中，所有的網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)都采用相同的速率運(yùn)動(dòng)，同時(shí)網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)的初始時(shí)刻具有任意的運(yùn)動(dòng)方向，它是一種自運(yùn)動(dòng)收斂模型。隨著系統(tǒng)的運(yùn)行進(jìn)程，系統(tǒng)中的每個(gè)網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)的運(yùn)動(dòng)，會(huì)根據(jù)其鄰近的網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)的運(yùn)動(dòng)矢量的平均值進(jìn)行不斷的自適應(yīng)更新數(shù)據(jù)，最終達(dá)到系統(tǒng)中的所有網(wǎng)絡(luò)個(gè)體節(jié)點(diǎn)都具有一致的運(yùn)動(dòng)方向，即系統(tǒng)實(shí)現(xiàn)運(yùn)動(dòng)一致化。

Vicsek模型系統(tǒng)數(shù)學(xué)計(jì)算簡易，比較適合用于中小型傳感器網(wǎng)絡(luò)系統(tǒng)的組網(wǎng)監(jiān)聽。Vicsek 模型工作原理：網(wǎng)絡(luò)系統(tǒng)中某個(gè)個(gè)體節(jié)點(diǎn)i的鄰居集合，是把該個(gè)體的當(dāng)前位置做為集合的幾何中心，半徑為常數(shù)r 的圓內(nèi)的所有個(gè)體節(jié)點(diǎn)組成。網(wǎng)絡(luò)中個(gè)體節(jié)點(diǎn)i的平均運(yùn)動(dòng)方向和運(yùn)動(dòng)位置，都可以通過Vicsek原始模型如公式1和公式2求得。

Vicsek模型通過系統(tǒng)運(yùn)行后，保證多個(gè)個(gè)體節(jié)點(diǎn)的矢量運(yùn)動(dòng)的方向一致性，系統(tǒng)最終的收斂方向是不固定的，個(gè)體節(jié)點(diǎn)i的所有鄰近節(jié)點(diǎn)的平均運(yùn)動(dòng)方向如公式3所示。

3.Vicsek 模型電子?xùn)艡诘膽?yīng)用

無線傳感網(wǎng)絡(luò)中個(gè)體節(jié)點(diǎn)部署受到位置環(huán)境限制情況下更適合采用分布式算法，Vicsek 模型是一種多智能系統(tǒng)控制模型。本系統(tǒng)采用的是Teddy M. Cheng 和 Andrey V.Savkin[2]提出的DSDAC算法，將其應(yīng)用于Vicsek模型下進(jìn)行無線傳感網(wǎng)絡(luò)。系統(tǒng)測試仿真首先設(shè)定兩個(gè)模擬區(qū)域，區(qū)域里面各存放N個(gè)傳感器模擬個(gè)體節(jié)點(diǎn)，然后設(shè)定各節(jié)點(diǎn)的橫縱坐標(biāo)的均值、方差、均值。各傳感器個(gè)體節(jié)點(diǎn)的初始方向角為0～180度之間隨機(jī)值。兩個(gè)區(qū)域的各傳感器節(jié)點(diǎn)編號(hào)后，設(shè)定各傳感器的感應(yīng)半徑，各個(gè)傳感器的感應(yīng)半徑相同。

系統(tǒng)仿真過程中，采集到的區(qū)域一中4個(gè)不同時(shí)刻的各個(gè)傳感器的X坐標(biāo)、Y坐標(biāo)、運(yùn)動(dòng)方向，見表1、表2、表3、表4中可以看到，對(duì)部分個(gè)體節(jié)點(diǎn)系統(tǒng)收斂的運(yùn)動(dòng)方向一致。

3.結(jié)論

在假設(shè)傳感器網(wǎng)絡(luò)保持聯(lián)通的情況下，經(jīng)過測試得出結(jié)論，影響算法的收斂速度較大是傳感器感器通信半徑，通信半徑直接影響區(qū)域內(nèi)的個(gè)體節(jié)點(diǎn)數(shù)量。在實(shí)驗(yàn)中通過對(duì)傳感器的通信半徑設(shè)定初值為 2，3、4、5、6、7等進(jìn)行實(shí)驗(yàn)，其它參數(shù)不改變，與之前仿真相同。每次實(shí)驗(yàn)中算法執(zhí)行次數(shù)都以 10 為步長從 200 開始遞增。在實(shí)驗(yàn)中，如果通信半徑過小，則不能構(gòu)成電子?xùn)艡?，而隨著通信半徑的增加，收斂速度立式越短。經(jīng)過實(shí)驗(yàn)測試和仿真得出結(jié)論：當(dāng)通信半徑較大時(shí)，某傳感器節(jié)點(diǎn)的相鄰個(gè)體節(jié)點(diǎn)集合元素增多，DSDAC算法收斂時(shí)效較快;當(dāng)通信半徑變小的時(shí)候，傳感器節(jié)點(diǎn)的相鄰個(gè)體節(jié)點(diǎn)集合元素逐漸減少，系統(tǒng)的收斂速度較慢。通過上述實(shí)驗(yàn)可知，基于Vicsek 模型的DSDAC算法仿真結(jié)果，當(dāng)通信半徑合理時(shí)，應(yīng)用在無線傳感器網(wǎng)絡(luò)，解決電子?xùn)艡诟采w問題是可行的。

參考文獻(xiàn)：

[1] T. Vicsek， A. Czirok， E.B. Jacob， et al. Novel type of phase transitions in a system of self-drivenparticles[C]. Physical Review Letters 75， 1995， pp. 1226C1229.

[2]范興剛 等.一種概率柵欄覆蓋模型及其構(gòu)建算法.計(jì)算機(jī)研究與發(fā)展.2017， 54（5）

[3]黨小超 等.一種基于改進(jìn)蟻群算法的三維K-柵欄覆蓋算法計(jì)算機(jī)工程2020， 46（2）

王振滔：衢州學(xué)院2018級(jí)電氣工程及其自動(dòng)化本科學(xué)生。資助項(xiàng)目：衢州學(xué)院大學(xué)生科技創(chuàng)新項(xiàng)目（項(xiàng)目編號(hào)：Q20X051）