葉青，史昕，孫夢薇，朱健

（1.國家山區(qū)公路工程技術(shù)研究中心，重慶 400067；2.重慶大學(xué) 大數(shù)據(jù)與軟件學(xué)院，重慶 401331；3.長安大學(xué) 信息工程學(xué)院，西安 710064）

0 引言

面向交通監(jiān)測的無線傳感網(wǎng)絡(luò)是智能交通領(lǐng)域新型應(yīng)用場景中的關(guān)注焦點［1］，傳感網(wǎng)絡(luò)具備的部署便利性［2］、感知協(xié)作性［3］、交互泛在性等優(yōu)點為傳統(tǒng)交通監(jiān)測應(yīng)用帶來顯著的改變［4］。實現(xiàn)感知協(xié)作性依賴于傳感節(jié)點之間的時間同步，即給特定區(qū)域內(nèi)的傳感節(jié)點提供一個公共通用的時間尺度［5］。該尺度旨在建立各個傳感節(jié)點感知數(shù)據(jù)與共識時間之間的一致性映射關(guān)系，交通監(jiān)測傳感網(wǎng)絡(luò)中與時序相關(guān)的所有操作均需解析該項映射關(guān)系［6］。時間同步算法主要由同步拓撲構(gòu)建和時鐘偏差估計構(gòu)成，其中同步拓撲旨在明確同步數(shù)據(jù)報文的傳輸路徑并決定報文數(shù)量的傳輸規(guī)模，也是執(zhí)行時鐘偏差估計的重要前提條件［7］。

交通監(jiān)測傳感網(wǎng)絡(luò)的時間同步在能量有效性和場景適應(yīng)性方面擁有獨特的設(shè)計需求。能量有效性需求主要體現(xiàn)在：傳感網(wǎng)絡(luò)的時間同步主要依賴節(jié)點間同步報文的無線共享交換。文獻［8］指出單個傳感器節(jié)點將1 Kb 字節(jié)數(shù)據(jù)傳輸100 m 所需的能量等價于執(zhí)行三百萬條指令消耗的能量，傳輸大量同步報文將加快傳感器節(jié)點能量的枯竭。然而在交通監(jiān)測傳感網(wǎng)絡(luò)中，傳感節(jié)點的核心任務(wù)是采集處理與傳輸共享交通流數(shù)據(jù)，如果傳感節(jié)點能量不加節(jié)制地消耗在同步報文無線傳輸中，則傳感節(jié)點的核心任務(wù)時間將大幅下降［9］。場景適應(yīng)性需求主要體現(xiàn)在：交通監(jiān)測傳感網(wǎng)絡(luò)的Sink 節(jié)點通?？紤]供電和維護的便利性進行部署，同步拓撲算法的能量有效性不能受Sink 節(jié)點部署位置的影響；交通監(jiān)測傳感網(wǎng)絡(luò)需要部署大規(guī)模的節(jié)點實現(xiàn)協(xié)同感知，同步拓撲算法的能量有效性不能受限于節(jié)點的部署規(guī)模；交通監(jiān)測傳感節(jié)點部署受限于道路邊界呈現(xiàn)狹長部署形態(tài)［10］，部分節(jié)點的同步報文傳輸必須采用多跳中繼方式實現(xiàn)［11］。

典型時間同步拓撲構(gòu)建算法主要有以下幾種：1）傳感網(wǎng)路時間同步協(xié)議（Timing-synchronization Protocol of Sensor Network，TPSN）算法［12］利用層探測方法構(gòu)建泛洪同步拓撲實現(xiàn)全網(wǎng)內(nèi)時間同步，由于所有節(jié)點均參與同步報文傳輸，同步過程會產(chǎn)生大量冗余報文。2）PBS（Pairwise Broadcast Synchronization）算法［13］利用無線信道廣播特性，同步位于相同廣播區(qū)域內(nèi)的節(jié)點，可有效減少同步報文開銷，但局限于單跳同步。3）GPA（Group-wise Pair-selection Algorithm）［14］利用PBS 算法通過層與層之間的同步傳遞實現(xiàn)多跳同步，存在大量已同步節(jié)點重復(fù)參與同步報文傳輸?shù)默F(xiàn)象，從而引入較多額外的能量開銷。4）DMSP（Distributed Multi-hop Synchronization Protocol）算法［15］是GPA 的一種改進，設(shè)置同步節(jié)點鏈表保存與篩選已同步節(jié)點，避免已同步節(jié)點重復(fù)參與同步，但是忽略了多基準節(jié)點的選擇問題。5）FDMS（Fast Distributed Multiple-hop Synchronization）算法［16］根據(jù)節(jié)點鄰接特征選擇互為相鄰的三個節(jié)點執(zhí)行RBS（Reference Broadcast Synchronization）算法［17］，該算法對節(jié)點拓撲連通性要求較高，僅適用于具備強連通性的拓撲結(jié)構(gòu)。6）EGTS（External Gradient Time Synchronization）算法［18］是FDMS 算法的一種改進，在鄰居節(jié)點間選擇參考節(jié)點多跳廣播時間報文，能夠減少多跳同步中已同步節(jié)點的重復(fù)報文傳輸量，但是同樣繼承了FDMS 算法對拓撲連通性要求較高的特點。7）LECFO（Linear Estimation of Clock Frequency Offset）算法［19］與ICPTR（Improved Clock Parameters Tracking and Ranging）算法［20］在時鐘偏差估計方面分別改進了GPA 和TPSN 算法，但沒有考慮同步拓撲對同步報文開銷的影響。近年來，全局分布式同步拓撲（無匯聚節(jié)點）構(gòu)建成為研究人員關(guān)注的焦點，它的魯棒性較好，對傳感器節(jié)點和關(guān)鍵通信鏈路狀態(tài)不敏感，但是拓撲構(gòu)建過程復(fù)雜度太高，節(jié)點集中式管理難以實現(xiàn)，且多跳性嚴重制約同步偏差估計的收斂速度［21］。

綜上所述，交通監(jiān)測傳感網(wǎng)絡(luò)由于Sink 節(jié)點的引入和節(jié)點的集中式管理需求，不適合采用分布式同步拓撲。在能量有效性方面，TPSN、EGTS 和ICPTR 算法在同步報文傳輸時存在大量冗余報文，難以滿足交通監(jiān)測傳感網(wǎng)絡(luò)對同步拓撲能量有效性的需求；PBS、LECFO 和DMSP 算法利用無線信道廣播特性［22］，在減少冗余報文方面優(yōu)于TPSN、EGTS 和ICPTR 算法，但對引入貪婪策略產(chǎn)生的局部最優(yōu)問題沒有給出相應(yīng)的解決方法，同步拓撲能量有效性的提升能力有限。在場景適應(yīng)性方面，TPSN、PBS 和ICPTR 算法沒有考慮同步報文的多跳傳輸；LECFO、DMSP 和EGTS 算法實現(xiàn)了同步報文的多跳傳輸，但對多跳同步涉及的多基準節(jié)點選擇問題沒有給出明確的解決方法；同時，TPSN、LECFO、EGTS 和ICPTR算法的能量有效性受限于節(jié)點的部署規(guī)模，即增大節(jié)點部署規(guī)模后同步報文開銷也呈現(xiàn)增大趨勢。

針對交通監(jiān)測傳感網(wǎng)絡(luò)時間同步拓撲的能量有效性和場景適應(yīng)性問題，提出一種基于形式概念分析的交通監(jiān)測傳感網(wǎng)絡(luò)貪婪性同步拓撲算法（Greedy Synchronization Topology algorithm based on Formal Concept Analysis for traffic surveillance based sensor network，GST-FCA）。該算法利用形式概念分析（Formal Concept Analysis，F(xiàn)CA）解析節(jié)點間的鄰接特征關(guān)聯(lián)性，實現(xiàn)多基準節(jié)點的篩選和廣播元組（Broadcast Tuple，BT）的構(gòu)建，以減少冗余性的同步報文開銷；通過引入向上托管機制以緩解貪婪策略產(chǎn)生的局部最優(yōu)問題，進一步降低已同步節(jié)點重復(fù)參與廣播元組篩選的概率；最后設(shè)定不同仿真測試場景利用Matlab 驗證GST-FCA 的能量有效性，GST-FCA 的能量有效性對節(jié)點部署位置、部署規(guī)模和道路部署具有較強的適應(yīng)性，能夠滿足交通監(jiān)測場景對節(jié)點進行大規(guī)模和便利性部署的應(yīng)用需求。

1 問題描述

交通監(jiān)測傳感網(wǎng)絡(luò)平面拓撲結(jié)構(gòu)根據(jù)TPSN 算法的層探測廣播機制可以轉(zhuǎn)換為層次型拓撲結(jié)構(gòu)，監(jiān)測網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)各個節(jié)點被分配不同的層數(shù)標識Li，i（i＞0）表示被定義節(jié)點距離Sink 節(jié)點（首次廣播層探測報文節(jié)點）的跳數(shù)。利用圖論思想描述交通監(jiān)測傳感網(wǎng)絡(luò)的時間同步拓撲結(jié)構(gòu)，即無向圖Gt(V，E)，其中：頂點V為交通監(jiān)測傳感網(wǎng)絡(luò)中的傳感節(jié)點集合；邊E為傳感節(jié)點間的鄰接特征集合。定義Vi和Vi+1分別表示Li層和Li+1層節(jié)點所構(gòu)成的集合，令V=Vi∪Vi+1。任意一 對節(jié)點vj和vk，且vj，vk∈V，如 果(vj，vk)∈E，則節(jié)點vj和vk存在鄰接特征，處在對稱性鏈接中的vj和vk互為鄰接特征。

由TPSN 算法的層探測廣播機制可得，處于Li+1層的所有節(jié)點在Li層必須至少擁有一個相鄰層鄰居節(jié)點，否則Li+1層的節(jié)點無法確定自身所處的層數(shù)。同步報文傳輸路徑如圖1 所示，如果Li層節(jié)點m與Li+1層節(jié)點n進行同步信息交換，即(m，n)∈E，利用同步信息交換的信道廣播，Li+1層節(jié)點不僅可以通過與Li層節(jié)點的直接同步信息交換實現(xiàn)時間同步，也可通過偵聽其余Li+1層鄰居節(jié)點與Li層節(jié)點的同步信息交換完成時間同步。即節(jié)點n、m與n在Li+1層的共同鄰居節(jié)點經(jīng)過x輪的同步信息交換均可實現(xiàn)同步，同時節(jié)點m與節(jié)點n配對構(gòu)成1 個廣播元組。

圖1 同步報文傳輸路徑示例Fig.1 Synchronization packet transmission path examples

廣播元組能夠引導(dǎo)局部鄰域內(nèi)節(jié)點的小范圍同步，且可以避免所有節(jié)點都必須參與發(fā)送同步報文實現(xiàn)同步，從而減少同步報文的傳輸量，提升同步拓撲的能量有效性。因此，可以考慮在交通監(jiān)測傳感網(wǎng)絡(luò)中構(gòu)建廣播元組以提升同步拓撲的能量有效性。根據(jù)節(jié)點鄰接特征和廣播元組的組成結(jié)構(gòu)，GST-FCA 需要解決滿足廣播元組約束條件下的多基準節(jié)點同步問題。該問題的求解過程涉及兩個關(guān)鍵點：如何解析同層與相鄰層鄰接特征的關(guān)聯(lián)性構(gòu)建廣播元組和怎樣減少因Li層節(jié)點同層鄰接特征制約產(chǎn)生的局部最優(yōu)解。

針對同層與相鄰層鄰接特征的關(guān)聯(lián)性解析，由于交通監(jiān)測傳感節(jié)點受通信距離約束，單個廣播元組難以實現(xiàn)Li+1層所有節(jié)點與Li層節(jié)點的時間同步，需要借助多基準節(jié)點同步（Synchronization with Multiple References，SMR）。從圖論角度描述SMR 可表示為：

從Gt=(V，E) 中篩選出NBT個廣播元組，其中：V=Vi∪Vi+1，Vi和Vi+1為Li層和Li+1層節(jié)點構(gòu)成的集合；E為Li層和Li+1層節(jié)點的鄰接特征集合；NBT表示實現(xiàn)Vi+1與Vi時間同步所需的最小廣播元組數(shù)。如果Di表示NBT個廣播元組在Li層的節(jié)點構(gòu)成的集合，當(dāng)Di中的元素唯一時，SMR 變?yōu)閱位鶞?節(jié)點同 步（Synchronization with Single Reference，SSR）。

廣播元組產(chǎn)生的局部最優(yōu)解主要由Li層節(jié)點同層鄰接特征制約已同步節(jié)點信息的共享范圍引起。如圖2 所示，vri表示位于Li層的基準節(jié)點，虛線表示節(jié)點的相鄰層鄰接特征，實線表示節(jié)點的同層鄰接特征，Li+1層節(jié)點構(gòu)成三個支配集。節(jié)點v3與vr3、v1與vr2、v6與vr5分別構(gòu)成3 個廣播元組（得到全局最優(yōu)解），如果vr1與vr5不存在鄰接特征，vr1會試圖同步節(jié)點v6和v7；vr1與vr3不存在鄰接特征，vr1會試圖同步節(jié)點v3，此情形將額外增加2 個廣播元組（得到局部最優(yōu)解），原因在于vr1并不掌握v6和v7已被同步的信息，vr1不能確定v3已被同步。因此在多基準節(jié)點同步條件下，Li層節(jié)點的同層鄰接特征會直接影響廣播元組的篩選數(shù)目。

2 基于FCA的貪婪性同步拓撲構(gòu)建

2.1 節(jié)點鄰接特征關(guān)聯(lián)性解析

FCA 是一種利用形式背景進行數(shù)據(jù)分析與規(guī)則提取的有力工具，提供了一種與傳統(tǒng)數(shù)據(jù)分析和知識表示完全不同的方法［23］。它利用形式化的語境構(gòu)造概念格（Concept Lattice，CL）表述組成本體的概念、屬性及關(guān)聯(lián)性。FCA 中概念的外延為對象集合，內(nèi)涵為所有對象的共有屬性集，外延作為CL 的行元素，內(nèi)涵作為CL 的列元素，行元素與列元素的關(guān)聯(lián)性用數(shù)值0 和1 表示，數(shù)值1 代表某對象與對應(yīng)屬性存在關(guān)聯(lián)性，0 則代表不存在關(guān)聯(lián)性。

本文引入形式概念分析，以不同層的節(jié)點集合與它的鄰接特征為形式背景，以廣播元組的組建結(jié)構(gòu)為關(guān)聯(lián)規(guī)則，對節(jié)點同層與相鄰層的鄰接特征進行關(guān)聯(lián)性分析，從而構(gòu)建廣播元組和劃分同步集合，具體過程如下。

定義1形式背景是由Q=(A，B，I)構(gòu)成的三元組，I是A和B的二元關(guān)系（即I?A×B），以Li層節(jié)點集合X與Li+1層節(jié)點集合Y為例，每一個二元組(x，y)∈I表示節(jié)點x∈X與節(jié)點y∈Y存在鄰接特征。

定義2假設(shè)形式背景Q=(X，Y，I)，φ表示冪集P(X)在冪集P(Y)中的映射關(guān)聯(lián)性，?表示冪集P(Y)在冪集P(X)中的映射關(guān)聯(lián)性，映射關(guān)聯(lián)性根據(jù)集合I判定，定義?X和?Y，(φ，?)是關(guān)于P(X)和P(Y) 的伽羅 瓦連接（Galois Connection，GC）［24］，φ和?定義如下。

定義4 關(guān)于二元組(x，y)的偽概念記為Rxy，Rxy為包含(x，y)的所有形式概念的組合：

分層條件下，節(jié)點間鄰接特征關(guān)聯(lián)性的分析步驟如下：

步驟1X賦值為Li層節(jié)點構(gòu)成的集合，Y賦值為Li+1層節(jié)點構(gòu)成的集合，P(X)定義為Li層節(jié)點構(gòu)成的冪集，同理定義P(Y)；根據(jù)φ和?的定義，若x為Li層任意一個節(jié)點，y為Li+1層任意一個節(jié)點，則φ(x)為與x存在鄰接特征的Li+1層節(jié)點構(gòu)成的集合，?(y)為與y存在鄰接特征的Li層節(jié)點構(gòu)成的集合。

步驟2 根據(jù)式（1）求解關(guān)于二元組(x，y)的偽概念Rxy，從Rxy中提取包含(x，y)的所有形式概念，具體流程如下。

1）構(gòu)建φ(x)的冪集P(φ(x))，從P(φ(x))中刪除不含y的元素，構(gòu)成集合P*(φ(x))，且P*(φ(x))?P(φ(x))。

2）若P*(φ(x))≠?，定義集合P*(φ(x))的任意一個元素為Y*，計算?(Y*)得到X*，X*表示與Y*所有元素存在鄰接特征的Li層節(jié)點；計算φ(X*)得到Y(jié)*，Y*表示與X*所有元素存在鄰接特征的Li+1層節(jié)點；于是，得到若干個包含(x，y)的形式概念，其中：r={1，2，…，T}，T為集合P*(φ(x))的基數(shù)。

其中：| · |表示集合的基數(shù)運算符。

步驟4 計算與節(jié)點x存在強關(guān)聯(lián)性的Li+1層節(jié)點集合sync_node(x)：

同理，定義Y和Z均為Li+1層節(jié)點構(gòu)成的集合，y和z分別為Li+1層的任意一個節(jié)點，同時定義所有形成的集合為，計算與節(jié)點y存在強關(guān)聯(lián)性的節(jié)點集合sync_node(y)：

步驟5 根據(jù)圖2 描述的廣播元組結(jié)構(gòu)示例，同步集合sync_set(x，y)由Li層節(jié)點x與Li+1層節(jié)點y的共同鄰居節(jié)點構(gòu)成：

步驟6 利用貪婪策略從所有同步集合sync_set(x，y)中找出集合元素數(shù)最多時所對應(yīng)的(xk，yk)：

式（6）中的xk和yk將構(gòu)成一個廣播元組，刪除與sync_set(xk，yk)中所有元素相關(guān)的鄰接特征，可得到修改后的關(guān)于X和Y的二元關(guān)系I*，此操作目的在于刪除已加入同步集合的節(jié)點，以避免這些節(jié)點重復(fù)參與同步集合的篩選。

步驟7 根據(jù)修改后的二元關(guān)系I*，從步驟1 開始重復(fù)執(zhí)行，直至sync_set(x，y)為空，此時Li+1層節(jié)點均已加入已有的同步集合，Li層與Li+1層節(jié)點的同步拓撲構(gòu)建完成。

2.2 局部最優(yōu)問題優(yōu)化及分層廣播機制改進

2.1 節(jié)表明Li層節(jié)點的鄰接特征（即連通性）直接影響已加入同步集合節(jié)點信息的共享范圍，然而共享范圍的局限性容易產(chǎn)生局部最優(yōu)解。通過分析節(jié)點鄰接特征關(guān)聯(lián)性解析結(jié)果，可以得到：Li-1層節(jié)點（Li層的上一層相鄰節(jié)點）能夠獲取較Li層節(jié)點更加充分的已同步節(jié)點信息。

證明 假設(shè)Li-1層節(jié)點構(gòu)成集合為V，Li層節(jié)點構(gòu)成集合為X，v為Li-1層任意一個節(jié)點，x為Li層任意一個節(jié)點，定義所有形成的集合為，利用式（7）計算通過Li-1層節(jié)點能夠與節(jié)點x建立關(guān)聯(lián)性的Li層節(jié)點構(gòu)成的集合Ux：

由形式概念分析的計算過程可得，Ux中的元素即使與節(jié)點x不存在同層鄰接特征，也能夠通過Vk*中的元素（屬于Li-1層集合V），與節(jié)點x共享已同步節(jié)點構(gòu)成的集合，從而擴大節(jié)點x原有同步集合的共享范圍。

因此，如果Li-1層節(jié)點能夠擁有Li和Li+1兩層鄰居信息，可以緩解因Li層節(jié)點鄰接特征制約引起的局部最優(yōu)問題?？紤]引入向上托管機制，將原來在Li層執(zhí)行的廣播元組構(gòu)建算法上移至Li-1層托管執(zhí)行。為了實現(xiàn)向上托管機制，提出針對TPSN 算法層探測廣播機制的改進步驟如下。

改進步驟1 假設(shè)節(jié)點m所在層數(shù)為Li，當(dāng)節(jié)點m接收到層數(shù)比i大的節(jié)點n發(fā)來的層探測數(shù)據(jù)包時，將節(jié)點n加入到節(jié)點m的相鄰層鄰接特征集合中，作為節(jié)點m的Li+1層鄰居；當(dāng)節(jié)點m接收到與i相等的節(jié)點n發(fā)來的層探測數(shù)據(jù)包時，將節(jié)點n加入到節(jié)點m的同層鄰接特征集合中，作為節(jié)點m的Li層鄰居。不同的是，TPSN 算法的層探測廣播機制針對上述兩類數(shù)據(jù)包執(zhí)行丟棄操作。

改進步驟2 當(dāng)交通監(jiān)測傳感網(wǎng)絡(luò)的節(jié)點層數(shù)（假設(shè)最大層數(shù)為M）分配完畢后，從LM層到L1層執(zhí)行回溯廣播，與DMSP 算法不同的是，LM層節(jié)點分別廣播它的同層鄰居信息，Li(0 ＜i＜M)層節(jié)點分別廣播它的同層和相鄰層鄰居信息，那么Li-1層節(jié)點至少可以擁有3 類信息：Li層鄰居節(jié)點的同層鄰居信息、Li層節(jié)點在Li+1層的鄰居信息以及Li+1層鄰居節(jié)點的同層鄰居信息。

改進后的分層廣播機制執(zhí)行過程存在如下特點：

1）Li層節(jié)點執(zhí)行回溯廣播時，數(shù)據(jù)包只封裝Li層和Li+1層鄰居信息，并非Li層以下所有層的鄰居信息。

2）假設(shè)網(wǎng)內(nèi)節(jié)點總數(shù)為N，從空間復(fù)雜度分析，獲得兩層鄰接特征所需廣播報文的總體數(shù)量規(guī)模為O(N)，相較于獲得單層鄰接特征，不會呈現(xiàn)數(shù)量級上的顯著增長［25］；

3）GST-FCA 與DMSP 算法均額外增加N個報文開銷完成回溯廣播，但是GST-FCA 中具備同層鄰接特征的節(jié)點，因此不需要報文開銷即可共享各自同步集合篩選結(jié)果。

2.3 GST-FCA的主要實現(xiàn)流程

GST-FCA 的主要實現(xiàn)流程歸納如下：

1）建立鄰居信息：利用改進的層探測廣播機制收集同層和相鄰層節(jié)點的鄰居信息；

2）向上托管執(zhí)行：引入向上托管機制，將廣播元組構(gòu)建算法上移至Li-1層托管執(zhí)行；

3）求解偽概念：針對Li-1層每個節(jié)點所包含的Li和Li+1層節(jié)點信息，求解分別由Li層任意節(jié)點x和Li+1層任意節(jié)點y構(gòu)成的二元組(x，y)的偽概念Rxy；

5）計算強關(guān)聯(lián)集合：選中使增益值取最大時對應(yīng)的節(jié)點x和y，根據(jù)式（3）、（4）分別計算出與節(jié)點x和y存在強關(guān)聯(lián)性的Li+1層節(jié)點集合sync_node(x)和sync_node(y)；

6）計算同步集合：根據(jù)式（5）得到由Li層節(jié)點x與Li+1層節(jié)點y的共同鄰居節(jié)點構(gòu)成的同步集合sync_set(x，y)；

7）修改鄰接特征：根據(jù)式（6）找出同步集合元素數(shù)最多所對應(yīng)的(xk，yk)，刪除與sync_set(xk，yk)中所有元素相關(guān)的鄰接特征，得到修改后的關(guān)于X和Y的二元關(guān)系I*；

8）判斷重復(fù)執(zhí)行：根據(jù)修改后的二元關(guān)系I*，返回第3）步重復(fù)執(zhí)行，直至sync_set(x，y)為空集則退出，此時Li+1層節(jié)點均已加入已有同步集合，完成Li層與Li+1層節(jié)點的同步拓撲構(gòu)建。

9）實現(xiàn)多層循環(huán)：定義網(wǎng)絡(luò)最大層數(shù)為M，根節(jié)點位于0層，則參數(shù)i的取值范圍為[ 1，M-1 ]，將參數(shù)i按照該范圍分別依次取值以實現(xiàn)全網(wǎng)范圍內(nèi)的同步拓撲構(gòu)建。

3 仿真實驗與結(jié)果分析

3.1 同步報文開銷仿真條件設(shè)置

利用Matlab 計算和分析GST-FCA 的同步報文開銷，關(guān)鍵仿真條件和參數(shù)定義如下：

1）在100 m×100 m 區(qū)域隨機部署交通監(jiān)測傳感節(jié)點2次，每次部署節(jié)點100 個；

2）在100 m×100 m 區(qū)域隨機部署交通監(jiān)測傳感節(jié)點15次，每次部署節(jié)點數(shù)目呈遞增趨勢以控制節(jié)點的平均度數(shù)變化；

3）以高速公路雙向6 車道的交通監(jiān)測場景為例，設(shè)定應(yīng)急車道寬度為3 m、行車道寬度為4 m、隔離帶寬度為1 m，在100 m×31 m 區(qū)域按指定位置部署交通監(jiān)測傳感節(jié)點126 個，節(jié)點部署于車道寬度方向中心位置，沿車道長度方向部署間距為7.5 m；

4）考慮到報文無線發(fā)送消耗的能量與發(fā)送報文數(shù)量強相關(guān)，以報文開銷量表征同步能耗的規(guī)模［15］，仿真結(jié)果中的報文開銷量指單次同步中若要實現(xiàn)相同報文傳輸范圍必需的同步報文傳輸量，且1 個廣播元組單次同步需要2 個同步報文開銷；每個廣播元組中層數(shù)較大的節(jié)點用“▲”表示。

3.2 同步報文開銷仿真結(jié)果與對比分析

仿真場景1：100 m×100 m 區(qū)域內(nèi)部署節(jié)點數(shù)目為100，設(shè)定節(jié)點間通信距離為25 m。

仿真場景1 主要用于分析GST-FCA 在100 m×100 m 區(qū)域內(nèi)隨機部署條件下的同步報文開銷，同時驗證Sink 節(jié)點部署位置對同步報文開銷的影響。該場景中，除Sink 節(jié)點外其余節(jié)點的位置呈現(xiàn)隨機性，在方形區(qū)域隨機部署相較于狹長部署形態(tài)的測試條件更具備一般性，且節(jié)點部署密度和平均度數(shù)擁有更大靈活性，可以更好地檢驗GST-FCA 的能量有效性以及Sink 節(jié)點部署位置對其影響。如果通過隨機部署Sink 節(jié)點驗證它對算法同步能量有效性的影響，可能由于Sink 節(jié)點部署位置太多，難以有效呈現(xiàn)所有仿真情況。結(jié)合交通流監(jiān)測傳感網(wǎng)絡(luò)應(yīng)用場景，Sink 節(jié)點的部署通常考慮供電和維護的便利性，一般部署在道路邊緣或者中央隔離帶。因此，選擇Sink 節(jié)點坐標（50，50）和（50，100）兩種情形進行仿真驗證。

表1 是2 種Sink 節(jié)點坐標下多種典型同步拓撲算法在不同層內(nèi)完成1 次同步所需的同步報文開銷，表中各項數(shù)據(jù)根據(jù)分層拓撲結(jié)構(gòu)以及各個算法的同步報文傳輸路徑計算，其中，最優(yōu)結(jié)果加粗表示，次優(yōu)結(jié)果用下劃線表示。從表1 可以看出，無論Sink 節(jié)點位于區(qū)域中心還是邊緣位置，相較于對比算法，GST-FCA 的同步報文開銷最小。當(dāng)Sink 節(jié)點位于（50，100）時，將GST-FCA 各層的同步報文開銷總和與次優(yōu)的DMSP 的差值除以DMSP 的同步報文開銷總和，可以得到GST-FCA 的同步報文開銷的最小降幅為11.54%。由此可得，GST-FCA 利用基于FCA 生成的廣播元組構(gòu)建時間同步拓撲，可以有效解決TPSN、EGTS 和LECFO 算法存在的大量冗余性同步報文開銷問題；GST-FCA 相較于DMSP 算法的單次同步報文開銷更少，說明GST-FCA 可以降低已同步節(jié)點重復(fù)參與廣播元組篩選的概率。Sink 節(jié)點的部署位置雖然直接影響其余傳感節(jié)點的分層結(jié)果，但是GST-FCA 的同步能量有效性沒有因為Sink 節(jié)點的部署位置產(chǎn)生較大影響。

表1 Sink節(jié)點在不同位置時的單次同步報文開銷Tab.1 Synchronization packet overhead in one synchronization round for Sink node located in different positions

仿真場景2：100 m×100 m 區(qū)域內(nèi)部署不同數(shù)目節(jié)點15次，節(jié)點數(shù)目變化范圍為100～200，節(jié)點間通信距離為20 m。

仿真場景2 主要用于分析GST-FCA 在100 m×100 m 區(qū)域內(nèi)不同節(jié)點平均度數(shù)下的同步報文開銷，即驗證節(jié)點部署規(guī)模對同步報文開銷的影響。圖3 給出不同節(jié)點平均度數(shù)對應(yīng)的同步報文開銷，圖中每條曲線的走向趨勢是經(jīng)過多項式插值擬合的結(jié)果，Sink 節(jié)點坐標為（50，50）?？梢钥闯?，TPSN、LECFO 和EGTS 算法的同步報文開銷隨著節(jié)點平均度數(shù)的增加而提高，DMSP 和GST-FCA 的同步報文開銷則整體保持平穩(wěn)趨勢，同時GST-FCA 的同步報文開銷少于DMSP 算法。通常在限定區(qū)域內(nèi)部署的節(jié)點數(shù)目越大則平均度數(shù)越大，而圖3 說明DMSP 和GST-FCA 的同步報文開銷受節(jié)點規(guī)模影響不明顯，且將GST-FCA 與DMSP 的所有節(jié)點平均度數(shù)上的同步報文開銷相加，同樣按照場景1 中的方式計算，GST-FCA 的同步報文開銷相較于DMSP 降低了24.59%。由此可見，GST-FCA 不僅可以減少大量冗余性同步報文開銷，而且通過引入向上托管機制間接擴大已同步節(jié)點信息的共享范圍，可以有效地緩解DMSP 算法因貪婪策略產(chǎn)生的局部最優(yōu)解問題（達到24.59%）；同時，GST-FCA 能在保證同步能量有效性的基礎(chǔ)上實現(xiàn)較大規(guī)模的節(jié)點部署，適用于交通監(jiān)測應(yīng)用場景。

圖3 不同節(jié)點平均度數(shù)對應(yīng)的同步報文開銷Fig.3 Synchronization packet overhead corresponding to different average degree of nodes

仿真場景3：100 m×31 m 的高速公路監(jiān)測區(qū)域內(nèi)，部署節(jié)點數(shù)目為100，節(jié)點間的通信距離為15m 。

仿真場景3 主要用于分析GST-FCA 在高速公路監(jiān)測場景下的同步報文開銷，即在道路和車道約束條件下驗證GST-FCA 的能量有效性。圖4 分別給出兩種126 個節(jié)點在高速公路交通監(jiān)測場景下的廣播元組分布情形，節(jié)點間的通信距離越短則節(jié)點平均度數(shù)越小，定義沿道路行進方向為X軸，垂直道路行進方向為Y軸。圖4 中節(jié)點平均度數(shù)為19.02，Sink 節(jié)點坐標分別為（50，31）、（50，15.5）。表2、3 分別列出Sink 節(jié)點位于邊緣和中心時多種典型同步拓撲算法在不同層內(nèi)完成1 次同步所需同步報文開銷。同樣按照場景1 中的計算方式計算同步報文開銷降低的幅度?？梢钥闯?，無論Sink 節(jié)點位于邊緣還是中心時，GST-FCA 的同步報文開銷相較于TPSN、LECFO、EGTS 和DMSP 等算法都取得了最小，且開銷至少降低39.16%、47.67%。Sink 節(jié)點位于道路邊緣時，節(jié)點被劃分為5 層，Sink 節(jié)點位于道路隔離帶時，節(jié)點被劃分為4 層，相同節(jié)點分布情況下，Sink 節(jié)點位于節(jié)點覆蓋區(qū)域中心位置可以減少節(jié)點層數(shù)，有利于降低多跳同步的累計誤差，同時GST-FCA 作用下的同步報文開銷并沒有較大差異性。由此表明，GST-FCA 通過FCA 產(chǎn)生的廣播元組和向上托管機制構(gòu)建時間同步拓撲，在受道路和車道約束的交通監(jiān)測場景中，不僅可以實現(xiàn)較少的單次同步報文開銷，而且DMSP 算法局部最優(yōu)解問題的優(yōu)化效果有進一步提升，尤其對于分層內(nèi)節(jié)點數(shù)量越多且所處層越靠近Sink 節(jié)點的網(wǎng)絡(luò)區(qū)域，它的優(yōu)化效果更為突出，這些優(yōu)勢有利于GSTFCA 在交通監(jiān)測場景中實現(xiàn)更好的時間同步拓撲能量有效性。

表2 Sink節(jié)點位于邊緣時的同步報文開銷Tab.2 Synchronization packet overhead when Sink node locating at edge

圖4 126個節(jié)點的廣播元組分布情形Fig.4 Scenarios of broadcast tuple distribution based on 126 nodes

無線傳感器網(wǎng)絡(luò)中報文無線傳輸存在丟包的可能性，且丟包率與報文大小、發(fā)送頻率、傳輸距離、障礙阻攔、網(wǎng)絡(luò)拓撲和沖突碰撞等因素有關(guān)聯(lián)。如果考慮丟包因素，可引入平均丟包率作為丟包期望值，實際的同步報文開銷估計通過必需的同步報文開銷附加上丟失的同步報文數(shù)量進行計算。根據(jù)丟包率計算公式，如果同步拓撲算法單次同步必需的報文開銷較大，其報文丟失數(shù)量相對較多，則實際同步報文開銷也較大，擴展到多輪同步亦是如此。因此，仿真過程以必需的同步報文開銷為參數(shù)指標在一定程度上可以表征同步拓撲算法的能量有效性。此外，如果進一步量化和分析不同網(wǎng)絡(luò)參數(shù)約束下的實際同步報文開銷，如丟包率、碰撞率、發(fā)送頻率和傳輸距離等，可結(jié)合已構(gòu)建的時間同步拓撲利用專門網(wǎng)絡(luò)仿真平臺進行測試與驗證。

表3 Sink節(jié)點位于中心時單次同步所需同步報文開銷Tab.3 Synchronization packet overhead when Sink node locating in center

4 結(jié)語

本文提出了一種基于形式概念分析的交通監(jiān)測傳感網(wǎng)絡(luò)貪婪性同步拓撲算法GST-FCA，實現(xiàn)了多基準節(jié)點同步條件下的廣播元組篩選，優(yōu)化了貪婪策略所產(chǎn)生的局部最優(yōu)解問題，并在Matlab 上驗證了算法的能量有效性和場景適應(yīng)性。測試結(jié)果表明，GST-FCA 能夠進一步減少同步報文傳輸量，對Sink 節(jié)點的部署位置和網(wǎng)絡(luò)節(jié)點的部署規(guī)模具備較強適應(yīng)性，且能夠在受道路和車道約束的高速公路交通監(jiān)測場景下呈現(xiàn)出較好的能量有效性。在進一步的工作中，考慮到廣播元組節(jié)點能量消耗相對較大，將研究基于Sink 節(jié)點部署位置的交通監(jiān)測傳感網(wǎng)絡(luò)內(nèi)節(jié)點同步能耗的均衡問題，以及結(jié)合丟包率、碰撞率等參數(shù)利用OMNet++或Network Simulator 平臺對算法的報文開銷作進一步量化分析。