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

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果忽略掉節(jié)點(diǎn)因?yàn)橥ㄐ沛溌访β岛湍康墓?jié)點(diǎn)忙碌 而等待的時間，假設(shè)一個節(jié)點(diǎn)只發(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é)點(diǎn)所經(jīng)歷的最小跳數(shù)為 h(Ni)，因此整個電子秤無線自組網(wǎng)的所有節(jié)點(diǎn)數(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算法的實(shí)現(xiàn)與改進(jìn)

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

2.1流量均衡原理

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

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

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

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

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

…，Nkn，它們的流量分別為)，t(Nk2 )，t (Nk3 )，???， t(N、），在每個節(jié)點(diǎn)都發(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改進(jìn)后的局部流量均衡策略

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

局部流量均衡：一棵數(shù)據(jù)匯集樹的第k層節(jié)點(diǎn)的集合 記作 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算法進(jìn)行改進(jìn)：對節(jié)點(diǎn)x進(jìn)行流量 均衡調(diào)整時，如果節(jié)點(diǎn)x的父節(jié)點(diǎn)為u，存在v€F(x)，則 有 Max= (t(u) - t(x) ) X (t(v)—t(x))，使 Max〉t(u) X t(v)，那么x將父節(jié)點(diǎn)重置為v。

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

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

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

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

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

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

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

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

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

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

2.4路由算法過程舉例

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

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

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

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

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

3.仿真實(shí)驗(yàn)

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

4.結(jié)語

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