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

引言

本文提出了一種用于自動化質(zhì)監(jiān)的電子秤無線自組 網(wǎng)的路由算法，通過為電子秤嵌入質(zhì)監(jiān)模塊來自動收集電 子秤示數(shù)的信息，質(zhì)監(jiān)模塊之間采用ZgBee組建無線自 組網(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ù)，當(dāng)質(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表示，為節(jié)點下 標(biāo)，對于V^eV’N內(nèi)存容量為M,有限的內(nèi)存容量決定 了凡能夠存儲的鄰居節(jié)點數(shù)目有限。

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

④對于V^eV，如果3 eiGE (i是直接通信邊），且 ei的一個端點是N，那么a的另一端點稱為節(jié)點凡的鄰 居節(jié)點，節(jié)點凡所有鄰居節(jié)點的總個數(shù)稱作節(jié)點凡的 度，記作d(N,)。

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

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

⑦設(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ā)送周期，記作丁。

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

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

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

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

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

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

D(N;) = Tr(Ni)+Ts(Ni)+Tt(Ni) (N, G V)

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

Ts(N;) = K (n, G V)

丁t(N0是數(shù)據(jù)包從節(jié)點N;出發(fā)后途經(jīng)若干中間節(jié)點 發(fā)送到匯集節(jié)點所用的時延，丁t(ND的計算如下所示： Tt(N;) = 2 X h(N;) X Ts(Nt) (N; G V)

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

Dtotal = 2 {Tr(Ni)+Ts(Ni)+Tt(Ni)} i=l

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

Htotal = ^h(N)，VN; G V，

i=l

Dtotai = {Tr(N;) +-B }+iKx Htotai X 2

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

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

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

2.1流量均衡原理

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

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

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

流量均衡原理：對于一棵數(shù)據(jù)匯集樹，假設(shè)其深度為

H，觀察這棵數(shù)據(jù)匯集樹的第k層（k，第（k+1)層到 第H層共有N個節(jié)點，在_個數(shù)據(jù)匯集周期T內(nèi)，這N 個節(jié)點產(chǎn)生的數(shù)據(jù)包必然全部要通過第k層向上轉(zhuǎn)發(fā)。 假設(shè)第k層_共有n個節(jié)點，節(jié)點分別為N&，Nk2，Nk3，

…，Nkn，它們的流量分別為)，t(Nk2 )，t (Nk3 )，???， t(N、），在每個節(jié)點都發(fā)送并只發(fā)送一次數(shù)據(jù)包的前提下，

有 t(Nk1 )+t(Nk2 ) + t(Nk3 )十…+ t(Nkn ) = M，為了達(dá)到流 量均衡，即讓()，t(Nk2 )，t(Nk )，…，t(Nkn )之間的差值

最小，根據(jù)乘法原理，需要確保nt(N)，（1 < i < n)最大。

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

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

局部流量均衡：一棵數(shù)據(jù)匯集樹的第k層節(jié)點的集合 記作 S(k)，N，Nk2，Nk3，…，Nkn e S(k)，如果 t(Nk1 ) x t(Nk2 )X t(Nk3 ) X…X t(N、)取得條件最大值，對于 V t(Nk, ),t(Nk)G S(k)，當(dāng) t(%)十 t(Nk;)不變時，必定有 t(Nk, )Xt(Nk)取得最大值。

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

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

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

①所有節(jié)點初始化，對于節(jié)點Nt，設(shè)置d(Nt) =0， L(Nt) = / ,h(Nt) ,F(Nt) = /，（Nt) = 1。

②數(shù)據(jù)匯集節(jié)點發(fā)出層次發(fā)現(xiàn)廣播命令，該命令包 含節(jié)點層次計數(shù)，記作h(e)，節(jié)點N收到該命令后，比較 h(re) + 1和h(Nt)的大小，如果Mre’ + KhCND，則令 ^凡）=從代）十1，然后將命令中的h(re)重置為h(Nt)、 地址重置為addr(i)，并廣播該命令，否則丟棄該命令，因 此，所有節(jié)點可以得知節(jié)點的層次信息。

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

④如果節(jié)點凡，!1(凡）=1，則N是數(shù)據(jù)匯集節(jié)點 Nsmk

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

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

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

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

2.4路由算法過程舉例

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

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

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

從圖3中可以看出，號節(jié)點的流量明顯多于同層節(jié) 點，因此需要對以2號為根的子樹進行調(diào)整，即從葉子節(jié) 點開始尋找是否有候選父節(jié)點，可見15號節(jié)點有調(diào)整的 可能，號和8號節(jié)點的流量之積為1X4 = 4，調(diào)整后為

(1 + 1) X (4一1)=6>4，因此可以進行調(diào)整，將7號節(jié)點 作為15號節(jié)點的父節(jié)點，同時更新7號節(jié)點流量信息。 對于7號節(jié)點，號節(jié)點和3號節(jié)點的流量之積為10X1 = 10，調(diào)整后為（10 — 1)X (1十1) = 18>10，因此將3號節(jié) 點作為7號節(jié)點的父節(jié)點，對于14號節(jié)點，由于15號節(jié) 點的父節(jié)點變?yōu)榱?/span> 7號節(jié)點，號節(jié)點的流量為3，號節(jié) 點和7號節(jié)點流量之積為4X3 = 12，若調(diào)整14號節(jié)點之 后，流星積為（4一2) X (3十2) = 10，因此不需要調(diào)整14號 節(jié)點。該方法使同層節(jié)點流量更加均衡，減少出現(xiàn)部分節(jié) 點流量過高影響網(wǎng)絡(luò)整體性能的情況。調(diào)整后的數(shù)據(jù)匯 集樹如圖4所示.

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ò)拓?fù)?/span> 結(jié)構(gòu)，呈現(xiàn)仿真結(jié)果。將一個數(shù)據(jù)匯集節(jié)點Smk和若干 個普通節(jié)點隨機均勻分布在區(qū)域內(nèi)，網(wǎng)絡(luò)結(jié)構(gòu)略——編者 注，算法的仿真結(jié)果略 編者注。

4.結(jié)語

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