無線傳感網(wǎng)絡(luò)基于有限能量和位置信息的算法

◎李為為

（阜陽職業(yè)技術(shù)學(xué)院工程科技學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)教研 室，安徽 阜陽 236000）

無線傳感網(wǎng)絡(luò)基于有限能量和位置信息的算法

◎李為為

（阜陽職業(yè)技術(shù)學(xué)院工程科技學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)教研 室，安徽 阜陽 236000）

通過讓一部分節(jié)點(diǎn)休眠，緩解傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能量限制。 提出一種用于數(shù)字物流的基于有限能量和位置信息的算法。仿真結(jié)果表明，采用這樣的方式，在不影響路由有效性的情況下，可以節(jié)約節(jié)點(diǎn)能量，同時(shí)還考慮了節(jié)點(diǎn)能量消耗的均衡性。

傳感器網(wǎng)絡(luò)；有限能量和位置信息算法；節(jié)約節(jié)點(diǎn)能量

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是一種由大量的在監(jiān)測(cè)區(qū)域部署密集的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)應(yīng)用系統(tǒng)［1］。傳感器節(jié)點(diǎn)的數(shù)量很多，節(jié)點(diǎn)的部署方式很隨機(jī)，節(jié)點(diǎn)的位置事先也是無法預(yù)知的；采用無線的方式進(jìn)行信息傳遞，節(jié)點(diǎn)的通信方式為多跳（multi-hop）、對(duì)等，自組織網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；節(jié)點(diǎn)間通過局部節(jié)點(diǎn)協(xié)調(diào)進(jìn)行數(shù)據(jù)采集、處理及交換信息。傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗模塊包括無線通信模塊、處理器模塊和傳感器模塊。其中，無線通信模塊集中了傳感器能量消耗的主要部分。發(fā)送、空閑、接收和睡眠4種狀態(tài)中，無線通信模塊的能量消耗主要集中在發(fā)送狀態(tài)。在發(fā)送狀態(tài)中，無線通信模塊消耗的能量是最大的，處于睡眠狀態(tài)的傳感器節(jié)點(diǎn)能聊消耗是最小的［2］。所以，在研究如何使傳感器網(wǎng)絡(luò)通信更有效率，使節(jié)點(diǎn)更快地進(jìn)入睡眠，節(jié)點(diǎn)發(fā)送和接收的信息盡量少，是網(wǎng)絡(luò)設(shè)計(jì)方面主要考慮的問題。

在無線傳感網(wǎng)中，很多場(chǎng)景不僅要收到節(jié)點(diǎn)的信息，還需要至少發(fā)送信息的節(jié)點(diǎn)位置，這樣才可以進(jìn)行下一步的行動(dòng)［3］。例如，在森林中對(duì)火災(zāi)情況的監(jiān)測(cè)，接收到火情，營救人員要知道火災(zāi)發(fā)生的具體位置，才可能進(jìn)行營救。提出的基于地理位置路由算法，假設(shè)節(jié)點(diǎn)部署后事先知道自己的位置，節(jié)點(diǎn)在發(fā)送信息時(shí)，接收信息者能夠根據(jù)節(jié)點(diǎn)發(fā)送的信息得到發(fā)送信息節(jié)點(diǎn)的位置或者所在區(qū)域的信息，節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)選擇合適的路徑和策略將信息發(fā)送到目的地，將提出的算法與合適路由信息相結(jié)合將信息發(fā)送到用戶終端。對(duì)位置信息確定的準(zhǔn)確性與相應(yīng)的節(jié)點(diǎn)花費(fèi)的代價(jià)相關(guān)。因此，根據(jù)不同的應(yīng)用需求，需要與合適的路由協(xié)議相結(jié)合，將信息傳輸?shù)接脩艚K端。提出的基于有限能量和位置信息的算法主要在不影響路由有效性的情況下，關(guān)閉一些不需要的節(jié)點(diǎn)來節(jié)省能量，如對(duì)物流的運(yùn)輸過程的監(jiān)測(cè)。采用虛擬網(wǎng)格思想的分簇機(jī)制［4］，在一個(gè)虛擬的網(wǎng)格中，采用選擇等價(jià)節(jié)點(diǎn)的方法，在等價(jià)節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)工作，其他不工作的節(jié)點(diǎn)可以休眠以節(jié)約能量。這樣既可以實(shí)時(shí)監(jiān)測(cè)物流在運(yùn)輸過程中商品的性能，又可以節(jié)約不必要的能量消耗，實(shí)現(xiàn)了節(jié)點(diǎn)能量消耗的均衡性。

上述基于有限能量和位置信息的算法可以用于物流運(yùn)輸過程中對(duì)運(yùn)輸商品的信息的測(cè)量。在運(yùn)輸過程中，采取讓一部分節(jié)點(diǎn)休眠來節(jié)約能量，工作的節(jié)點(diǎn)將采集到的信息發(fā)送到用戶終端。算法為LEACH［5］算法的分簇機(jī)制提供了新的思路，設(shè)計(jì)了基于有限能量和位置信息的算法，同時(shí)考慮了所有節(jié)點(diǎn)能量消耗的均衡性。提出的基于有限能量和位置信息的算法的中心思想是，首先劃分虛擬網(wǎng)格，然后進(jìn)行采用比較剩余能量的方法在虛擬網(wǎng)格中選擇一個(gè)節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，通過這種機(jī)制讓不工作的節(jié)點(diǎn)消耗更少的能量，實(shí)現(xiàn)所有節(jié)點(diǎn)能量消耗的均衡性。

1　有限能量和位置信息的算法模型

我們提出的算法主要用于物流運(yùn)輸過程中對(duì)運(yùn)輸商品參數(shù)測(cè)量的情況。針對(duì)物流的場(chǎng)景建立如圖1所示的有限能量和位置信息的算法模型。

圖1　有限能量和位置信息的算法模型圖

所提出的算法的核心思想如下：按柵格選擇代表節(jié)點(diǎn)的方法，從刪格中選擇一小部分節(jié)點(diǎn)，與數(shù)學(xué)上在全集中選擇一部分子集很相似，同時(shí)節(jié)點(diǎn)當(dāng)前的能量狀態(tài)作為是否設(shè)置該節(jié)點(diǎn)為信息轉(zhuǎn)發(fā)節(jié)點(diǎn)的依據(jù)，能有效地延長網(wǎng)絡(luò)的生存時(shí)間。

2　LEACH算法

LEACH［6］算法是Heinzelman等提出的用于無線傳感器網(wǎng)絡(luò)分簇的經(jīng)典算法。通過將“輪”的思想引入算法，每輪中將節(jié)點(diǎn)的狀態(tài)分為初始化和穩(wěn)定工作2個(gè)階段。在初始化的階段，完成網(wǎng)絡(luò)節(jié)點(diǎn)中簇頭的選舉和成簇的2個(gè)任務(wù)。節(jié)點(diǎn)部署后通過隨機(jī)產(chǎn)生0～1之間的隨機(jī)數(shù)，然后設(shè)置閾值T（n），通過比較節(jié)點(diǎn)與閾值的大小，確定節(jié)點(diǎn)是否為簇頭，成為簇頭的節(jié)點(diǎn)通過廣播告訴其他簇頭節(jié)點(diǎn)。T（n）的表達(dá)式如下：

式中參數(shù)設(shè)置如下：簇頭數(shù)量的百分比，p；網(wǎng)絡(luò)中節(jié)點(diǎn)選擇輪數(shù)，r；一輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)，mod（1/p）；未當(dāng)選過簇頭節(jié)點(diǎn)集合，G。

網(wǎng)絡(luò)中的部分成為簇頭的節(jié)點(diǎn)發(fā)布廣播信息后，非簇頭節(jié)點(diǎn)根據(jù)其所接收的成為簇頭節(jié)點(diǎn)的信號(hào)的強(qiáng)度，選擇信號(hào)較強(qiáng)的簇頭節(jié)點(diǎn)加入，該階段為成簇階段。

簇頭節(jié)點(diǎn)接收到簇內(nèi)成員節(jié)點(diǎn)發(fā)布的信息，將信息融合后發(fā)送給匯聚中心，該階段為穩(wěn)定階段。

LEACH算法實(shí)現(xiàn)起來比較容易，通過簇頭的選擇解決了能量負(fù)載的平衡，但是還存在一定的不足之處。例如，選舉簇頭時(shí)，節(jié)點(diǎn)采用隨機(jī)的方式成簇，這樣相應(yīng)帶來簇頭位置的隨機(jī)以及簇內(nèi)節(jié)點(diǎn)數(shù)量的不均衡，對(duì)簇頭節(jié)點(diǎn)的剩余能量也沒有考慮到，網(wǎng)絡(luò)中節(jié)點(diǎn)的位置也是未知的。該文基于以上兩個(gè)問題，對(duì)節(jié)點(diǎn)的能量和位置信息進(jìn)行了考慮，借用Leach算法的分簇機(jī)制，改進(jìn)了算法選舉簇頭和算法中未知節(jié)點(diǎn)位置信息的不足。

3　有限能量和位置信息的算法

3.1網(wǎng)絡(luò)模型

剛剛過去的金秋十月，中國鐵路昆明局集團(tuán)完成旅客發(fā)送482.5萬人，單日旅客發(fā)送最高突破30萬人次，然而1978年云南鐵路準(zhǔn)軌每月發(fā)送旅客僅為50萬人，增長近9倍。

3.1.1階段一：劃分網(wǎng)格

節(jié)點(diǎn)部署后，假定節(jié)點(diǎn)相互之間知道位置信息，根據(jù)節(jié)點(diǎn)的通信距離和節(jié)點(diǎn)所在的位置，將節(jié)點(diǎn)的部署的網(wǎng)格區(qū)域分成很多虛擬的網(wǎng)格，假定鄰近的任意兩個(gè)單元格都能夠相互通信。初始時(shí)做出如下假設(shè)：①節(jié)點(diǎn)自身的位置和整個(gè)網(wǎng)絡(luò)區(qū)域節(jié)點(diǎn)的位置是已知的；②節(jié)點(diǎn)可以通過位置信息和網(wǎng)絡(luò)中節(jié)點(diǎn)的相對(duì)位置信息計(jì)算出自己屬于哪個(gè)網(wǎng)絡(luò)。

3.1.2階段二：在虛擬的網(wǎng)格中選擇簇頭

通過設(shè)置一定的周期，使節(jié)點(diǎn)在睡眠和工作狀態(tài)中進(jìn)行切換，周期性醒來的節(jié)點(diǎn)與網(wǎng)格中的其他節(jié)點(diǎn)相互傳遞信息，以此來判定下次成為簇頭的節(jié)點(diǎn)。

3.2選擇簇頭

從LEACH協(xié)議可以得到，選擇簇頭的多少對(duì)網(wǎng)絡(luò)的生命周期有一定的影響。如果選擇簇頭節(jié)點(diǎn)較少，會(huì)導(dǎo)致一個(gè)簇所能監(jiān)測(cè)的區(qū)域過大，簇內(nèi)成員節(jié)點(diǎn)與簇頭的距離較遠(yuǎn)，這樣會(huì)有大量的不必要的傳輸數(shù)據(jù)的能量消耗；如果選擇簇頭節(jié)點(diǎn)較多，鑒于簇頭節(jié)點(diǎn)的能量消耗遠(yuǎn)大于非簇頭節(jié)點(diǎn)，這樣會(huì)帶來節(jié)點(diǎn)在進(jìn)行路由選擇時(shí)消耗的總能量加大，而且還會(huì)降低數(shù)據(jù)融合的效率，導(dǎo)致會(huì)有很多不必要的數(shù)據(jù)融合。

提出的算法中假設(shè)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都有睡眠（sleeping）、活動(dòng)（Active）和發(fā)現(xiàn)（Discovery）3種狀態(tài)［6］，如圖2所示。

圖2　節(jié)點(diǎn)狀態(tài)關(guān)系圖

在網(wǎng)絡(luò)部署后，網(wǎng)絡(luò)中全部的節(jié)點(diǎn)都處于發(fā)現(xiàn)的狀態(tài)，網(wǎng)絡(luò)中的節(jié)點(diǎn)都通過相互發(fā)送信息告知鄰居節(jié)點(diǎn)自己的ID和位置等信息，這樣網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠得到網(wǎng)格內(nèi)其他節(jié)點(diǎn)的信息。接著，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)把自身的定時(shí)器設(shè)置為隨機(jī)值。當(dāng)節(jié)點(diǎn)的定時(shí)器超時(shí)，節(jié)點(diǎn)就開始傳遞消息，告知鄰居節(jié)點(diǎn)它進(jìn)入活動(dòng)狀態(tài)，并發(fā)布自己成為簇頭節(jié)點(diǎn)。

如果節(jié)點(diǎn)在其定時(shí)器超時(shí)前接收到網(wǎng)格中其他節(jié)點(diǎn)成為簇頭的消息，證明節(jié)點(diǎn)此次競(jìng)爭(zhēng)簇頭失敗，節(jié)點(diǎn)進(jìn)而轉(zhuǎn)入睡眠狀態(tài)。競(jìng)爭(zhēng)成為簇頭的節(jié)點(diǎn)通過設(shè)置定時(shí)器，確定節(jié)點(diǎn)保持活動(dòng)狀態(tài)的時(shí)間。在節(jié)點(diǎn)定時(shí)器超時(shí)前，簇頭節(jié)點(diǎn)定時(shí)廣播消息證明自己處于活動(dòng)狀態(tài)，以此來抑制其他處于發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)轉(zhuǎn)入活動(dòng)狀態(tài)。在節(jié)點(diǎn)定時(shí)器超時(shí)后，簇頭節(jié)點(diǎn)重新將狀態(tài)設(shè)置為發(fā)現(xiàn)。此時(shí)在睡眠狀態(tài)的節(jié)點(diǎn)設(shè)置定時(shí)器，并在定時(shí)器超時(shí)后，節(jié)點(diǎn)重新設(shè)置為發(fā)現(xiàn)狀態(tài)。處于活動(dòng)狀態(tài)的節(jié)點(diǎn)發(fā)現(xiàn)了網(wǎng)絡(luò)中出現(xiàn)更適合作為簇頭的節(jié)點(diǎn)后，節(jié)點(diǎn)會(huì)自動(dòng)將狀態(tài)切換到睡眠狀態(tài)。在超時(shí)后，簇頭節(jié)點(diǎn)重新回到發(fā)現(xiàn)狀態(tài)。處于睡眠狀態(tài)的節(jié)點(diǎn)設(shè)置定時(shí)器為，并在超時(shí)后，節(jié)點(diǎn)重新回到發(fā)現(xiàn)狀態(tài)。處于活動(dòng)狀態(tài)或發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)如果發(fā)現(xiàn)本單元格中出現(xiàn)了更適合成為簇頭的節(jié)點(diǎn)時(shí)，會(huì)自動(dòng)進(jìn)入睡眠狀態(tài)。

4　仿真結(jié)果

采用Matlab仿真了所提出的算法。并對(duì)比了每隔10S節(jié)點(diǎn)平均剩余能量和每輪存活節(jié)點(diǎn)數(shù)。仿真過程中的參數(shù)設(shè)置如表1所示。

表1　仿真過程中的參數(shù)設(shè)置表

4.1 仿真場(chǎng)景1：節(jié)點(diǎn)剩余平均能量比較

每隔10 s對(duì)比節(jié)點(diǎn)的平均剩余能量。節(jié)點(diǎn)平均剩余能量如圖3所示。

圖3　節(jié)點(diǎn)剩余平均能量圖

圖3顯示了當(dāng)節(jié)點(diǎn)數(shù)為400時(shí)，節(jié)點(diǎn)的平均剩余能量。由圖3可以看出，采用該算法初始時(shí)能夠基本保證剩余能量的均衡，實(shí)現(xiàn)延長網(wǎng)絡(luò)生命周期的目的。

4.2仿真場(chǎng)景2：存活節(jié)點(diǎn)數(shù)目對(duì)照

參數(shù)設(shè)置如下：傳感器節(jié)點(diǎn)數(shù)，400個(gè)；網(wǎng)絡(luò)運(yùn)行論數(shù)，1∶10，length（energy_cost_per_times），其中l(wèi)ength（energy_cost_per_times）為當(dāng)前節(jié)點(diǎn)剩余能量值。

圖4顯示了采用該算法在一段時(shí)間內(nèi)基本能夠保證死亡節(jié)點(diǎn)數(shù)為0，證明了提出的算法能夠?qū)崿F(xiàn)節(jié)點(diǎn)能量均衡消耗。

5　結(jié)語

該文提出了有限能量和位置信息的算法。通過采用網(wǎng)格的思想，讓節(jié)點(diǎn)周期性的休眠，從而實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)能量均衡消耗，進(jìn)而延長了網(wǎng)絡(luò)生命周期。且算法是基于平面模型的，沒有考慮到實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)之間距離的鄰近，并不能代表節(jié)點(diǎn)之間可以直接通信的問題，因此存在一些不足，后續(xù)工作中將會(huì)研究如何改進(jìn)這些不足［7］。

[1] J. Hao，B. X. Zhang，H. T. Mouftah. Routing protocols for duty cycled wireless sensor networks：a survey[J]. IEEE Communications Magazine，2012，50（12）：116-123.

[2]孫利民，李中建，陳 渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[3] P K Tripathi，N Sing，K Verma. Clustering algorithm for non-uniformly distributed nodes in wireless sensor network[J]. Electronics Letters，2013，49（4）：299-300.

[4] X Li，S Soltani，W Mutka，et al. The evolution of MAC protocols in wireless sensor networks：a survey[J]. IEEE Communications Surveys & Tutorials，2013，15（1）：101-120.

[5] S Deng，J Li，L Shen. Mobility-based clustering protocol for wireless sensor networks with mobile nodes[J]. IET wireless Sensor Systems，2011，1（1）：39-47.

[6]肖純賢，朱丙瑜，趙晶菁，等.無線傳感器網(wǎng)絡(luò)LEACH算法的改進(jìn)[J].南開大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，43（5）：34-36.

[7]喬曉軍，張 馨，王 成，等.無線傳感器網(wǎng)絡(luò)在農(nóng)業(yè)中的應(yīng)用[J].農(nóng)業(yè)工程學(xué)報(bào)，2005，21（增刊）：232-234.

Based on Incident Response Algorithm for Wireless Sensor Networks

Li Weiwei
（Computer Network Teaching and Research Section of Fuyang Vocational and Technical College，F(xiàn)uyang 236000， China）

By allowing a portion of the nodes to sleep， the energy limitation of sensor network nodes was alleviated. An algorithm based on finite energy and position information for digital logistics was proposed. Simulation results showed that in such a way， without affecting the validity of the route， the node could save energy， but also consider the node energy consumption balance.

Sensor network； Finite energy and position information of an algorithm； The node energy saving

TN915

10.16736/j.cnki.cn41-1434/ts.2016.06.028

關(guān)聯(lián)規(guī)則在高職學(xué)生就業(yè)數(shù)據(jù)處理中的應(yīng)用研究（編號(hào)：KJ2016A561）。

李為為（1984-），女，河南周口人，碩士研究生，助教；主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)拓?fù)淇刂啤?/p>