提出了一種基于ZlgBee無線自組網絡用于自動化質監的電子秤路由算法。以DGT-CC為藍本，使用更加完善的 局部流量均衡策略來規避擁塞，并為無線自組網構建流量均衡的數據匯集樹路由。通過本路由算法可以高效、快速地收 集電子秤數據信息，實現高效方便的質監。

引言

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

1.電子秤無線自組網

1.1電子秤無線自組網模型定義

電子秤無線自組網以電子秤為通信節點，建立無線局 域網來收集由電磁砝碼產生的示數，當質監完成后，各個 節點將數據發送至數據匯集節點。電子秤無線自組網網 絡模型定義如下：

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

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

③每個節點凡都有唯一的編號，節點凡的編號記 作addr(0，為0?9 999之間的整數，可以參與排序，是節 點參與ZgBe e組網時協調器分配的網絡地址。

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

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

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

⑦設定每個電子秤無線自組網節點都發送而且只發送一次數據給數據匯集節點Nsink，從第一個節點開始發送 數據起，到所有節點數據發送完畢的這段時間稱為電子秤 無線自組網的一個數據發送周期，記作丁。

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

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

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

1.2電子秤無線自組網模型性能分析

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

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

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

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

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

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

如果忽略掉節點因為通信鏈路忙碌和目的節點忙碌 而等待的時間，假設一個節點只發送一次數據包，在一個 數據發送周期丁內，整個電子秤無線自組網絡的全部時 延Dtotal如下所示：

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

VN G V，< i< n 將數據傳送至數據匯集節點所經歷的最小跳數為 h(Ni)，因此整個電子秤無線自組網的所有節點數據匯集 路徑就是數據匯集路徑之和，簡稱路徑和，記作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 由此發現，網絡總時延與路徑和存在正相關，網絡總 操作數也隨著路徑和的增加而增加，因此可以得出結論： 網絡性能與路徑和H totai存在正相關，可以通過降低網絡 路徑和來提高網絡性能。

2 .DGT-CC算法的實現與改進

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

2.1流量均衡原理

根據流量均衡原理，DG丁-CC算法平衡最短路徑數據 匯集樹中每一層節點間的流量之差，使得整個網絡性能達 到最優。

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

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

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

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

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

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

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

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

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

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

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

2.3完善后的DGT-CC算法實現

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

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

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

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

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

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

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

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

⑥改進的流量均衡算法步驟略 編者注，可以避 免流量熱點問題，使網絡性能達到優化。

2.4路由算法過程舉例

選取若干ZigBee全功能節點、節點位置及鄰居信息， 隨機選取任意一個節點作為ZgBee協調器構建網絡，如 圖1所示，圖中虛線連接表示節點間的鄰居關系.圖1節點鄰居關系及地址編號圖

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

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

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

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

3.仿真實驗

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

4.結語

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