孫同陳 李 峰

（江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

匯聚節(jié)點(diǎn)在ZigBee 無(wú)線傳感網(wǎng)絡(luò)中起著重要作用，是無(wú)線傳感網(wǎng)絡(luò)的集群中心。選擇合適的位置部署匯聚節(jié)點(diǎn)不僅可以提高底層mesh 無(wú)線組網(wǎng)的可靠性，同時(shí)也提高了無(wú)線傳輸速度［1］。由于匯聚節(jié)點(diǎn)部署在集中控制器內(nèi)部，對(duì)于匯聚節(jié)點(diǎn)的選址實(shí)際上也是對(duì)集中控制器選址。

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

文獻(xiàn)［6］中，針對(duì)基于道路網(wǎng)絡(luò)分布的數(shù)據(jù)對(duì)象提出eb-cls算法，該算法本質(zhì)上是一種層次聚類算法，適用于任意形狀簇的數(shù)據(jù)，提高了層次聚類算法的運(yùn)行效率，然而，在ZigBee無(wú)線傳感網(wǎng)絡(luò)中，單個(gè)匯聚節(jié)點(diǎn)的內(nèi)存是有限的，即它所能接收到的其他傳感節(jié)點(diǎn)數(shù)量是有限的，同時(shí)，節(jié)點(diǎn)間的Zig-Bee無(wú)線傳感距離是受環(huán)境影響的。

本文在文獻(xiàn)［6］基礎(chǔ)上提出了基于道路網(wǎng)絡(luò)的路燈聚類組網(wǎng)算法SLCNARN，在道路網(wǎng)絡(luò)環(huán)境中，增加了聚類算法對(duì)基于環(huán)境的網(wǎng)絡(luò)距離定義、路燈集中控制器容量以及對(duì)路燈基于道路分布特點(diǎn)的考慮，并利用對(duì)比實(shí)驗(yàn)驗(yàn)證該算法的可行性。

2 基本模型和定義

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

因此，針對(duì)不同環(huán)境下路燈節(jié)點(diǎn)間通信距離不同的特點(diǎn)，增加了對(duì)基于環(huán)境影響的網(wǎng)絡(luò)距離的定義；然后結(jié)合集合集中控制器容量有限的特點(diǎn)，對(duì)路燈聚類的約束條件進(jìn)行定義。

定義1：道路網(wǎng)絡(luò)與路燈節(jié)點(diǎn)。

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

對(duì)象間的相似性通常用歐式距離來(lái)度量，距離越近相似性越高，基于路燈節(jié)點(diǎn)之間通信連接的特性，采用網(wǎng)絡(luò)距離來(lái)取代歐式距離。

定義2：路燈節(jié)點(diǎn)間的網(wǎng)絡(luò)距離。

1）因?yàn)榈缆肪W(wǎng)絡(luò)模型的邊是基于道路路段的交叉結(jié)點(diǎn)劃分，所以同一路段上面的兩個(gè)路燈x，y之間的網(wǎng)路距離采用直接距離D(x，y)，定義為

其中，px和py分別表示為在同一條網(wǎng)絡(luò)邊上的對(duì)象到結(jié)點(diǎn)的距離。

2）同一路段上路燈節(jié)點(diǎn)到所在邊上結(jié)點(diǎn)間的網(wǎng)絡(luò)距離。

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

路段結(jié)點(diǎn)間的網(wǎng)絡(luò)距離D(vi，vj)。即網(wǎng)絡(luò)節(jié)點(diǎn)間的最短路徑距離，采用迪杰斯特拉算法求解。

3）不同路段上的路燈節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離，定義為

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

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

定義4：基于環(huán)境影響的網(wǎng)絡(luò)距離。

由于在實(shí)際的項(xiàng)目部署過(guò)程中，路燈終端節(jié)點(diǎn)間的有效通信距離會(huì)受到節(jié)點(diǎn)附近的環(huán)境影響，比如，樹木建筑物的遮擋。在此，通過(guò)引入環(huán)境綜合影響因子來(lái)表征環(huán)境對(duì)路燈節(jié)點(diǎn)的影響程度，同時(shí)考慮到ZigBee節(jié)點(diǎn)，則網(wǎng)絡(luò)距離，在此定義為

式中，γx和γy分別表示路燈節(jié)點(diǎn)對(duì)應(yīng)的環(huán)境綜合影響因子。其中，γ的取值可以參考室外無(wú)線信號(hào)路徑損耗模型［10~11］定義如下：

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

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

表1 綜合環(huán)境影響因子分類

定義5：路燈聚類塊。

當(dāng)Cl 滿足下列條件時(shí)，稱非空集合Cl 為一個(gè)路燈聚類塊。

1）路燈節(jié)點(diǎn)總數(shù)≤集中控制器容量θ。

2）相鄰兩個(gè)路燈節(jié)點(diǎn)間的距離≤最大有效通信距離ε。

其中，集中控制器的最大負(fù)荷θ，是出于對(duì)集中控制器內(nèi)存容量的考慮，需要存放路燈的參數(shù)信息、注冊(cè)信息等。

3 基于道路約束的路燈組網(wǎng)算法

不同的聚類分析方法適用于不同的數(shù)據(jù)聚類應(yīng)用場(chǎng)景，通常需要考慮數(shù)據(jù)量大小和數(shù)據(jù)特征屬性來(lái)選擇合適的聚類算法。路燈數(shù)據(jù)是空間型數(shù)據(jù)，文獻(xiàn)［1］中，提出的eb-cls聚類算法可以有效找出基于道路網(wǎng)絡(luò)中的對(duì)象聚類的結(jié)果。然而，由于在ZigBee無(wú)線傳感網(wǎng)絡(luò)中，路燈的集中控制器所能存儲(chǔ)的路燈信息是有限的，同時(shí)，相鄰節(jié)點(diǎn)間的有效傳輸距離是受環(huán)境影響的。

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

3.1 eb-cls算法

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

eb-cls 算法在分裂階段時(shí)，需要遍歷每條邊上面的對(duì)象，對(duì)相鄰對(duì)象距離相似度不滿足條件的聚類，在兩個(gè)對(duì)象之間將聚類塊劃分裂成兩個(gè)聚類；在合并階段時(shí)，也是根據(jù)相鄰聚類間的網(wǎng)絡(luò)距離進(jìn)行聚類的合并。而對(duì)于路燈對(duì)象來(lái)說(shuō)，它們?cè)诘缆飞鲜堑染喾植嫉?，即同一道路邊上的?duì)象是相似的。

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

3.2 SLCNARN算法

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

1）聚類初始化階段。將同一個(gè)路段上面的路燈劃分成同一個(gè)聚類，初始聚類的個(gè)數(shù)即為網(wǎng)絡(luò)邊的個(gè)數(shù)。

2）聚類分裂階段。主要是依次遍歷各個(gè)路段，依次分裂大的聚類塊為較小的聚類塊。具體來(lái)說(shuō)，對(duì)于每個(gè)初始的聚類，使它的網(wǎng)絡(luò)邊的長(zhǎng)度不大于μ。另外，為了優(yōu)化接下來(lái)的聚類合并，還需要為每個(gè)聚類塊指定其滿足μ和θ有效結(jié)點(diǎn)。

3）聚類合并階段。根據(jù)聚類塊之間的距離相似度，同時(shí)，需要結(jié)合聚類合并之后路燈節(jié)點(diǎn)總數(shù)，使它的和不大于集中控制器的最大負(fù)荷。具體來(lái)說(shuō)，就是需要反復(fù)合并每個(gè)結(jié)點(diǎn)周圍的聚類，直到合并到最大的聚類結(jié)果。

3.3 算法步驟

4 實(shí)驗(yàn)結(jié)果分析與討論

4.1 實(shí)驗(yàn)配置和數(shù)據(jù)集

實(shí)驗(yàn)的硬件環(huán)境配置為Intel（R）Core（TM）i5-4200M CPU 和8G 內(nèi)存的PC，軟件環(huán)境為win10平臺(tái)，所有代碼使用C#實(shí)現(xiàn)。本文使用A 市中心城區(qū)的路網(wǎng)結(jié)構(gòu)及其路燈終端節(jié)點(diǎn)安裝位置作為實(shí)驗(yàn)數(shù)據(jù)，根據(jù)所在環(huán)境特征，其終端及其對(duì)應(yīng)的綜合環(huán)境影響因子γ分布如圖2所示。

圖1 路網(wǎng)結(jié)構(gòu)及其綜合影響因子示意圖

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

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

根據(jù)我國(guó)《城市道路照明設(shè)計(jì)標(biāo)準(zhǔn)》［12］以及對(duì)集中控制器的內(nèi)存容量等因素的考慮，將實(shí)驗(yàn)參數(shù)設(shè)置如下：集中控制器的最大容量設(shè)置為300，路燈間距設(shè)置為25m，相鄰節(jié)點(diǎn)最大通信距離設(shè)置為200m。

4.2 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估該算法的性能，我們通過(guò)將此算法分別與eb-cls算法和k-mediods算法的分類方法進(jìn)行比較。本小節(jié)主要從算法的實(shí)現(xiàn)效果和算法效率進(jìn)行對(duì)比驗(yàn)證。

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

一方面是路燈對(duì)象的整體性。道路路燈是基于道路分布的，因此，需要考慮路燈控制時(shí)候按道路開(kāi)關(guān)的一致性和連貫性，即一條道路（邊）被聚類到的對(duì)象個(gè)數(shù)越少越好。在本實(shí)驗(yàn)中，通過(guò)對(duì)比不同算法數(shù)據(jù)集中每條邊上的聚類總數(shù)與道路邊總數(shù)的比值來(lái)衡量路燈對(duì)象的整體性。

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

另一方面是聚類的精度。聚類精度是檢測(cè)聚類質(zhì)量的重要指標(biāo)。路燈對(duì)象在聚類的過(guò)程中，需要將每個(gè)對(duì)象都“分配”到聚類中去，同時(shí)，需要滿足聚類中心容量（集中控制器的容量）的要求。在本實(shí)驗(yàn)中，我們通過(guò)計(jì)算對(duì)象數(shù)與集中控制器容量的百分比作為衡量聚類精度的指標(biāo)［14］，其公式如下：

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

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

表2 路燈對(duì)象整體性比較

表3 聚類的準(zhǔn)確率比較

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

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

圖3 執(zhí)行時(shí)間比較

通過(guò)上述實(shí)驗(yàn)的分析驗(yàn)證可以看出，SLCNARN算法可以有效地找出路燈對(duì)象聚類的結(jié)果，計(jì)算出集中控制器的擺放位置；而且算法的效率較高，在路燈集中控制器的選址上具有較高的應(yīng)用價(jià)值。

5 結(jié)語(yǔ)

本文提出的路燈組網(wǎng)算法在綜合考慮道路、環(huán)境等因素的前提下，將路燈節(jié)點(diǎn)進(jìn)行聚類分簇，計(jì)算路燈集中控制器的擺放位置，同時(shí)通過(guò)實(shí)驗(yàn)，與K-mediods 算法、eb-cls 算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，該算法能夠有效降低勞動(dòng)強(qiáng)度，為集中控制器的安裝提供理論依據(jù)。