董甲東，吳順風，黃昌文

（1.安慶師范大學 電子工程與智能制造學院，安徽 安慶 246133；2.安徽安簧機械股份有限公司，安徽 安慶 246005）

近年來，隨著多功能傳感器技術和現(xiàn)代網(wǎng)絡技術的快速發(fā)展，無線傳感器網(wǎng)絡（WSN）得到廣泛應用。WSN是基于無線通信方式的分布式、多節(jié)點、多跳、自組織系統(tǒng)，其節(jié)點傳感器屬微型嵌入式設備，主要實現(xiàn)監(jiān)測對象數(shù)據(jù)采集、處理、發(fā)送以及請求信息的控制等功能，通過多節(jié)點協(xié)同，組成無線傳感器網(wǎng)絡，最終將獲取信息送達至用戶[1]。

各節(jié)點傳感器的時間同步是WSN的關鍵技術，也是近年來研究的熱點領域。傳感器節(jié)點在采集對象信息、信息處理、信息傳輸時，需要多個傳感器節(jié)點協(xié)同工作[2]。在同一系統(tǒng)中，各節(jié)點信息的采集和傳輸需要有統(tǒng)一的時間標準，這也是多個節(jié)點進行信息交換的關鍵。在WSN中，傳感器節(jié)點時間信息由各節(jié)點的本地時鐘提供。每個傳感器內含有一個晶體振蕩器，其構成了本地計時器。晶體振蕩器的生產(chǎn)工藝不同，或工作環(huán)境的溫度、壓力、工作時長不同，均可能導致傳感器節(jié)點的晶振速率產(chǎn)生偏差，最終造成網(wǎng)絡節(jié)點間的時間不同步。對于WSN，傳感器節(jié)點時間保持同步是實現(xiàn)傳感器運行、通信和節(jié)點定位的技術基礎[3]。在綜合分析、研究WSN的時間同步傳統(tǒng)算法基礎上，本文提出了CS-TPSN算法，通過層內和層間的優(yōu)化設計[4]，改進拓撲結構，減少報文數(shù)量，降低算法開銷，實現(xiàn)基于OPNET的建模和仿真分析。

1 無線傳感器網(wǎng)絡時間同步算法

Internet時間同步主要采用網(wǎng)絡時間協(xié)議（NTP）實現(xiàn)系統(tǒng)各節(jié)點的時間同步，結合本地時間和時間誤差，可對系統(tǒng)各節(jié)點進行時間統(tǒng)一，其精度可達毫秒級，時間同步機制已得到深入研究和廣泛應用?；贜TP協(xié)議基礎，WSN時間同步協(xié)議的算法主要有以下三類。

（1）接收者-接收者（Receiver-Receiver）的時間同步算法。其代表算法為2002年Jeremy Elson等提出的參考廣播同步算法（RBS）[5]。該算法具有較低的同步誤差，明顯的缺點就是節(jié)點之間進行同步需要交換包含時間信息的數(shù)據(jù)包[6]，數(shù)據(jù)包交換次數(shù)太多使得算法復雜且能量消耗大[7]。

（2）發(fā)送者-接收者（Sender-Receiver）的單向時間同步算法。其代表算法為2004年Miklós Maróti等提出的泛洪時間同步協(xié)議（FTSP）[8]。該算法采用單向消息處理方式，通過將通信延遲進行詳細劃分并分別進行處理來減小延遲對同步精度的影響，雖然提高了同步精度、減少了數(shù)據(jù)包交換量，但由于采用泛洪的方式，通信距離受中心節(jié)點能量制約，對于范圍較大的網(wǎng)絡能量消耗嚴重。

（3）發(fā)送者-接收者（Sender-Receiver）的雙向時間同步算法。其代表算法為2003年Saurabh Ganeri‐wal等提出的傳感器網(wǎng)絡的時間同步協(xié)議（TPSN）[9]。該算法采用中心節(jié)點與子節(jié)點的雙向通信，交換時間信息計算偏差值達到網(wǎng)絡時間同步，雖然具有較高的時鐘同步精度，但當網(wǎng)絡中節(jié)點密度較大時，節(jié)點同步跳數(shù)明顯增加，這影響了同步精度并增加了節(jié)點能量消耗。

此外，Kyoung-lae Noh等將RBS和TPSN進行結合，提出了PBS（Pairwise Broadcast Synchronization）時鐘同步算法[10]。該算法采用僅接收者（ROS）同步機制，減少了網(wǎng)絡通信能耗，但其采用兩個超級節(jié)點覆蓋網(wǎng)絡中其他所有節(jié)點，存在通信范圍有限的問題。當WSN規(guī)模增大時，網(wǎng)絡的同步精度會隨著節(jié)點的同步跳數(shù)增加而降低，同時會增加能耗[11]。經(jīng)典時鐘同步算法無法有效適應大規(guī)模多跳WSN。為此，結合TPSN與RBS算法的優(yōu)點，本文提出一種應用于多跳WSN的時間同步算法，即CS-TPSN（Clock Synchronization Node-TPSN）。在TPSN算法基礎上首先引入時鐘節(jié)點。同步節(jié)點和普通節(jié)點的概念，然后以分層的方式劃分節(jié)點，采用發(fā)送者-接收者雙向時間同步協(xié)議并結合廣播時間同步協(xié)議方式完成WSN時間同步，該算法可以確保同步精度，降低節(jié)點能量消耗，能夠應用于多跳WSN。

2 CS-TPSN改進算法

2.1 TPSN算法

TPSN時間同步算法是基于發(fā)送者-接收者雙向時間同步算法的代表協(xié)議，通過發(fā)送者與接收者間相互交換時間信息實現(xiàn)同步。該算法類似于NTP時間同步協(xié)議，需要一個提供絕對時間的時鐘源來負責對全網(wǎng)進行時間同步。采用網(wǎng)絡分層，將節(jié)點按層次劃分，下層節(jié)點只與對應上層節(jié)點通信以完成時間同步。算法執(zhí)行步驟分為兩個階段：層次發(fā)現(xiàn)階段和時間同步階段。

層次發(fā)現(xiàn)階段，該階段主要工作是將網(wǎng)絡分層。TPSN構建了一個生成樹，其中給每個節(jié)點設定唯一ID號，通過記錄節(jié)點ID號以維持分層過程中父子節(jié)點關系，每個節(jié)點都知道自己和父節(jié)點的層次。設定時鐘源節(jié)點為0層的根節(jié)點，負責網(wǎng)絡層次劃分開始。根節(jié)點發(fā)送分層數(shù)據(jù)包，其中包含自己所在0層的層次信息和節(jié)點ID。當所有一跳鄰居節(jié)點接收到數(shù)據(jù)包時，一跳節(jié)點將自己層次設為1，父節(jié)點層次設為0，并記錄父節(jié)點ID信息。一跳節(jié)點完成后再發(fā)送分層數(shù)據(jù)包，此時接收到1層數(shù)據(jù)包且未分層的節(jié)點將自己層次設為2，父節(jié)點層次設為1，并記錄父節(jié)點ID信息。以此類推來完成全網(wǎng)層次劃分。二跳TPSN網(wǎng)絡拓撲如圖1所示。

圖1 TPSN網(wǎng)絡拓撲結構

時間同步階段，該階段主要工作是將網(wǎng)絡節(jié)點時間同步。當網(wǎng)絡層次發(fā)現(xiàn)階段完成后，由參考節(jié)點發(fā)送時間同步開始包，開始網(wǎng)絡時間同步，時間開始同步包發(fā)送至全網(wǎng)。1層節(jié)點接收到開始同步數(shù)據(jù)包后向根節(jié)點發(fā)送時間同步請求，根節(jié)點接收后發(fā)送同步應答包，1層節(jié)點依次完成時間同步。待一層節(jié)點全部完成同步后，2層節(jié)點向1層節(jié)點發(fā)送時間同步請求，1層節(jié)點接收后發(fā)送同步應答包，2層節(jié)點依次完成時間同步。以此類推完成全網(wǎng)節(jié)點時間同步。節(jié)點雙向交換信息過程如圖2所示。

圖2 TPSN協(xié)議節(jié)點雙向交換信息過程

假設兩個節(jié)點i、j，將節(jié)點i同步到節(jié)點j，節(jié)點同步過程具體如下：

（1）節(jié)點i準備一個時間同步包，發(fā)送給節(jié)點j開始時間同步，并記錄發(fā)送時刻T1；

（2）節(jié)點j接收到節(jié)點i的時間同步包后，立刻記錄接收時刻，記錄為T2；

（3）節(jié)點j等待一段時間后發(fā)送時間同步應答包給節(jié)點i，并記錄發(fā)送時刻T3；

（4）節(jié)點i接收到節(jié)點j的時間同步應答包，記錄接收時刻為T4，并通過記錄的時間戳信息計算時間偏差。

令節(jié)點時間偏差為θ，傳輸延遲為d，根據(jù)時間同步過程可得計算出偏差和延遲后，節(jié)點i和j的時鐘差異可以修正，使用偏差校正本地時鐘，提高同步精確度。

2.2 CS-TPSN改進算法

如何降低TPSN協(xié)議的數(shù)據(jù)包交換次數(shù)，降低協(xié)議開銷，是研究優(yōu)化算法的主要方向。TPSN算法的節(jié)點間相互通信次數(shù)較多，在一次時間同步過程中，每一個節(jié)點都需要與父節(jié)點交換最少4次數(shù)據(jù)包。為解決數(shù)據(jù)包交換次數(shù)多的問題，通過網(wǎng)絡拓撲簡化對時間同步算法進行優(yōu)化。簡化后拓撲結構如下頁圖3所示。

圖3 CS-TPSN網(wǎng)絡拓撲結構

TPSN協(xié)議在多跳情況下，下層節(jié)點需向每個上層節(jié)點發(fā)送時間同步請求，下層節(jié)點需與多個上層節(jié)點計算偏差，這種同步方式并不能保證同步精度的提高。因此，設計下層節(jié)點選取一個上層節(jié)點作為父節(jié)點，一個下層節(jié)點對應一個父節(jié)點，父節(jié)點對應一個或多個子節(jié)點，父節(jié)點在整個網(wǎng)絡中被稱為同步節(jié)點。具體工作流程如下頁圖4所示。

圖4 CS-TPSN算法工作流程

（1）網(wǎng)絡拓撲初始化。全網(wǎng)時鐘源的參考節(jié)點主動發(fā)起周期性拓撲更新。數(shù)據(jù)中包含參考節(jié)點ID信息、自身層次和父節(jié)點等信息。接收到廣播消息的節(jié)點保存接收信息，將發(fā)送數(shù)據(jù)節(jié)點設置為父節(jié)點，并繼續(xù)發(fā)送包含相同信息的數(shù)據(jù)包，以此完成全網(wǎng)初始化。

（2）計算二跳節(jié)點。網(wǎng)絡初始化完成后，每個節(jié)點將保存自己的子節(jié)點信息，然后節(jié)點將子節(jié)點信息發(fā)送到父節(jié)點，此時父節(jié)點與自己保存的子節(jié)點信息進行對比可獲得二跳節(jié)點信息。

（3）計算同步節(jié)點。對于每個同步節(jié)點的計算，采用的是貪婪啟發(fā)式算法[12]。算法優(yōu)先覆蓋獨立節(jié)點，二跳節(jié)點與根節(jié)點之間如果只有一個節(jié)點進行數(shù)據(jù)轉發(fā)，則此中間節(jié)點被選為同步節(jié)點。在獨立節(jié)點覆蓋完成后，根據(jù)子節(jié)點覆蓋的二跳節(jié)點數(shù)量判斷是否被選擇為同步節(jié)點，二跳節(jié)點覆蓋數(shù)量多的優(yōu)先選中，完成全部覆蓋和同步節(jié)點選擇。

（4）同步方式名單。上層節(jié)點計算完同步節(jié)點并廣播發(fā)布信息，下層節(jié)點將根據(jù)此信息生成同步方式名單。當下層節(jié)點接收到上層節(jié)點發(fā)送的同步信息名單后，與自己ID進行對比，如果在名單中則將上層節(jié)點記錄在自己的同步節(jié)點名單中，并采用時間同步協(xié)議同步；如果不在同步名單中則將自己的同步名單記錄為空，采用廣播方式同步。

3 CS-TPSN算法建模與仿真

OPNET是一款用于網(wǎng)絡環(huán)境建模與仿真的專業(yè)軟件包，能精準仿真和分析各類復雜網(wǎng)絡性能，在網(wǎng)絡設備制造和通信運營領域有廣泛的應用。下面基于OPNET進行建模和仿真分析。

3.1 CS-TPSN算法建模

CS-TPSN算法建模主要包括進程層次設計、節(jié)點模型和包結構設計、網(wǎng)絡結構設計等，進程層次設計是建模仿真工作的核心。CS-TPSN算法具體功能將在進程模型設計中實現(xiàn)，設計完成后即可設計節(jié)點和網(wǎng)絡結構，最終完成仿真設計。

CS-TPSN算法節(jié)點分為TIME和COMMON節(jié)點，TIME節(jié)點負責提供基準時鐘，定義為0層根節(jié)點，其他除TIME節(jié)點外均為COMMON節(jié)點。TIME節(jié)點與COMMON節(jié)點均采用相同進程模型，但通過進程函數(shù)模塊設計并判斷節(jié)點類型后，執(zhí)行不同功能。進程模型如圖5所示。

圖5 TIME和COMMON節(jié)點進程模型

判斷TIME節(jié)點和COMMON節(jié)點關鍵代碼如下。

//獲取節(jié)點類型

op_ima_obj_attr_get(own_node_id,"Node Type",&node_type);

if(node_type==0)

{

initial_offset=0.0;

initial_skew=0.0;

//調度基準節(jié)點并發(fā)起拓撲初始化過程

op_intrpt_schedule_self

(op_sim_time(),TOPO_CODE);

own_parent=-1;

own_level=0;

}

else

{

//非核心節(jié)點存在時鐘偏差

initial_offset = op_dist_uniform

(0.1);

initial_skew=op_dist_uniform(0.000001);

own_parent=-1;

own_level=MAX_NODE_NUM;

}

TIME節(jié)點作為全網(wǎng)核心節(jié)點，有獨立時鐘源，負責提供全網(wǎng)基準時間。根據(jù)算法描述，核心節(jié)點主要承擔以下工作：（1）啟動網(wǎng)絡拓撲，對網(wǎng)絡進行分層和拓撲更新；（2）作為網(wǎng)絡節(jié)點參與網(wǎng)絡結構劃分；（3）與下層節(jié)點相互交換數(shù)據(jù)包，完成時間同步。TIME節(jié)點功能實現(xiàn)關鍵代碼如下。

if(op_intrpt_code()==TOPO_CODE)

{

//創(chuàng)建拓撲初始化報文

pkptr=op_pk_create_fmt("topo_init_pkt2");

//設置報文字段內容

op_pk_nfd_set(pkptr,"Type",0x00);

op_pk_nfd_set(pkptr,"Node ID",own_address);

op_pk_nfd_set(pkptr,"Level",0);

op_pk_nfd_set(pkptr,"Parent ID",-1);

//統(tǒng)計網(wǎng)絡開銷

op_stat_write(ovhd_gstathandle,1.0);

op_stat_write(ovhd_gstathandle,0.0);

//發(fā)送報文

op_pk_send(pkptr,OUTSTRM);

}

COMMON節(jié)點作為網(wǎng)絡內的普通節(jié)點，需要將時間與TIME節(jié)點同步。根據(jù)算法描述，COMMON節(jié)點主要承擔以下工作：（1）作為網(wǎng)絡節(jié)點，響應核心節(jié)點發(fā)起的網(wǎng)絡初始化，完成網(wǎng)絡分層和拓撲更新；（2）網(wǎng)絡分層完成后，主動向上層節(jié)點發(fā)起時間同步請求，與上層節(jié)點進行信息交互，完成時間同步工作；（3）如果COMMON節(jié)點被選擇為同步節(jié)點，則負責與下層節(jié)點進行信息交互完成時間同步工作。COMMON節(jié)點功能實現(xiàn)關鍵代碼如下。

//時間同步應答報文

static void time_synrpy_handle(Packet*pkptr)

{

int temp_node_id;

double temp_date;

FIN(time_synrpy_handle(pkptr));

//從報文中提取有效字段

op_pk_nfd_get(pkptr,"Child ID",&temp_node_id);

//判斷是否應答給本節(jié)點的報文

if(temp_node_id==own_address)

{

//提取上層節(jié)點反饋的時間信息

op_pk_nfd_get(pkptr,"T O 2",&syn_to2);

op_pk_nfd_get(pkptr,"T O 3",&syn_to3);

//記錄當前接收反饋時間

syn_ta4=current_time;

//計算時間偏差

temp_date=((syn_ta4-syn_to2)-(syn_to3-syn_ta1))/2;

time_date-=temp_date;

printf("node:%d current:%f time:%f date:%f-- % f ",own_address,current_time,op_sim_time(),temp_date,current_time-temp_date);

}

3.2 仿真分析

采用OPNET仿真軟件，對CS-TPSN算法與傳統(tǒng)RBS、TPSN算法的時間同步誤差和網(wǎng)絡開銷進行仿真，結果如圖6、圖7所示。由圖6可知：RBS算法的同步誤差較高，隨著節(jié)點數(shù)增加其誤差隨之加大；TPSN算法的同步誤差在節(jié)點數(shù)較少和跳數(shù)低的情況下表現(xiàn)優(yōu)異，但隨著跳數(shù)增加，同步誤差逐漸增加；在跳數(shù)較少時，CS-TPSN算法與TPSN算法時間同步誤差相差不大，但隨著跳數(shù)增加，CS-TPSN算法同步誤差逐漸優(yōu)于TPSN。由圖7可知：節(jié)點數(shù)量較少時，CS-TPSN算法無法選擇最佳鄰居節(jié)點，其性能應與TPSN相同，但由于CS-TPSN算法可以減少節(jié)點數(shù)據(jù)包交換次數(shù)，其他節(jié)點采用廣播監(jiān)聽的方式完成時間同步；而TPSN算法采用一對一時間同步，每個節(jié)點通過直接與上層節(jié)點交換數(shù)據(jù)包完成同步，隨著網(wǎng)絡節(jié)點數(shù)增加，跳數(shù)增多，CS-TPSN算法同步誤差將明顯小于TPSN算法，當節(jié)點數(shù)目為150時，誤差結果降低約20%，由其趨勢可知，伴隨節(jié)點數(shù)目增加誤差降低效果增強，如圖6所示。隨著節(jié)點數(shù)增加，RBS、TPSN算法協(xié)議開銷均高于CS-TPSN算法。

圖6 CS-TPSN算法與傳統(tǒng)算法的誤差仿真分析

圖7 CS-TPSN算法與傳統(tǒng)算法的網(wǎng)絡開銷仿真分析

4 結束語

綜上所述，本文在綜合分析傳統(tǒng)TPSN、RBS時間同步算法的基礎上，提出了改進算法CS-TPSN。本算法主要通過減少TPSN數(shù)據(jù)包交換次數(shù)減低能耗，提高節(jié)點生存壽命；采用周期性更新拓撲結構，提高算法的可擴展性，效果較好。但是，不足在于算法設計沒有充分考慮移動節(jié)點，這是未來研究和改進的方向。