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

引言

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

1.電子秤無(wú)線(xiàn)自組網(wǎng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

VN G V，< i< n 將數據傳送至數據匯集節點(diǎn)所經(jīng)歷的最小跳數為 h(Ni)，因此整個(gè)電子秤無(wú)線(xiàn)自組網(wǎng)的所有節點(diǎn)數據匯集 路徑就是數據匯集路徑之和，簡(jiǎn)稱(chēng)路徑和，記作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ā)現，網(wǎng)絡(luò )總時(shí)延與路徑和存在正相關(guān)，網(wǎng)絡(luò )總 操作數也隨著(zhù)路徑和的增加而增加，因此可以得出結論： 網(wǎng)絡(luò )性能與路徑和H totai存在正相關(guān)，可以通過(guò)降低網(wǎng)絡(luò ) 路徑和來(lái)提高網(wǎng)絡(luò )性能。

2 .DGT-CC算法的實(shí)現與改進(jìn)

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

2.1流量均衡原理

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

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

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

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

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

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

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

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

2.2改進(jìn)后的局部流量均衡策略

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

局部流量均衡：一棵數據匯集樹(shù)的第k層節點(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)，當 t(%)十 t(Nk;)不變時(shí)，必定有 t(Nk, )Xt(Nk)取得最大值。

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

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

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

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

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

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

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

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

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

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

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

2.4路由算法過(guò)程舉例

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

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

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

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

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

3.仿真實(shí)驗

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

4.結語(yǔ)

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