無線路燈的三鏈路由算法和協(xié)議設(shè)計(jì)

史新峰，王宜懷，顧會光

（蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州215000）

0 引 言

路燈的相對物理位置不同于大多數(shù)學(xué)者所研究的傳感網(wǎng)絡(luò)，那些節(jié)點(diǎn)一般呈面式分布，而路燈具有獨(dú)有的單條、雙條、三條等平行式的物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并且要求高穩(wěn)定性、協(xié)議低實(shí)現(xiàn)難度和后期可維護(hù)性?，F(xiàn)有的無線通信協(xié)議并不是基于以上前提提出的，如802.15.4協(xié)議并不能完成路燈組網(wǎng)要求，ZigBee協(xié)議因其復(fù)雜性開發(fā)難度大導(dǎo)致穩(wěn)定性差，也不能很好的適用于無線路燈這種具體應(yīng)用。其網(wǎng)絡(luò)層的AODV 路由算法和對應(yīng)的簡化版本AODVjr，是為了適用于拓?fù)浠蛲ㄐ庞袝r發(fā)生變化的環(huán)境［2］。路燈拓?fù)鋮s是一旦確定下來，拓?fù)浣Y(jié)構(gòu)就不再發(fā)生變化，顯然ZigBee的復(fù)雜路由協(xié)議用在這里并不合適。

為了降低協(xié)議棧開發(fā)難度和提升穩(wěn)定性，國內(nèi)一部分公司采用最簡單的洪泛通信模式，這種路由方式簡單粗糙，效率非常低，冗余數(shù)據(jù)特別多［3］。綜上，針對路燈具體拓?fù)?，設(shè)計(jì)一種簡單高效穩(wěn)定的路由算法十分有必要。

1 網(wǎng)絡(luò)拓?fù)浜头?wù)函數(shù)

1.1 網(wǎng)絡(luò)拓?fù)?/h3>

路燈網(wǎng)絡(luò)是一類具體結(jié)構(gòu)網(wǎng)絡(luò)，絕大多數(shù)的拓?fù)浣Y(jié)構(gòu)如圖1所示，是兩條平行線，根據(jù)馬路的寬度不同也有一條、三條和四條等，這里我們以最常見的兩條為例進(jìn)行研究，在實(shí)際應(yīng)用中，可以根據(jù)具體情況稍做修改和擴(kuò)展就可以適應(yīng)單條或多條路燈的情況。我們把協(xié)調(diào)器 （也常被稱作Sink節(jié)點(diǎn)）放置在路燈的一側(cè)的前端或是后端，為了表達(dá)方便，把協(xié)調(diào)器放置在前端，每條路配備一個協(xié)調(diào)器。并且給每盞路燈依次編號。

圖1 路燈的拓?fù)浣Y(jié)構(gòu)

1.2 MAC層需提供的服務(wù)函數(shù)

很多研究者是在一個假設(shè)的基礎(chǔ)上，進(jìn)行路由的研究和設(shè)計(jì)，嚴(yán)重降低了算法的實(shí)用性和可實(shí)踐性。為了克服以上不足，三鏈路由算法不是建立在假設(shè)的基礎(chǔ)之上，而是建立在以下兩個MAC 層提供的函數(shù)。而這兩個函數(shù)在任何無線芯片上都較容易實(shí)現(xiàn)。

（1）int MAC＿SendDataRequest（int destadd，char＊data，int length）；

其中函數(shù) （1）提供的功能是將數(shù)據(jù)發(fā)送到目的節(jié)點(diǎn)，但必須加以說明的是，這個函數(shù)中必須得采取CSMA／CA發(fā)送機(jī)制，從而協(xié)調(diào)MAC 層的發(fā)送順序。函數(shù) （2）的功能是只接收MAC地址跟自己匹配的MAC 幀數(shù)據(jù)，除此之外全部忽略掉，也就是說MAC 層不必提供廣播功能，而廣播的功能是在網(wǎng)絡(luò)層的三鏈路由算法實(shí)現(xiàn)的。這個函數(shù)是將收到的數(shù)據(jù)放入緩沖區(qū)并將其地址提交給上層。雖然在發(fā)送函數(shù)中采用了CSMA／CA 發(fā)送機(jī)制，但是MAC 層不要求服從802.15.4協(xié)議。

單燈的MAC地址可以跟圖1中的編號一一對應(yīng)，但會出現(xiàn)兩個單燈節(jié)點(diǎn)具有同樣MAC 地址的問題。因此需要根據(jù)單燈節(jié)點(diǎn)所在的那一側(cè)，來給編號前加一個域進(jìn)行區(qū)分。這樣MAC地址就會變成如圖2所示的那樣。

圖2 MAC地址

2 三鏈路由算法

2.1 算法原理

單燈節(jié)點(diǎn)的有效發(fā)送半徑用r表示，路燈單燈間的距離用d表示，單側(cè)安裝的路燈總數(shù)用sum 表示。在路由的過程中，我們采取的是從一級鏈到三級鏈逐步縮小范圍的方式進(jìn)行的。

2.1.1 一級鏈

根據(jù)路燈的物理拓?fù)浣Y(jié)構(gòu)，我們把馬路兩側(cè)的路燈分為兩條一級鏈。在這里使用＜X＞表示鏈號，如圖3所示。

圖3 一級鏈

2.1.2 二級鏈

根據(jù)單燈節(jié)點(diǎn)的有效發(fā)送半徑r和路燈間的距離d可以確定二級鏈。二級鏈的最小單位不是單個節(jié)點(diǎn)，而是以一定數(shù)量為n的節(jié)點(diǎn)組為一個單位，各個單位間又發(fā)生通信關(guān)系，從而形成了二級鏈。其中n的最簡單取值方式為r／d。二級鏈可用如下表示形式：＜X＞－＜Y＞，其中X是一級鏈號，Y 為二級鏈號，Y 的可取值為：1，n＋1，2n＋1，3n＋1，…， （sum／n－1）＊n＋1。例如，在r＝100m，d＝25m，sum＝200的情況下，可以算出n＝4，那么Y 的取值為1，5，9，13，…，197 具體示意如圖4 所示。其實(shí)二級鏈號＜Y＞就是對應(yīng)那一組離協(xié)調(diào)器最近的那個單燈節(jié)點(diǎn)的MAC 地址。也正是這些節(jié)點(diǎn)間的相互通信形成了二級鏈。

圖4 二級鏈

2.1.3 三級鏈

這一級鏈的最小單位是單燈節(jié)點(diǎn)，也就是說它是組內(nèi)鏈。為了說明組內(nèi)鏈的特性，我們以星型網(wǎng)絡(luò)為對比對象，其組內(nèi)所有信息都是通過組內(nèi)中心節(jié)點(diǎn)轉(zhuǎn)發(fā)。我們在單播時三級鏈組內(nèi)會采用跟星型網(wǎng)絡(luò)相同的方式轉(zhuǎn)發(fā)，而廣播時三級鏈上是一個串聯(lián)一個，形成一個小鏈，從而達(dá)到廣播的功能。每個節(jié)點(diǎn)的地址可以用如下形式表示：＜X＞－＜Z＞，其中Z的取值跟圖1中的單燈編號一一對應(yīng)為：1，2，3……。圖5給出了3個鏈的全部數(shù)據(jù)流。

圖5 三級鏈

需要注意兩點(diǎn)，第一點(diǎn)，在以上給出的二級鏈和三級鏈的劃分只是一個靜態(tài)的劃分，而實(shí)際運(yùn)行的三鏈路由算法中，二級鏈和三級鏈的劃分都是動態(tài)變化的，這正是三鏈路由算法的核心特點(diǎn)，這個特點(diǎn)是降低開發(fā)難度、提升網(wǎng)絡(luò)穩(wěn)定性和簡化后期維護(hù)的根本基礎(chǔ)。第二點(diǎn)，三鏈路由算法中，二級鏈地址＜X＞－＜Y＞和三級鏈地址＜X＞－＜Z＞在形式上是一模一樣的從而導(dǎo)致區(qū)分不開，只有在路由的過程中會區(qū)分出來，所以這里我們用＜X＞－＜Y／Z＞來表示單燈節(jié)點(diǎn)的網(wǎng)絡(luò)地址。所有網(wǎng)絡(luò)地址不支持動態(tài)分配和隨意更改，跟MAC 地址是一一對應(yīng)的。在不斷變化的網(wǎng)絡(luò)中，采用固定網(wǎng)絡(luò)地址是不能滿足要求的，但是對于路燈這種一旦確定下來就不會改變的網(wǎng)絡(luò)特性，采取固定網(wǎng)絡(luò)地址，利于使用簡單算法實(shí)來現(xiàn)路由功能。

2.2 算法實(shí)現(xiàn)

跟傳統(tǒng)路由算法不同的是，三鏈路由算法不要求路燈節(jié)點(diǎn)計(jì)算最短路徑然后形成路由表，并且還得不斷的維護(hù)路由表。三鏈路由算法只需要節(jié)點(diǎn)能向目的地址發(fā)送數(shù)據(jù)，并且當(dāng)作為接收節(jié)點(diǎn)時可以通過回發(fā)ACK 幀的方式確認(rèn)是否發(fā)送成功等功能。在算法原理里我們提出了3個鏈的劃分，而實(shí)際在算法實(shí)現(xiàn)上，第二級鏈和第三級鏈的形成都是動態(tài)形成并不斷變化的。對于單燈節(jié)點(diǎn)而言，每個節(jié)點(diǎn)的內(nèi)部控制程序除了MAC 地址以外其它部分是完全一樣的。

2.2.1 單播

單播主要分為3部分。當(dāng)協(xié)調(diào)器接收到數(shù)據(jù)后先進(jìn)行一級鏈判斷，然后轉(zhuǎn)發(fā)給路燈節(jié)點(diǎn)。每個路燈節(jié)點(diǎn)接到數(shù)據(jù)后都會進(jìn)行二級鏈和三級鏈判斷，最終接收到數(shù)據(jù)。單播的詳細(xì)流程如圖6所示。

圖6給出的是下行數(shù)據(jù)的路由方式，也就是協(xié)調(diào)器給單燈節(jié)點(diǎn)發(fā)送數(shù)據(jù)的路由方式。上行數(shù)據(jù)發(fā)送跟下行數(shù)據(jù)發(fā)送原理一樣，但是一般不會正好逆著下行數(shù)據(jù)發(fā)送的路徑發(fā)送回去，因?yàn)閱螣艄?jié)點(diǎn)會根據(jù)自己的地址重組二級鏈和三級鏈，這個時候發(fā)送節(jié)點(diǎn)自動晉升為二級鏈中的一個節(jié)點(diǎn)，協(xié)調(diào)器會退化成為一個三級鏈節(jié)點(diǎn)。圖7是同一單燈節(jié)點(diǎn)的下行接收數(shù)據(jù)和上行發(fā)送數(shù)據(jù)路徑對比。

2.2.2 廣播

圖6 單播數(shù)據(jù)流程

圖7 上行和下行對比

在對單燈節(jié)點(diǎn)通信的過程中，其實(shí)并沒有使用到三級鏈，不過對于路燈的控制更多的是廣播數(shù)據(jù)，這個時候三級鏈就會反復(fù)的用到。這里必須引入一個控制參數(shù)c，標(biāo)識當(dāng)前數(shù)據(jù)幀所處的路由鏈級數(shù)，其次跳數(shù)n也會被反復(fù)使用。如果沒有c，當(dāng)＜X＞－＜Y／Z＞收到數(shù)據(jù)后就沒有辦法判斷是將數(shù)據(jù)轉(zhuǎn)發(fā)給下一二級鏈單元，還是轉(zhuǎn)發(fā)給三級鏈單位。在三級鏈轉(zhuǎn)發(fā)的過程中，每轉(zhuǎn)發(fā)一次數(shù)據(jù)包的n值就會被減1，當(dāng)n等于1 時，說明最后一個節(jié)點(diǎn)接收到了數(shù)據(jù)，停止轉(zhuǎn)發(fā)。具體的流程如圖8所示。

圖8 廣播流程

3 協(xié)議設(shè)計(jì)

任何協(xié)議的設(shè)計(jì)都會體現(xiàn)在幀結(jié)構(gòu)上，同樣三鏈路由也是靠具體網(wǎng)絡(luò)層的幀控制來實(shí)現(xiàn)的。圖9給出了網(wǎng)絡(luò)層的通信數(shù)據(jù)幀結(jié)構(gòu)組成。其中地址3字節(jié)的第一個字節(jié)用來存放＜X＞，后兩字節(jié)用來存放＜X／Y＞除此之外，因?yàn)槁放c路之間的節(jié)點(diǎn)地址都是重復(fù)的。所以每條路必須有一個唯一的網(wǎng)絡(luò)號，從而避免相鄰道路節(jié)點(diǎn)之間數(shù)據(jù)發(fā)生混亂。

4 測試結(jié)果和評價

為了檢驗(yàn)三鏈路由算法和其對應(yīng)協(xié)議的特性，用40個節(jié)點(diǎn)和一個協(xié)調(diào)器來組成一個微型路燈網(wǎng)絡(luò)。其中sum＝20，r＝10m，d＝3m。即微型路燈網(wǎng)絡(luò)的單側(cè)節(jié)點(diǎn)數(shù)量為20，有效發(fā)送半徑為10m，相鄰節(jié)點(diǎn)間的距離為3 m。同時采用同樣硬件節(jié)點(diǎn)設(shè)置了兩個對比微型網(wǎng)絡(luò)，一個采用很多無線路燈公司正在使用的泛洪通信方式，另外一個采用TI公司推出遵從ZigBee協(xié)議實(shí)現(xiàn)的Zstack協(xié)議棧。經(jīng)過10 萬次通信量的數(shù)據(jù)統(tǒng)計(jì)和分析，實(shí)驗(yàn)結(jié)果見表1和表2。

表1 與泛洪通信網(wǎng)絡(luò)的對比

表2 與Zstack通信網(wǎng)絡(luò)的對比

圖9 幀結(jié)構(gòu)組成

通過實(shí)驗(yàn)數(shù)據(jù)結(jié)果和對比結(jié)果可以發(fā)現(xiàn)，三鏈路由通信方式在平均延遲和丟包率上優(yōu)于洪泛通信和Zsatck協(xié)議棧。在丟包率方面，同樣優(yōu)于Zstack協(xié)議棧的表現(xiàn)，但是稍弱于泛洪通信方式。由于泛洪通信的特殊傳送數(shù)據(jù)方式，保證了它具有較低丟包率，而三鏈路由通信為了在其它屬性方面得到提升，放棄一定的丟包率是可以接受的。

除此之外，三鏈路由算法和對應(yīng)協(xié)議還具有以下三方面的優(yōu)點(diǎn)。

4.1 算法實(shí)現(xiàn)難度低

不同于其它很多算法，它不需要建立在一定的假設(shè)和前提下。它只需要兩個基本的收發(fā)函數(shù)就可以實(shí)現(xiàn)。另外，算法不需要計(jì)算最短路徑和建立維護(hù)路由表等復(fù)雜操作，對算法實(shí)現(xiàn)進(jìn)行了極大地簡化，從而對于編碼實(shí)現(xiàn)降低了編寫和調(diào)試的難度。在實(shí)際工程中，有非常好的指導(dǎo)作用。

4.2 路燈節(jié)點(diǎn)間相互協(xié)調(diào)完成路由

不同于其它需要路由設(shè)備支持的網(wǎng)絡(luò)，三鏈路燈路由算法是靠各個子節(jié)點(diǎn)間的協(xié)調(diào)完成路由并通信的。故對開發(fā)人員而言，不需再專門開發(fā)一種路由設(shè)備，節(jié)省了費(fèi)用、人力和時間成本。

4.3 網(wǎng)絡(luò)健壯性高

雖然路燈網(wǎng)絡(luò)是一個非移動的固定網(wǎng)絡(luò)，不會有新路燈節(jié)點(diǎn)的加入和離開，但是在運(yùn)行的過程中，依然會有網(wǎng)絡(luò)節(jié)點(diǎn)在不確定的時間發(fā)生故障或是損壞。強(qiáng)健的網(wǎng)絡(luò)是不允許由于單個節(jié)點(diǎn)損壞從而導(dǎo)致整個網(wǎng)絡(luò)的癱瘓現(xiàn)象出現(xiàn)的。對三鏈路由算法稍做改動就可以避免發(fā)生這種現(xiàn)象。我們假設(shè)二級鏈中某個節(jié)點(diǎn)發(fā)生故障來分析。

對于單播或是廣播，首先需要發(fā)現(xiàn)故障路燈，發(fā)現(xiàn)方式為：當(dāng)向目標(biāo)節(jié)點(diǎn)發(fā)送信息的源節(jié)點(diǎn)或是協(xié)調(diào)器連續(xù)幾次都沒有得到目標(biāo)節(jié)點(diǎn)的確認(rèn)信息，則源節(jié)點(diǎn)認(rèn)為目標(biāo)節(jié)點(diǎn)故障。不管是在單播或是廣播中發(fā)現(xiàn)二級鏈某一路燈節(jié)點(diǎn)故障，都會采取一樣的處理方法。①源節(jié)點(diǎn)會采取繞過故障路燈節(jié)點(diǎn)，重新確定下一跳地址的策略，從而使數(shù)據(jù)包向最終目的路燈節(jié)點(diǎn)靠近；②源節(jié)點(diǎn)用上行數(shù)據(jù)發(fā)送的方式向協(xié)調(diào)器報告故障路燈的節(jié)點(diǎn)號，協(xié)調(diào)器在接到故障報告后會接著報告給遠(yuǎn)程控制端，等待維護(hù)人員來修理或是更換。圖10給出了節(jié)點(diǎn)發(fā)生故障前后數(shù)據(jù)流對比。

圖10 節(jié)點(diǎn)發(fā)生故障前后數(shù)據(jù)流對比

由于全部路燈節(jié)點(diǎn)都是功能相同的，除了把新的路燈節(jié)點(diǎn)地址修改成為故障路燈節(jié)點(diǎn)的原有地址外，維護(hù)人員不需要做任何其它工作，直接替換就可以了。

5 結(jié)束語

本文提出的算法實(shí)現(xiàn)了對路燈專有網(wǎng)絡(luò)的路由，極大地簡化了開發(fā)人員的開發(fā)難度，況且該算法形成的網(wǎng)絡(luò)具有很好的健壯性和可維護(hù)性。

雖然，本算法有諸多優(yōu)點(diǎn)，但是依然存在不足，比如說需要人為手動的方式燒寫不同的物理地址，我們曾嘗試，通過能量檢測的方式來自動確定自己的物理地址，但是由于不同的節(jié)點(diǎn)發(fā)送的信息能量衰減跟距離不能成穩(wěn)定關(guān)系，從而導(dǎo)致物理地址燒寫混亂，這個問題的解決辦法，會繼續(xù)研究。

［1］HE Sai，CHEN Xiaoping.Application of ZigBee technology to urban lighting monitoring system ［J］.Computer Systems Applications，2011，20 （11）：45－49 （in Chinese）.［何賽，陳小平.ZigBee技術(shù)在城市照明監(jiān)控系統(tǒng)中的應(yīng)用 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20 （11）：45－49.］

［2］SUN Leyi.Wireless monitoring system design and implementation based on ZigBee ［J］.Information System Project，2011（9）：41－48 （in Chinese）.［孫樂益.基于ZigBee無線監(jiān)控系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)研究 ［J］.信息系統(tǒng)工程，2011 （9）：41－48.］

［3］LEI Yang，SHANG Fengjun，REN Yusen.Research on present status of wireless sensor network routing protocol［J］.Communication Technology，2009，42 （3）：117－222 （in Chinese）.［雷陽，尚鳳軍，任宇森.無線傳感網(wǎng)絡(luò)路由協(xié)議現(xiàn)狀研究 ［J］.通信技術(shù)，2009，42 （3）：117－222.］

［4］Lindsey S，Raghavendra C，Sivalingam K.Data gathering algorithms in sensor networks using energy metric ［J］.IEEE Transactions on Parallel and Distributed System，2002，13（9）：924－935.

［5］REN Tiaojuan，CHEN Yourong，WANG Zhangquan.Lifetime optimized algorithm with mobile sink node in wireless sensor networks［J］.Chinese Journal of Sensors and Actuators，2013，82 （1）：684－690 （in Chinese）. ［任條娟，陳友榮，王章權(quán).交通路燈監(jiān)控系統(tǒng)的無線傳感網(wǎng)鏈狀路由算法 ［J］.電信科學(xué)，2013，82 （1）：684－690.］

［6］Heinzelman WR，Chandrakasan A，Balakrishnan H.Energyefficient communication protocol for wireless micro sensor networks［C］／／Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000：1－8.

［7］WANG Yihuai，WU Jin，JIANG Yinzhen.Principle and practice of embedded system ［M］.Beijing：Publishing House of Electronics Industry，2012：392－395 （in Chinese）. ［王宜懷，吳瑾，蔣銀珍.嵌入式系統(tǒng)原理與實(shí)踐 ［M］.北京：電子工業(yè)大學(xué)出版社，2012：392－395.］

［8］Woon WT，Wan T.Performance evaluation of IEEE 802.15.4 adhoc wireless sensor networks：Simulation approach ［C］／／Proc of IEEE International Conference on Systems，Man and Cybemetics.Tainan，Taiwan：IEEE，2011：1443－1448.

［9］Du X，Lin F.Improving sensor network performance by deploying mobile sensors［C］／／In Proc of 24th IEEE International on Performance，Computing，and Communications.Phoenix，Arizona：IEEE，2009：67－71.

［10］XU Peicheng，HU Guorong.Improved ZigBee network routing algorithm ［J］.Computer Engineering and Design，2013，34 （9）：3019－3024 （in Chinese）. ［徐沛成，胡國榮.改進(jìn)的ZigBee網(wǎng)絡(luò)路由算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（9）：3019－3024.］