史新峰，王宜懷，顧會光

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

0 引 言

路燈的相對物理位置不同于大多數(shù)學(xué)者所研究的傳感網(wǎng)絡(luò)，那些節(jié)點一般呈面式分布，而路燈具有獨有的單條、雙條、三條等平行式的物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并且要求高穩(wěn)定性、協(xié)議低實現(xiàn)難度和后期可維護性?，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ù)洌O(shè)計一種簡單高效穩(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ù)馬路的寬度不同也有一條、三條和四條等，這里我們以最常見的兩條為例進行研究，在實際應(yīng)用中，可以根據(jù)具體情況稍做修改和擴展就可以適應(yīng)單條或多條路燈的情況。我們把協(xié)調(diào)器 （也常被稱作Sink節(jié)點）放置在路燈的一側(cè)的前端或是后端，為了表達(dá)方便，把協(xié)調(diào)器放置在前端，每條路配備一個協(xié)調(diào)器。并且給每盞路燈依次編號。

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

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

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

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

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

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

圖2 MAC地址

2 三鏈路由算法

2.1 算法原理

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

2.1.1 一級鏈

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

圖3 一級鏈

2.1.2 二級鏈

根據(jù)單燈節(jié)點的有效發(fā)送半徑r和路燈間的距離d可以確定二級鏈。二級鏈的最小單位不是單個節(jié)點，而是以一定數(shù)量為n的節(jié)點組為一個單位，各個單位間又發(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 所示。其實二級鏈號＜Y＞就是對應(yīng)那一組離協(xié)調(diào)器最近的那個單燈節(jié)點的MAC 地址。也正是這些節(jié)點間的相互通信形成了二級鏈。

圖4 二級鏈

2.1.3 三級鏈

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

圖5 三級鏈

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

2.2 算法實現(xiàn)

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

2.2.1 單播

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

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

2.2.2 廣播

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

圖7 上行和下行對比

在對單燈節(jié)點通信的過程中，其實并沒有使用到三級鏈，不過對于路燈的控制更多的是廣播數(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é)點接收到了數(shù)據(jù)，停止轉(zhuǎn)發(fā)。具體的流程如圖8所示。

圖8 廣播流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

雖然，本算法有諸多優(yōu)點，但是依然存在不足，比如說需要人為手動的方式燒寫不同的物理地址，我們曾嘗試，通過能量檢測的方式來自動確定自己的物理地址，但是由于不同的節(jié)點發(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］.計算機系統(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è)計實現(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)原理與實踐 ［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）. ［徐沛成，胡國榮.改進的ZigBee網(wǎng)絡(luò)路由算法 ［J］.計算機工程與設(shè)計，2013，34（9）：3019－3024.］