基于道路網絡的LED 路燈聚類組網算法的研究*

孫同陳 李 峰

（江蘇大學計算機科學與通信工程學院 鎮江 212013）

1 引言

匯聚節點在ZigBee 無線傳感網絡中起著重要作用，是無線傳感網絡的集群中心。選擇合適的位置部署匯聚節點不僅可以提高底層mesh 無線組網的可靠性，同時也提高了無線傳輸速度［1］。由于匯聚節點部署在集中控制器內部，對于匯聚節點的選址實際上也是對集中控制器選址。

目前，國內外對于路燈集中控制器的選址研究較少，現有的選址方案主要分為三種：基于能耗的選址方式［2］，基于壽命的選址方式［3］，基于移動匯聚選址的方式［4］。大都是圍繞如何降低能耗實現各傳感節點能耗均衡出發，在實際項目中，路燈匯聚節點部署在集中控制器內部，由集中控制器供電，不需要考慮節點能耗的問題。文獻［5］中，提出了一種基于綜合度量聚類的方法實現子網劃分。該方法綜合考慮了環境對路燈底層子網劃分的影響，結合k-mediods 算法進行聚類分析，對匯聚節點的選擇有一定參考依據，但是k-mediods 算法適用于球狀簇數據，道路網絡情況復雜，缺乏對路燈數據基于道路分布約束的考慮。

文獻［6］中，針對基于道路網絡分布的數據對象提出eb-cls算法，該算法本質上是一種層次聚類算法，適用于任意形狀簇的數據，提高了層次聚類算法的運行效率，然而，在ZigBee無線傳感網絡中，單個匯聚節點的內存是有限的，即它所能接收到的其他傳感節點數量是有限的，同時，節點間的Zig-Bee無線傳感距離是受環境影響的。

本文在文獻［6］基礎上提出了基于道路網絡的路燈聚類組網算法SLCNARN，在道路網絡環境中，增加了聚類算法對基于環境的網絡距離定義、路燈集中控制器容量以及對路燈基于道路分布特點的考慮，并利用對比實驗驗證該算法的可行性。

2 基本模型和定義

本文首先引入路網模型、網絡距離等定義［8~9］，將道路網絡表示為圖，將道路路段映射為圖的邊，將路段的交叉節點映射為圖的結點，將路燈節點映射為對象。路網模型和網絡距離的引入，極大簡化了路燈數據的復雜程度，同時也較好地反映了路燈數據基于道路網絡分布的特點。然而，在路燈節點間（ZigBee）通信的過程中，路燈節點的通信距離有限，同時還會受到環境因素的制約，此外，作為需要存放路燈節點信息的集中控制器容量也有限。

因此，針對不同環境下路燈節點間通信距離不同的特點，增加了對基于環境影響的網絡距離的定義；然后結合集合集中控制器容量有限的特點，對路燈聚類的約束條件進行定義。

定義1：道路網絡與路燈節點。

道路網絡可以表示為無向圖G={V，E，W}，其中，V 是路段交叉結點的集合{v1，v2，…，vn} ，E是各個路段的集合{e1，e2，…，en}，W是路段長度集合，表示邊對應的權值。路燈節點位于圖的邊e上，可以表示為一個三元組(vi，vj，p)，其中，vi和vj為路燈節點所在邊的兩個結點，p為路燈節點到它所在網絡邊結點vi的距離，取值范圍為[0，W(e)]。

對象間的相似性通常用歐式距離來度量，距離越近相似性越高，基于路燈節點之間通信連接的特性，采用網絡距離來取代歐式距離。

定義2：路燈節點間的網絡距離。

1）因為道路網絡模型的邊是基于道路路段的交叉結點劃分，所以同一路段上面的兩個路燈x，y之間的網路距離采用直接距離D(x，y)，定義為

其中，px和py分別表示為在同一條網絡邊上的對象到結點的距離。

2）同一路段上路燈節點到所在邊上結點間的網絡距離。

其中，D(x，vi)表示路燈節點x到所在結點vi的距離，D(x，vj)表示路燈節點x到所在結點vj的距離，W(vi，vj)表示結點vi和結點vj之間的距離。

路段結點間的網絡距離D(vi，vj)。即網絡節點間的最短路徑距離，采用迪杰斯特拉算法求解。

3）不同路段上的路燈節點之間的網絡距離，定義為

其中，D(x′，vi)表示路燈節點x′到所在結點vi的距離，D(vi，vj)表示不同路段結點間的最短距離，D(vj，y′)表示路燈節點y′到所在結點vj的距離。

定義3：聚類間的網絡距離。為兩個聚類邊界上面的路燈之間的最短網絡距離。假設聚類Cm={pm1，pm2，…，pmz}，Cn={pn1，pn2，…，pnz}，則聚類間的網絡距離定義為

定義4：基于環境影響的網絡距離。

由于在實際的項目部署過程中，路燈終端節點間的有效通信距離會受到節點附近的環境影響，比如，樹木建筑物的遮擋。在此，通過引入環境綜合影響因子來表征環境對路燈節點的影響程度，同時考慮到ZigBee節點，則網絡距離，在此定義為

式中，γx和γy分別表示路燈節點對應的環境綜合影響因子。其中，γ的取值可以參考室外無線信號路徑損耗模型［10~11］定義如下：

路燈節點既可以作為發送節點也可以作為接收節點。式中，d 是到發送節點的距離，L（d）是距離發送節點d處的路徑損耗；d0為參考距離，一般取值為1m，L(d0)為距離發射節點距離為d0的路徑損耗；τ為路徑損耗指數，表示路徑損耗隨距離增長的速率，它與傳播環境有關；Xσ為陰影衰落引起的樣本標準差，為零均值的高斯分布。

信道鏈路損耗的影響因素較多，與所處的環境、工作頻段等有關，在這上面，國內外有很多學者進行了大批量的測試，并對相關參數進行了統計分析，根據Sohrabi K［12］等在各種不同的傳播條件下，針對固定頻率范圍內的測試結果可知，樹木的濃密程度對無線信號的強度有較大影響。在城市道路建設的過程中，道路兩旁的綠化設施會導致路燈信號傳播過程的衰減，在SLCNARN算法中，綜合考慮通訊模塊信號、路燈間距和綠化程度等因素，對信號衰減區域進行簡單的劃分，對γ進行不同的取值，如表1所示。

表1 綜合環境影響因子分類

定義5：路燈聚類塊。

當Cl 滿足下列條件時，稱非空集合Cl 為一個路燈聚類塊。

1）路燈節點總數≤集中控制器容量θ。

2）相鄰兩個路燈節點間的距離≤最大有效通信距離ε。

其中，集中控制器的最大負荷θ，是出于對集中控制器內存容量的考慮，需要存放路燈的參數信息、注冊信息等。

3 基于道路約束的路燈組網算法

不同的聚類分析方法適用于不同的數據聚類應用場景，通常需要考慮數據量大小和數據特征屬性來選擇合適的聚類算法。路燈數據是空間型數據，文獻［1］中，提出的eb-cls聚類算法可以有效找出基于道路網絡中的對象聚類的結果。然而，由于在ZigBee無線傳感網絡中，路燈的集中控制器所能存儲的路燈信息是有限的，同時，相鄰節點間的有效傳輸距離是受環境影響的。

SLCNARN 算法是建立在eb-cls 算法的基礎上，增加了對基于環境的網絡距離定義、路燈集中控制器容量以及對路燈基于道路分布特點的考慮，并通過對比實驗驗證該算法的可行性。SLCNARN算法根據路燈對象帶狀分布以及ZigBee 結點組網的特點，以路燈通信距離和路燈集中控制器容量作為聚類分裂階段和合并階段的條件，這樣在分裂階段只需要計算路段（邊）的長度，對超出集中控制器容量距離μ（μ=θ×路燈間距）的聚類進行分裂，減少了時間消耗，也提高了SLCNARN 聚類算法的精度。下面幾個小節主要對SLCNARN算法進行介紹說明，并通過實驗進行算法驗證。

3.1 eb-cls算法

eb-cls算法［1］，主要分為初始化階段、分裂階段和合并階段。它是將兩種典型的層次聚類方法（自頂向下分裂的層次聚類方法和自下向上的凝聚層次聚類方法）相結合，利用對象包含邊的信息，從中間層次將對象劃分為初始聚類，再分別向下層和上層進行層次的分裂和合并，這種方法適用于數據量大的數據，聚類效率較高。

eb-cls 算法在分裂階段時，需要遍歷每條邊上面的對象，對相鄰對象距離相似度不滿足條件的聚類，在兩個對象之間將聚類塊劃分裂成兩個聚類；在合并階段時，也是根據相鄰聚類間的網絡距離進行聚類的合并。而對于路燈對象來說，它們在道路上是等距分布的，即同一道路邊上的對象是相似的。

因此，本文提出的SLCNARN算法，根據路燈對象帶狀分布以及zigbee 結點組網的特點，以路燈通信距離和路燈集中控制器容量作為聚類分裂階段和合并階段的條件，這樣在分裂階段只需要計算路段（邊）的長度，對超出集中控制器容量距離μ（μ=θ×路燈間距）的聚類進行分裂，減少了時間消耗，也提高了SLCNARN 聚類算法的精度。下面幾個小節主要對SLCNARN 算法進行介紹說明，并通過實驗進行算法驗證。

3.2 SLCNARN算法

SLCNARN 算法本質上是基于層次聚類的算法，大致分為以下三個階段：聚類初始化階段、聚類分裂階段、聚類合并階段。

1）聚類初始化階段。將同一個路段上面的路燈劃分成同一個聚類，初始聚類的個數即為網絡邊的個數。

2）聚類分裂階段。主要是依次遍歷各個路段，依次分裂大的聚類塊為較小的聚類塊。具體來說，對于每個初始的聚類，使它的網絡邊的長度不大于μ。另外，為了優化接下來的聚類合并，還需要為每個聚類塊指定其滿足μ和θ有效結點。

3）聚類合并階段。根據聚類塊之間的距離相似度，同時，需要結合聚類合并之后路燈節點總數，使它的和不大于集中控制器的最大負荷。具體來說，就是需要反復合并每個結點周圍的聚類，直到合并到最大的聚類結果。

3.3 算法步驟

4 實驗結果分析與討論

4.1 實驗配置和數據集

實驗的硬件環境配置為Intel（R）Core（TM）i5-4200M CPU 和8G 內存的PC，軟件環境為win10平臺，所有代碼使用C#實現。本文使用A 市中心城區的路網結構及其路燈終端節點安裝位置作為實驗數據，根據所在環境特征，其終端及其對應的綜合環境影響因子γ分布如圖2所示。

圖1 路網結構及其綜合影響因子示意圖

圖2 k-mediods、eb-cls和SLCNARN效果圖

根據地理環境特征，將該市路網結構圖大致分成3個區域，其中，區域1，以高速公路為主，地帶較為空曠，樹木遮擋較少，故綜合影響因子取值為γ=0.9；區域2，以市區街道為主，樹木建筑較多，路燈有較多藏在樹中，故綜合影響因子取值為γ=0.6；區域3，有一定程度低矮建筑和樹木遮擋，故綜合影響因子取值為γ=0.8。

根據我國《城市道路照明設計標準》［12］以及對集中控制器的內存容量等因素的考慮，將實驗參數設置如下：集中控制器的最大容量設置為300，路燈間距設置為25m，相鄰節點最大通信距離設置為200m。

4.2 實驗結果與分析

為了評估該算法的性能，我們通過將此算法分別與eb-cls算法和k-mediods算法的分類方法進行比較。本小節主要從算法的實現效果和算法效率進行對比驗證。

SLCNARN 算法效果驗證：路燈對象的聚類效果主要從路燈對象的整體性和聚類的精度兩方面綜合考慮。

一方面是路燈對象的整體性。道路路燈是基于道路分布的，因此，需要考慮路燈控制時候按道路開關的一致性和連貫性，即一條道路（邊）被聚類到的對象個數越少越好。在本實驗中，通過對比不同算法數據集中每條邊上的聚類總數與道路邊總數的比值來衡量路燈對象的整體性。

其中，k表示道路邊的數目，CKi表示每條邊上面聚類的個數，表示每條邊的“整體性”。

另一方面是聚類的精度。聚類精度是檢測聚類質量的重要指標。路燈對象在聚類的過程中，需要將每個對象都“分配”到聚類中去，同時，需要滿足聚類中心容量（集中控制器的容量）的要求。在本實驗中，我們通過計算對象數與集中控制器容量的百分比作為衡量聚類精度的指標［14］，其公式如下：

其中，n 表示聚類的數目，CNi表示第i 個聚類中的對象個數，θ是集中控制器最大容量，是第i個聚類的精度值，P2的取值是所有聚類的平均精度值。

通過對路燈對象整體性和聚類精度兩方面的考慮，分別應用式（8）和式（9）對P1和P2值進行比較，實驗結果如表2、表3 所示，由表2 可知，eb-cls算法與SLCNARN算法，路燈對象的整體性相似，這是由于兩個算法在聚類初始化階段都是以路燈對象所在邊作為初始化聚類，在分裂階段中eb-cls算法由于相鄰路燈對象之間距離等距，分裂出的聚類有限，SLCNARN 算法由于根據集中控制器容量進行聚類分裂，分裂出的聚類也比較有效，因而兩個算法最終的整體性相似；SLCNARN 算法與k-mediods 算法相比，聚類路燈對象的整體性較好，整體性數值也較為穩定，由表3 可知，SLCNARN 算法的聚類精度高于eb-cls 算法，這是由于eb-cls 算法在聚類的過程中會刪除孤立的點，而在k-mediods 算法中，聚類簇數和中心點的選擇對結果影響很大。

表2 路燈對象整體性比較

表3 聚類的準確率比較

如圖2 所示，（a）是k-mediods 算法聚類結果，生成了23 個聚類中心點即集中控制器擺放位置；（b）是eb-cls 算法聚類結果，生成了13 個聚類中心點，聚類中心數量與（a）和（c）相比較少，每個聚類中心點所聚合的終端節點數量大于集中控制器容量閾值；（c）是SLCNARN 算法聚類結果圖，生成了28 個聚類中心點，中心點位置主要集中在路口交叉處，便于管理。

SLCNARN 算法效率驗證：基于上述的實驗配置和數據集，通過改變路燈節點的數量值，對SLCNARN 算法、eb-cls 算法以及k-mediods 算法執行時間進行比較，結果如圖3 所示，SLCNARN 算法執行時間要比eb-cls 算法要低，遠小于k-mediods算法，這是由于SLCNARN 算法是基于道路邊進行算法的分裂過程，同時考慮了路燈對象的空間特性和傳播特性，減少了聚類算法的操作過程，而k-mediods 算法運行的時間由它的復雜度O(k(n-k)2)決定的。

圖3 執行時間比較

通過上述實驗的分析驗證可以看出，SLCNARN算法可以有效地找出路燈對象聚類的結果，計算出集中控制器的擺放位置；而且算法的效率較高，在路燈集中控制器的選址上具有較高的應用價值。

5 結語

本文提出的路燈組網算法在綜合考慮道路、環境等因素的前提下，將路燈節點進行聚類分簇，計算路燈集中控制器的擺放位置，同時通過實驗，與K-mediods 算法、eb-cls 算法進行對比，實驗結果表明，該算法能夠有效降低勞動強度，為集中控制器的安裝提供理論依據。