Flooding算法改進(jìn)及其應(yīng)用

唐堅剛+潘銳

摘 要：針對泛洪式路由算法（Flooding）中路由信息內(nèi)爆的缺點，提出一種基于Flooding的改進(jìn)路由算法，該算法根據(jù)所有路燈采用靜態(tài)地址，并通過序列號對協(xié)調(diào)器所發(fā)的命令幀進(jìn)行標(biāo)記。子節(jié)點根據(jù)序列號對數(shù)據(jù)幀進(jìn)行過濾。最后，結(jié)合智能路燈控制系統(tǒng)和改進(jìn)的Flooding算法進(jìn)行路由實驗。

關(guān)鍵詞關(guān)鍵詞：Flooding算法；靜態(tài)地址；路燈控制系統(tǒng)

DOIDOI：10.11907/rjdk.161531

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A ：1672-7800（2016）008-0006-04

0 引言

隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展與人們對共享資源需求的不斷增長，網(wǎng)格技術(shù)已成為分布式計算領(lǐng)域近年來研究的一個熱點[1]。無線傳感器網(wǎng)絡(luò)是集信息采集、信息處理、信息傳輸于一體的綜合系統(tǒng)[2]。Flooding路由協(xié)議[3]是傳統(tǒng)網(wǎng)絡(luò)中最為經(jīng)典和簡單的路由協(xié)議，是基于泛洪機(jī)制的路由協(xié)議，可以應(yīng)用到無線傳感器網(wǎng)絡(luò)中。該協(xié)議不要求維護(hù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和相關(guān)路由計算，僅要求傳感器網(wǎng)絡(luò)節(jié)點在接收到信息后以廣播的方式向鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，鄰居節(jié)點重復(fù)執(zhí)行上述過程（轉(zhuǎn)發(fā)時除去剛剛發(fā)送給它們的節(jié)點），直到數(shù)據(jù)包到達(dá)目的地或者該數(shù)據(jù)包的生命周期結(jié)束。

1 國內(nèi)外研究現(xiàn)狀

路由協(xié)議是無線傳感器網(wǎng)絡(luò)的重要技術(shù)[4]，目前國內(nèi)外學(xué)者作了相關(guān)研究。在路由表中，通過增加路由方向與資源狀態(tài)信息兩者之間的關(guān)聯(lián)度，有效增加資源請求被轉(zhuǎn)發(fā)到可滿足節(jié)點的概率[5]；根據(jù)Power-Law規(guī)律，總選擇具有最大聚集度的節(jié)點進(jìn)行轉(zhuǎn)發(fā)[6]；先根據(jù)一定的標(biāo)準(zhǔn)判斷兩個查詢請求的相似性，然后將最新的查詢請求轉(zhuǎn)發(fā)給最近滿足相似查詢的鄰居節(jié)點[7]。

2 Flooding路由算法

在無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)包的生命周期中，一般預(yù)先設(shè)定該數(shù)據(jù)包所轉(zhuǎn)發(fā)的最大跳轉(zhuǎn)數(shù)。假設(shè)源節(jié)點A需要將數(shù)據(jù)包p發(fā)送至匯聚節(jié)點D，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，節(jié)點之間的聯(lián)機(jī)表示兩者在通信范圍內(nèi)可通信。節(jié)點A首先將p的副本進(jìn)行廣播，則其鄰居節(jié)點B、E、G接收到p副本之后，直接將p副本通過廣播的形式轉(zhuǎn)發(fā)（除去節(jié)點A），以此類推，直到p達(dá)到匯聚節(jié)點D或TTL。以節(jié)點B、C為例，如圖2所示，B將p副本轉(zhuǎn)發(fā)至節(jié)點C、E、F，C將p副本轉(zhuǎn)發(fā)至節(jié)點E、F、D。

3 改進(jìn)后的Flooding路由算法

針對Cluster-Tree算法和Flooding算法的缺點，給出了一種基于Flooding算法的改進(jìn)路由算法。該算法通過修改網(wǎng)絡(luò)層的幀結(jié)構(gòu)，在末尾加入序列號，標(biāo)記中心協(xié)調(diào)器每次發(fā)送的數(shù)據(jù)幀。中心協(xié)調(diào)器在每次發(fā)幀時生成序列號。當(dāng)路由節(jié)點收到一個數(shù)據(jù)幀時，提取幀中的序列號，將其跟之前剛收到的序列號進(jìn)行校驗，若相同，則不進(jìn)行任何操作，反之，就會處理接收的數(shù)據(jù)幀，執(zhí)行相關(guān)命令，記錄數(shù)據(jù)幀并進(jìn)行廣播。算法流程如圖3所示。

4 改進(jìn)后的Flooding路由算法實現(xiàn)

4.1 平臺簡介

為了有效提高網(wǎng)絡(luò)的傳輸效率，中心協(xié)調(diào)器和路由器以MC13213芯片安裝在路燈上，軟件部分采用基于MsstatePAN的協(xié)議棧，在網(wǎng)絡(luò)層部分，不采用Cluster-Tree的地址分配方法，使用改進(jìn)的Flooding算法進(jìn)行測試。

4.2 數(shù)據(jù)幀結(jié)構(gòu)設(shè)計

在重新定義幀結(jié)構(gòu)時，由于考慮到路燈的實際使用情況，結(jié)合該算法，總共設(shè)定了60字節(jié)的幀結(jié)構(gòu)，目前只使用了33個字節(jié)，剩余27個字節(jié)作保留，數(shù)據(jù)幀結(jié)構(gòu)定義如圖4所示。在設(shè)計幀時，網(wǎng)絡(luò)ID是識別該網(wǎng)絡(luò)的唯一標(biāo)識，幀總共分為兩種類型，命令幀和確認(rèn)幀，命令幀是從協(xié)調(diào)器發(fā)出的，確認(rèn)幀是從節(jié)點發(fā)出的，協(xié)調(diào)器需要處理的幀如圖5所示。

（1）目的地址。標(biāo)識接收開關(guān)燈等命令的最終節(jié)點，而不一定是指路由結(jié)點。如果不是0xFF，則表示控制單盞燈，如果是0xFF，則表示控制多盞燈，此時“開燈間隔參數(shù)”有效。

（2）開燈間隔。由協(xié)調(diào)器進(jìn)行處理，間隔為1表示開二分之一的燈，2表示開三分之一的燈，表示單側(cè)燈的間隔狀況。這是為某些天氣情況下，需要開間隔燈而設(shè)計的。

（3）左右標(biāo)識。表示路兩側(cè)哪一側(cè)的燈，0x01表示“左”側(cè)，0x02表示“右”側(cè)，0x03表示所有的側(cè)，“左右”由人為指定包含在幀里面。只有當(dāng)“目的地址”為0xFF時，“開燈間隔”以及“左右標(biāo)識”參數(shù)才有效。這3個參數(shù)由協(xié)調(diào)器進(jìn)行處理。

（4）序列號。由協(xié)調(diào)器生成，大小為2個字節(jié)，當(dāng)值達(dá)到0xFFFF時，系統(tǒng)自動清零，目的是對協(xié)調(diào)器發(fā)出的命令幀進(jìn)行標(biāo)記。

4.3 命令幀及確認(rèn)幀的演示及說明

如圖6所示，總共八盞燈被依次編號，每盞燈都被看作是一個節(jié)點。在所有節(jié)點正常運作情況下，使用協(xié)調(diào)器通過串口發(fā)出命令，命令7號燈開燈，并且運用改進(jìn)的Flooding路由算法，圖6展示的是其中一種可能路徑。

從圖6看出，黑色實心圓是協(xié)調(diào)器，空心圓是子節(jié)點，當(dāng)協(xié)調(diào)器發(fā)出第一條命令時，給命令幀標(biāo)序列號1，節(jié)點1和節(jié)點2收到序列號為1的命令幀，然后節(jié)點1和節(jié)點2對這命令幀進(jìn)行處理，并廣播出去。如果節(jié)點3先接收到節(jié)點1的命令幀進(jìn)行處理，然后又收到節(jié)點2的命令幀，但是判斷序列號相同且都為1，則不對第二次收到的幀進(jìn)行處理，其它節(jié)點跟節(jié)點3相同。最終節(jié)點7收到命令幀，判斷后處理，燈亮。

假設(shè)出現(xiàn)節(jié)點損壞，且中心協(xié)調(diào)器需要對此節(jié)點后面的節(jié)點進(jìn)行操作，則其它節(jié)點在將數(shù)據(jù)幀傳送給此節(jié)點時，此節(jié)點不能對其進(jìn)行處理，但是基于此算法的優(yōu)點，數(shù)據(jù)幀可以通過此節(jié)點的左右鄰節(jié)點或者對面的節(jié)點進(jìn)行廣播，從而數(shù)據(jù)幀能夠被后面的節(jié)點接收。

經(jīng)過上述過程，節(jié)點7打開燈后，需要返回一個確認(rèn)幀給協(xié)調(diào)器，將原來的命令幀改為確認(rèn)幀。節(jié)點5和節(jié)點8判斷這是確認(rèn)幀就不比較剛才的序列號，確認(rèn)幀經(jīng)過不斷轉(zhuǎn)發(fā)，最終協(xié)調(diào)器收到此確認(rèn)幀。具體過程如圖7所示。

5 應(yīng)用實例介紹

通過上文對Flooding算法的分析及改進(jìn)可知，理論上，改進(jìn)后的算法具備實現(xiàn)的可能。結(jié)合ZigBee技術(shù)設(shè)計路燈硬件系統(tǒng)，并制作節(jié)點模型進(jìn)行實驗，將改進(jìn)的Flooding算法和原始算法的執(zhí)行效果進(jìn)行對比。

5.1 路燈控制系統(tǒng)硬件設(shè)計

根據(jù)照明控制器所實現(xiàn)的主要功能，硬件部分如圖8所示，主要包括ZigBee模塊、功率檢測模塊、電源管理模塊、超聲波模塊、光線檢測模塊繼電器模塊以及微處理器（MCU）模塊等。

5.2 軟件開發(fā)環(huán)境

在設(shè)計程序時，選擇Windows XP操作系統(tǒng)、CodeWarrior 軟件開發(fā)環(huán)境以及硬件仿真器 USB Multilink 連接工具來完成程序的編寫、調(diào)試。CodeWarrior 軟件開發(fā)工具支持飛思卡爾處理器芯片的軟件編程、連接和源程序調(diào)試[8]。使用CodeWarrior軟件編寫代碼時，使用C語言進(jìn)行編寫，編寫完成后通過 USB Multilink 連接工具與硬件平臺連接[9]，并將程序下載到芯片中。

5.3 路燈模型展示

為了測試該新型智能照明控制器的感應(yīng)性能，結(jié)合路燈控制特點，搭建一個由6個節(jié)點組成的智能照明模擬測試環(huán)境，測試環(huán)境由PC機(jī)控制界面以及配置照明控制器節(jié)點的組網(wǎng)模型組成。測試的主要項目是穩(wěn)定性、智能響應(yīng)等，通過戶外模擬進(jìn)行實際性能測試。制作路燈模型后進(jìn)行實驗，如圖9所示。

由于幀結(jié)構(gòu)設(shè)計得比較完整，通過串口向節(jié)點發(fā)送不同的幀，可以實現(xiàn)不同模式的亮燈模式，使用一個上面裝有6個節(jié)點的木板模型來模擬，有單盞點亮、間隔開關(guān)燈和全燈點亮等模式，全燈點亮如圖10所示。

6 實驗結(jié)果及分析

6.1 實驗場景設(shè)置

實驗場景設(shè)置如下：①節(jié)點個數(shù)：中心協(xié)調(diào)器1個，子節(jié)點數(shù)目6個；②節(jié)點間傳送數(shù)據(jù)距離為30m；③實驗規(guī)則：路燈以左邊為奇數(shù)，右邊為偶數(shù)依次排列；④實驗次數(shù)：同時重復(fù)實驗500次；⑤針對Cluster-Tree算法設(shè)置：CM=4，RM=4，LM=3。

6.2 無故障節(jié)點實驗結(jié)果

假設(shè)所有節(jié)點為正常，沒有損壞，分別對改進(jìn)Flooding和Cluster-Tree算法進(jìn)行開全燈實驗，通過燈是否全亮或者主節(jié)點接收到的數(shù)據(jù)包查看是否有丟包情況。從實驗結(jié)果中可以看出，在所有節(jié)點正常的情況下，協(xié)調(diào)器命令所有節(jié)點開燈，改進(jìn)的Flooding算法和Cluster-Tree算法路由轉(zhuǎn)發(fā)能力相當(dāng)，其中有幾次節(jié)點轉(zhuǎn)發(fā)不成功。實驗結(jié)果如圖11所示。

6.3 節(jié)點故障實驗結(jié)果

假設(shè)其中一個節(jié)點損壞，則分別對改進(jìn)Flooding和Cluster-Tree算法進(jìn)行開全燈實驗，從實驗結(jié)果中可以看出，在一個節(jié)點損壞的情況下，協(xié)調(diào)器命令所有節(jié)點開燈。改進(jìn)的Flooding算法明顯比Cluster-Tree算法路由轉(zhuǎn)發(fā)能力強，開燈成功率高、丟包率低。

對于不能使所有燈全開的情況，多次發(fā)幀仍然可以使沒有亮的燈開燈。通過多次實驗發(fā)現(xiàn)可能由以下原因引起：①發(fā)幀過于頻繁；②節(jié)點之間相互干擾。實驗結(jié)果如圖12所示。

7 結(jié)語

改進(jìn)后的Flooding算法實現(xiàn)方法淺顯易懂，繼承了原來Flooding的優(yōu)點，即每個節(jié)點只需將接收到的數(shù)據(jù)包進(jìn)行判斷，再進(jìn)行廣播，而無需查找路由表，選擇下一跳節(jié)點的計算。并且，其無需特殊的算法來保持網(wǎng)絡(luò)拓?fù)湫畔⒌母乱约靶侣酚傻陌l(fā)現(xiàn)，而且避免了原來Flooding信息內(nèi)爆、部分重迭和網(wǎng)絡(luò)資源利用不合理的缺點。

參考文獻(xiàn)：

[1] 張秋余，喬贊，袁占亭.基于偏好和M-Flooding的網(wǎng)格資源發(fā)現(xiàn)[J].計算機(jī)工程，2010，36（14）：40-45.

[2] I F AKYILDIZ，W SU，Y SANKARASUBRAMANIAM.A Survey on sensor networks[J].IEEE Commianications Magazine，2002，40（8）：102-114.

[3] 殷波.無限傳感網(wǎng)絡(luò)路由算法研究[D].武漢：華中科技大學(xué)，2006.

[4] 郭文靜.無限傳感器網(wǎng)絡(luò)生命期優(yōu)化路由協(xié)議的研究[D].上海：華東師范大學(xué)，2013.

[5] 周從華，劉志鋒.具有過去時態(tài)算子的計算樹邏輯模型檢測[J].計算機(jī)工程，2007，33（22）：98-100.

[6] 李健，唐文忠，宋長福.角色訪問控制技術(shù)在管理信息系統(tǒng)中的應(yīng)用[J].北京航空航天大學(xué)報，2003，29（6）：534-538.

[7] LI XIAOOU，MEDINA J M，CHAPA S V.Applying petri nets in active database systems[J].IEEE Transactions on Systems，Man and Cybernetics，2007，37（4）：482-493.

[8] 王江峰.基于ZigBee無限傳感網(wǎng)絡(luò)的實現(xiàn)[D].濟(jì)南：濟(jì)南大學(xué)，2010.

[9] 位元文化.精通 PalmOS 程序設(shè)計：Codewarrior 入門教程[M].北京：清華大學(xué)出版社，2001.

（責(zé)任編輯：孫 娟）