用于自動化質(zhì)監(jiān)的電子秤無線自組網(wǎng)路由算法設(shè)計※

張韋霆，馬維華，王贊森

(南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，南京 210016)

?

用于自動化質(zhì)監(jiān)的電子秤無線自組網(wǎng)路由算法設(shè)計※

張韋霆，馬維華，王贊森

(南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，南京 210016)

摘要:提出了一種基于ZigBee無線自組網(wǎng)絡(luò)用于自動化質(zhì)監(jiān)的電子秤路由算法。以DGT-CC為藍本，使用更加完善的局部流量均衡策略來規(guī)避擁塞，并為無線自組網(wǎng)構(gòu)建流量均衡的數(shù)據(jù)匯集樹路由。通過本路由算法可以高效、快速地收集電子秤數(shù)據(jù)信息，實現(xiàn)高效方便的質(zhì)監(jiān)。

關(guān)鍵詞:自動化質(zhì)監(jiān)；無線自組網(wǎng)；DGT-CC算法；路由

引言

本文提出了一種用于自動化質(zhì)監(jiān)的電子秤無線自組網(wǎng)的路由算法，通過為電子秤嵌入質(zhì)監(jiān)模塊來自動收集電子秤示數(shù)的信息，質(zhì)監(jiān)模塊之間采用ZigBee組建無線自組網(wǎng)進行數(shù)據(jù)的匯集與共享，而自組網(wǎng)建立后可以通過WiFi將數(shù)據(jù)發(fā)送至智能手機終端，從而方便監(jiān)測電子秤示數(shù)是否與電磁砝碼重量相符，即是否存在質(zhì)量問題。

1電子秤無線自組網(wǎng)

1.1電子秤無線自組網(wǎng)模型定義

電子秤無線自組網(wǎng)以電子秤為通信節(jié)點，建立無線局域網(wǎng)來收集由電磁砝碼產(chǎn)生的示數(shù)，當質(zhì)監(jiān)完成后，各個節(jié)點將數(shù)據(jù)發(fā)送至數(shù)據(jù)匯集節(jié)點。電子秤無線自組網(wǎng)網(wǎng)絡(luò)模型定義如下：

① 電子秤無線自組網(wǎng)各節(jié)點隨機分布在二維平面內(nèi)(三維情況暫不予考慮)，且節(jié)點位置固定，軟硬件條件相同，所有電子秤節(jié)點構(gòu)成一個自組網(wǎng)集合，記作V，任意可以直接通信的兩個節(jié)點構(gòu)成一個節(jié)點對，這個節(jié)點對稱為電子秤無線自組網(wǎng)中的一條直接通信邊，所有直接通信邊的集合記作E。因此，整個電子秤無線自組網(wǎng)可表示成G=(V,E)。

② 電子秤無線自組網(wǎng)中節(jié)點用N表示，i為節(jié)點下標，對于?Ni∈V，N內(nèi)存容量為M，有限的內(nèi)存容量決定了Ni能夠存儲的鄰居節(jié)點數(shù)目有限。

③ 每個節(jié)點Ni都有唯一的編號，節(jié)點Ni的編號記作addr(i)，為0～9 999之間的整數(shù)，可以參與排序，是節(jié)點參與ZigBee組網(wǎng)時協(xié)調(diào)器分配的網(wǎng)絡(luò)地址。

④ 對于?Ni∈V，如果?ei∈E (ei是直接通信邊)，且ei的一個端點是Ni，那么ei的另一端點稱為節(jié)點Ni的鄰居節(jié)點，節(jié)點Ni所有鄰居節(jié)點的總個數(shù)稱作節(jié)點Ni的度，記作d(Ni)。

⑤ 電子秤無線自組網(wǎng)存在一個數(shù)據(jù)匯集節(jié)點Nsink，自組網(wǎng)中所有節(jié)點都將數(shù)據(jù)傳輸給匯集節(jié)點Nsink，節(jié)點Ni到節(jié)點Nsink經(jīng)歷的最短路徑(最小跳數(shù))記為h(Ni)，hNi(Nj)表示節(jié)點Ni的鄰居節(jié)點Ni到數(shù)據(jù)匯集節(jié)點Nsink的最短路徑。

⑥ 節(jié)點Ni的所有鄰居節(jié)點組成一個鄰居節(jié)點集合，記作L(Ni)。

⑦ 設(shè)定每個電子秤無線自組網(wǎng)節(jié)點都發(fā)送而且只發(fā)送一次數(shù)據(jù)給數(shù)據(jù)匯集節(jié)點Nsink，從第一個節(jié)點開始發(fā)送數(shù)據(jù)起，到所有節(jié)點數(shù)據(jù)發(fā)送完畢的這段時間稱為電子秤無線自組網(wǎng)的一個數(shù)據(jù)發(fā)送周期，記作T。

⑧ 電子秤無線自組網(wǎng)中的節(jié)點依附于電子秤設(shè)備，所以一般認為Ni能量無限(?Ni∈V)，并且在數(shù)據(jù)收集的這段時間內(nèi)，節(jié)點Ni是固定的，節(jié)點Ni的接收和發(fā)送隊列容量有限，即如果一段時間內(nèi)有多個節(jié)點向Ni發(fā)送數(shù)據(jù)包，數(shù)據(jù)包會有一定的丟失概率，將節(jié)點Ni數(shù)據(jù)處理能力(即單位時間接收和發(fā)送數(shù)據(jù)的速度)記為B。

⑨ 到數(shù)據(jù)匯集節(jié)點Nsink的最短路徑相同的節(jié)點的集合稱為同層節(jié)點，“層”用來衡量節(jié)點到數(shù)據(jù)匯集節(jié)點Nsink的最短路徑的長度，?Ni∈V，如果h(Ni=k)，那么稱Ni為第k層節(jié)點，同理，k層節(jié)點就是指所有到數(shù)據(jù)匯集節(jié)點Nsink的最短路徑為k的節(jié)點的集合。

⑩ 如果Nj∈L(Ni)且h(Nj)=h(Ni)-1，那么Nj就是Ni的一個候選父節(jié)點，Ni的所有候選父節(jié)點組成的集合記作F(Ni)，組網(wǎng)時Ni會按照流量均衡的原則選擇F(Ni)中的某個節(jié)點作為自己的父節(jié)點。如果Ni選擇Nj作為父節(jié)點，那么Ni被稱為Nj的子節(jié)點，任意節(jié)點(除Nsink)的父節(jié)點有且只有一個。

1.2電子秤無線自組網(wǎng)模型性能分析

時延和能耗是反映無線自組網(wǎng)性能的重要指標，在本系統(tǒng)中，各節(jié)點直接安裝在電子秤內(nèi)，節(jié)點能量依附于電子秤，因此可以認為無線自組網(wǎng)各節(jié)點能量是無限的，所以采用節(jié)點總操作數(shù)來衡量節(jié)點及網(wǎng)絡(luò)壽命。節(jié)點總操作數(shù)指一個數(shù)據(jù)發(fā)送周期T內(nèi)，節(jié)點Ni執(zhí)行的所有操作(包括接收數(shù)據(jù)包、發(fā)送數(shù)據(jù)包、解析指令、查找路由、數(shù)據(jù)聚合等)，所有操作總數(shù)稱為節(jié)點Ni的總操作數(shù)，記作OP(Ni)。

假設(shè)每次發(fā)送數(shù)據(jù)的大小為K，忽略數(shù)據(jù)在節(jié)點直接傳輸?shù)臅r間，將Ni發(fā)出的數(shù)據(jù)包到達數(shù)據(jù)匯集節(jié)點Nsink所用的時間作為節(jié)點Ni至Nsink的時延，記作D(Ni)，如下所示：

其中，Tr(Ni)是節(jié)點Ni路由發(fā)現(xiàn)，即尋找下一跳地址所用的時間；Ts(Ni)是節(jié)點發(fā)送時延，與數(shù)據(jù)包大小和節(jié)點單位時間發(fā)送和接收數(shù)據(jù)能力相關(guān)，Ts(Ni)的計算如下所示：

Tt(Ni)是數(shù)據(jù)包從節(jié)點Ni出發(fā)后途經(jīng)若干中間節(jié)點發(fā)送到匯集節(jié)點所用的時延，Tt(Ni)的計算如下所示：

如果忽略掉節(jié)點因為通信鏈路忙碌和目的節(jié)點忙碌而等待的時間，假設(shè)一個節(jié)點只發(fā)送一次數(shù)據(jù)包，在一個數(shù)據(jù)發(fā)送周期T內(nèi)，整個電子秤無線自組網(wǎng)絡(luò)的全部時延Dtotal如下所示：

?Ni∈V,1≤i≤n

將數(shù)據(jù)傳送至數(shù)據(jù)匯集節(jié)點所經(jīng)歷的最小跳數(shù)為h(Ni)，因此整個電子秤無線自組網(wǎng)的所有節(jié)點數(shù)據(jù)匯集路徑就是數(shù)據(jù)匯集路徑之和，簡稱路徑和，記作Htotal，因此Htotal和Dtotal如下所示：

?Ni∈V,1≤i≤n

由此發(fā)現(xiàn),網(wǎng)絡(luò)總時延與路徑和存在正相關(guān)，網(wǎng)絡(luò)總操作數(shù)也隨著路徑和的增加而增加，因此可以得出結(jié)論:網(wǎng)絡(luò)性能與路徑和Htotal存在正相關(guān)，可以通過降低網(wǎng)絡(luò)路徑和來提高網(wǎng)絡(luò)性能。

2DGT-CC算法的實現(xiàn)與改進

通過基于擁塞控制的無線傳感網(wǎng)絡(luò)數(shù)據(jù)匯集樹生成算法DGT-CC (Data Gather Tree based on Congestion Control)構(gòu)建路由樹，將與終端智能手機連接的節(jié)點設(shè)為Nsink，以Nsink為根建立一個最短數(shù)據(jù)路徑匯集樹，即每個節(jié)點到數(shù)據(jù)匯集節(jié)點的路徑都是最短的。設(shè)定Ni到Nsink的跳數(shù)為k，那么Ni總是從集合L中選擇父節(jié)點，L是所有到Nsink的跳數(shù)為(k-1)的節(jié)點組成的集合，所以Ni發(fā)送數(shù)據(jù)至數(shù)據(jù)匯集節(jié)點Nsink的下一跳地址就是Ni的父節(jié)點。

2.1流量均衡原理

根據(jù)流量均衡原理，DGT-CC算法平衡最短路徑數(shù)據(jù)匯集樹中每一層節(jié)點間的流量之差，使得整個網(wǎng)絡(luò)性能達到最優(yōu)。

流量定義：在無線網(wǎng)絡(luò)中某個節(jié)點的流量指一段時間中該節(jié)點發(fā)送或者轉(zhuǎn)發(fā)的數(shù)據(jù)包的總大小，電子秤無線自組網(wǎng)中節(jié)點Ni(Ni∈V)的流量定義為在一個數(shù)據(jù)發(fā)送周期T內(nèi)，Ni發(fā)送或轉(zhuǎn)發(fā)的數(shù)據(jù)包的總大小。由于在電子秤無線自組網(wǎng)中，各個節(jié)點向數(shù)據(jù)節(jié)點發(fā)送一次數(shù)據(jù)，在每個節(jié)點發(fā)送數(shù)據(jù)量相同的情況下，t(Ni)可以簡化為以Ni為根的子樹的節(jié)點數(shù)量總和。

流量熱點簡介：如果大量節(jié)點同時向某個特定的節(jié)點發(fā)送數(shù)據(jù)包，那么這個節(jié)點就可以稱為流量熱點。因此，越靠近Nsink，流量熱點越多，流量熱點緩存滿了之后，后續(xù)發(fā)送過來的數(shù)據(jù)包會被丟棄，這樣勢必會導(dǎo)致節(jié)點重復(fù)發(fā)送數(shù)據(jù)包，增大網(wǎng)絡(luò)時延。所以應(yīng)當平衡熱點的流量，防止部分熱點流量過大，影響網(wǎng)絡(luò)性能。

2.2改進后的局部流量均衡策略

DGT-CC算法中的流量均衡步驟直接來源于流量均衡原理，對于某個節(jié)點，總是選擇候選父節(jié)點中流量最小的作為父節(jié)點,這樣會導(dǎo)致單個節(jié)點的流量均衡，有待優(yōu)化，因此對局部流量均衡策略進行了改進。

局部流量均衡：一棵數(shù)據(jù)匯集樹的第k層節(jié)點的集合記作S(k),Nk1,Nk2,Nk3,…,Nkn∈S(k)，如果t(Nk1)×t(Nk2)×t(Nk3)×…×t(Nkn)取得條件最大值，對于?t(Nki),t(Nkj)∈S(k)，當t(Nki)+t(Nkj)不變時，必定有t(Nki)×t(Nkj)取得最大值。

因此對DGT-CC算法進行改進：對節(jié)點x進行流量均衡調(diào)整時，如果節(jié)點x的父節(jié)點為u，存在v∈F(x)，則有Max=(t(u)-t(x))×(t(v)-t(x))，使Max>t(u)×t(v)，那么x將父節(jié)點重置為v。

2.3完善后的DGT-CC算法實現(xiàn)

完善后的DGT-CC算法步驟如下：

①所有節(jié)點初始化，對于節(jié)點Ni，設(shè)置d(Ni)=0，L(Ni)=?，h(Ni)=∞，F(xiàn)(Ni)=?，t(Ni)=1。

② 數(shù)據(jù)匯集節(jié)點發(fā)出層次發(fā)現(xiàn)廣播命令，該命令包含節(jié)點層次計數(shù)，記作h(re)，節(jié)點Ni收到該命令后，比較h(re)+1和h(Ni)的大小，如果h(re)+1

③ 所有節(jié)點向周圍廣播發(fā)送hello消息，消息包含節(jié)點層次計數(shù)，收到的節(jié)點緩沖區(qū)中沒有源節(jié)點的信息，則將源節(jié)點的層次和地址信息存入到緩沖區(qū)，并且將d(Ni)自加1。當接收完所有hello消息后，丟棄層次計數(shù)大于h(Ni)的節(jié)點數(shù)據(jù)，其余的節(jié)點數(shù)據(jù)存入L(Ni)，將L(Ni)中節(jié)點層次計數(shù)比h(Ni)小1的節(jié)點存入F(Ni)，并向L(Ni)中的所有節(jié)點發(fā)送包含d(Ni)的消息，使每個節(jié)點都能得到鄰居節(jié)點的度。

④ 如果節(jié)點Ni，h(Ni)=1，則Ni是數(shù)據(jù)匯集節(jié)點Nsink的鄰居節(jié)點，則Ni可直接發(fā)送請求與Nsink建立父子關(guān)系；否則，Ni對F(Ni)按照節(jié)點度從小到大排序，節(jié)點度小的優(yōu)先被選擇，節(jié)點度相同時地址小的優(yōu)先被選擇，向該節(jié)點發(fā)送請求，得到應(yīng)答后建立父子關(guān)系，通過這一過程所有節(jié)點共同組成一棵最短路徑匯集樹。

⑤ 最短路徑匯集樹生成后，便進行流量統(tǒng)計，每個節(jié)點獲取流量信息，數(shù)據(jù)匯集節(jié)點Nsink廣播流量測試命令flow_test_packet，節(jié)點Ni收到該命令后會向父節(jié)點發(fā)送流量測試數(shù)據(jù)包data_test，具體步驟略——編者注。

經(jīng)過一個周期T，每個節(jié)點都知道了自身的流量值，并且通過廣播消息發(fā)送給所有鄰居節(jié)點。

⑥ 改進的流量均衡算法步驟略——編者注，可以避免流量熱點問題，使網(wǎng)絡(luò)性能達到優(yōu)化。

2.4路由算法過程舉例

選取若干ZigBee全功能節(jié)點、節(jié)點位置及鄰居信息，隨機選取任意一個節(jié)點作為ZigBee協(xié)調(diào)器構(gòu)建網(wǎng)絡(luò)，如圖1所示，圖中虛線連接表示節(jié)點間的鄰居關(guān)系。

圖1　節(jié)點鄰居關(guān)系及地址編號圖

根據(jù)網(wǎng)絡(luò)拓撲圖進行流量均衡的數(shù)據(jù)匯集樹生成，經(jīng)過算法步驟的①、②、③，所有節(jié)點都得了自身的層次h和節(jié)點度d，節(jié)點用addr(h,d)的方式表示節(jié)點信息，如圖 2所示。

圖2　節(jié)點層次與節(jié)點度示意圖

根據(jù)步驟④來構(gòu)建最短路徑數(shù)據(jù)匯集，以7號節(jié)點為例，在網(wǎng)絡(luò)拓撲圖中有兩個候選父節(jié)點，分別是2(1，5)和3(1，5)，根據(jù)條件，當父節(jié)點度數(shù)相同時選擇地址小的父節(jié)點，即2號節(jié)點，用帶箭頭的實線表示子節(jié)點向父節(jié)點數(shù)據(jù)匯集的路徑，如圖3所示。同時統(tǒng)計該節(jié)點的自身流量信息，在一輪數(shù)據(jù)匯集周期T后，所有節(jié)點都可以得到自己的流量信息。

圖3　最短路徑數(shù)據(jù)匯集樹

從圖3中可以看出，2號節(jié)點的流量明顯多于同層節(jié)點，因此需要對以2號為根的子樹進行調(diào)整，即從葉子節(jié)點開始尋找是否有候選父節(jié)點，可見15號節(jié)點有調(diào)整的可能，7號和8號節(jié)點的流量之積為1×4=4，調(diào)整后為(1+1)×(4-1)=6>4，因此可以進行調(diào)整，將7號節(jié)點作為15號節(jié)點的父節(jié)點，同時更新7號節(jié)點流量信息。對于7號節(jié)點，2號節(jié)點和3號節(jié)點的流量之積為10×1=10，調(diào)整后為(10-1)×(1+1)=18>10，因此將3號節(jié)點作為7號節(jié)點的父節(jié)點，對于14號節(jié)點，由于15號節(jié)點的父節(jié)點變?yōu)榱?號節(jié)點，7號節(jié)點的流量為3，6號節(jié)點和7號節(jié)點流量之積為4×3=12，若調(diào)整14號節(jié)點之后，流量積為(4-2)×(3+2)=10，因此不需要調(diào)整14號節(jié)點。該方法使同層節(jié)點流量更加均衡，減少出現(xiàn)部分節(jié)點流量過高影響網(wǎng)絡(luò)整體性能的情況。調(diào)整后的數(shù)據(jù)匯集樹如圖4所示。

圖4　調(diào)整后的數(shù)據(jù)匯集樹

3仿真實驗

仿真實驗采用OPNET實驗平臺，使用ZigBee節(jié)點組織無線自組網(wǎng)，選取任意一個節(jié)點作為數(shù)據(jù)匯集節(jié)點，其他節(jié)點將數(shù)據(jù)信息發(fā)送到數(shù)據(jù)匯集節(jié)點，仿真網(wǎng)絡(luò)時延以及網(wǎng)絡(luò)中的流量通過設(shè)置數(shù)據(jù)包、節(jié)點類型、網(wǎng)絡(luò)拓撲結(jié)構(gòu)，呈現(xiàn)仿真結(jié)果。將一個數(shù)據(jù)匯集節(jié)點Sink和若干個普通節(jié)點隨機均勻分布在區(qū)域內(nèi)，網(wǎng)絡(luò)結(jié)構(gòu)略——編者注，算法的仿真結(jié)果略——編者注。

結(jié)語

本文提出了一種基于自動化質(zhì)監(jiān)的電子秤無線自組網(wǎng)路由算法，將電子秤嵌入質(zhì)監(jiān)模塊，質(zhì)監(jiān)人員通過帶有WiFi的手機就可以實現(xiàn)電子秤稱重示數(shù)的收集與檢驗，而本路由算法可以幫助質(zhì)監(jiān)人員高效地進行檢查，防止局部流量過大導(dǎo)致網(wǎng)絡(luò)性能受到影響。

參考文獻

[1] 石為人,唐云建,王燕霞.基于擁塞控制的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)匯集樹生成算法[J] .自動化學(xué)報,2010(6).

[2] 王贊森,馬維華.手機WiFi熱點的電子秤自動質(zhì)監(jiān)系統(tǒng)設(shè)計[J] .單片機與嵌入式系統(tǒng)應(yīng)用,2014(4).

[3] 梁平原,陳炳權(quán),譚子尤.無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集關(guān)鍵技術(shù)及研究進展[J] .吉首大學(xué)學(xué)報:自然科學(xué)版,2011(1).

[4] 費曉飛,胡捍英.無線傳感器網(wǎng)鄰居發(fā)現(xiàn)算法研究[J] .微計算機信息,2009(4).

張韋霆、王贊森(碩士研究生)，馬維華(教授)：研究方向為嵌入式系統(tǒng)應(yīng)用。

Wireless Ad Hoc Networks Routing Algorithm of Electronic Scale for

Automatic Quality Supervision※

Zhang Weiting,Ma Weihua,Wang Zansen

(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Abstract：A wireless Ad Hoc networks routing algorithm based on ZigBee of electronic scale for automatic quality supervision is proposed.Based on DGT-CC algorithm,a more perfect local traffic equilibrium strategy is used to avoid congestion,and a traffic balanced data collection tree routing is constructed.The electronic scale data information can be collected efficiently and quickly using the routing algorithm,and the quality supervision can be achieved easily.

Key words:automatic quality supervision;Ad Hoc network;DGT-CC algorithm;route

收稿日期：(責(zé)任編輯：薛士然2015-07-27)

中圖分類號:TP301.6

文獻標識碼:A