基于形式概念分析的交通監測傳感網絡貪婪性同步拓撲算法

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

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

0 引言

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

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

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

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

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

1 問題描述

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

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

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

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

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

從Gt=(V，E) 中篩選出NBT個廣播元組，其中：V=Vi∪Vi+1，Vi和Vi+1為Li層和Li+1層節點構成的集合；E為Li層和Li+1層節點的鄰接特征集合；NBT表示實現Vi+1與Vi時間同步所需的最小廣播元組數。如果Di表示NBT個廣播元組在Li層的節點構成的集合，當Di中的元素唯一時，SMR 變為單基準 節點同 步（Synchronization with Single Reference，SSR）。

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

2 基于FCA的貪婪性同步拓撲構建

2.1 節點鄰接特征關聯性解析

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

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

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

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

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

分層條件下，節點間鄰接特征關聯性的分析步驟如下：

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

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

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

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

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

步驟4 計算與節點x存在強關聯性的Li+1層節點集合sync_node(x)：

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

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

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

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

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

2.2 局部最優問題優化及分層廣播機制改進

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

證明 假設Li-1層節點構成集合為V，Li層節點構成集合為X，v為Li-1層任意一個節點，x為Li層任意一個節點，定義所有形成的集合為，利用式（7）計算通過Li-1層節點能夠與節點x建立關聯性的Li層節點構成的集合Ux：

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

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

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

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

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

1）Li層節點執行回溯廣播時，數據包只封裝Li層和Li+1層鄰居信息，并非Li層以下所有層的鄰居信息。

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

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

2.3 GST-FCA的主要實現流程

GST-FCA 的主要實現流程歸納如下：

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

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

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

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

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

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

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

9）實現多層循環：定義網絡最大層數為M，根節點位于0層，則參數i的取值范圍為[ 1，M-1 ]，將參數i按照該范圍分別依次取值以實現全網范圍內的同步拓撲構建。

3 仿真實驗與結果分析

3.1 同步報文開銷仿真條件設置

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

1）在100 m×100 m 區域隨機部署交通監測傳感節點2次，每次部署節點100 個；

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

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

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

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

仿真場景1：100 m×100 m 區域內部署節點數目為100，設定節點間通信距離為25 m。

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

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

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

仿真場景2：100 m×100 m 區域內部署不同數目節點15次，節點數目變化范圍為100～200，節點間通信距離為20 m。

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

圖3 不同節點平均度數對應的同步報文開銷Fig.3 Synchronization packet overhead corresponding to different average degree of nodes

仿真場景3：100 m×31 m 的高速公路監測區域內，部署節點數目為100，節點間的通信距離為15m 。

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

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

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

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

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

4 結語

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