一種等級化分布式時間同步算法

摘 要： 為了滿足無線自組網中采用分布式TDMA組網所需的時間同步要求，提出了一種等級化分布式時間同步算法。該方法采用時間參考節點推選制度，實時更新參考節點，同時采用分層的時間等級和時間質量相結合使得在網的每個節點都能和自己周圍最靠近時間參考點的節點進行對時同步，仿真實驗結果表明，該方法能夠提高同步精度，完全滿足分布式TDMA無線自組網的時間同步要求。

關鍵詞： 無線自組網； 時分多址； 分布式時間同步； 時間參考節

中圖分類號： TN929.5?34 文獻標識碼： A 文章編號： 1004?373X（2013）17?0037?04

0 引 言

無線自組網（Ad Hoc Network）也稱多跳無線網，是由一組帶有無線通信收發裝置的移動終端節點組成的一個多跳的臨時性無中心網絡，可以在任何時刻、任何地點快速構建起一個移動通信網絡，并且不需要現有信息基礎網絡設施的支持，網中的每個終端可以自由移動，地位相等[1]。

時分多址（TDMA）是目前在無線自組網絡中普遍采用的一種信道接入方法。TDMA信道訪問需要維護一個公共的時間參考基準來實現無沖突TDMA通信，網絡時間同步為一個基本要求[2]。因而網絡同步技術是實現TDMA的關鍵技術之一。對于分布式網絡而言，節點之間沒有統一的時鐘。而TDMA是要求統一時鐘的，因此設計一種切實可行的同步策略非常重要。

本文針對分布式TDMA提出了一種基于質量的等級化分布式時間同步算法，采用時間參考節點推選制度，實時更新參考節點，同時采用分層的時間等級和時間質量相結合使得在網的每個節點都能和自己周圍最靠近時間參考點的節點進行對時同步，提高了同步的精確性。

1 時間同步技術

定時同步技術的主要作用是使各節點的時間基準保持一致，各個節點保持同步，從而能以TDMA的方式使用公共的無線媒介。

目前，常用的TDMA定時同步技術主要有：

（1）高精度時鐘法

各節點采用高精度的時鐘如原子鐘、銣鐘等產生自己的時間基準。

高精度時鐘法的優點是：精度很高，如原子鐘1 μs/天，故幾乎沒有同步誤差；沒有網絡的分裂和合并問題，協議簡單，而缺點則是成本、體積和功耗較大。

（2）外時間基準法

利用GPS或北斗時標作為時間基準。GPS的時間精度已經達到了20 ns，因而在Ad Hoc網中可以利用GPS同步時鐘來為每個終端提供同步[3]。

外時間基準法的優點是：精度高，實現簡單；沒有網絡的分裂和合并問題，協議簡單。其缺點則是網絡的運行必須依賴于GPS或北斗時標信號，一旦時標信號不可用時，網絡便無法運行[4]。

（3）分布式同步法

分布式同步有兩個方式：一種是中心式的，即以某節點為中心，其他節點與它同步；另一種是互同步技術[4?5]。節點之間相互計算同步誤差，利用數學迭代方法逐步收斂到同步位置上[6?9]。

分布式同步法的優點是：不依賴外部時鐘源，抗毀頑存能力強；成本、體積和功耗較小。其缺點則是：由于傳輸時延、噪聲干擾等因素，網絡中存在較大的同步誤差；網絡存在分裂和合并問題，故協議較復雜。

比較上面三種同步方式，各種方式各有優缺點。但在追求低成本、不依賴外部信號支持的應用場合，為了支持多跳中繼路由情況下的自組網TDMA接入，分布式同步法是最有效的同步方法。

2 基于質量的等級化分布式時間同步算法

2.1 算法描述

首先，對每個節點同步信息增加相應的時間參考點ID信息、時間等級信息和時間質量信息；

其次，根據各節點ID值的大小推選時間參考節點，以時間參考節點為中心向外擴散，構成逐級擴散的同步網絡，并確定各節點的時間等級和時間參考點ID值，修改對應節點信息中的時間等級信息和時間參考點ID信息；

然后，時間參考節點定時廣播對時和路由信息，路由信息包含有節點同步信息，各級節點分別與時間等級靠前的節點進行對時，并修改本節點的時間等級信息和時間參考點ID信息，同時開始本節點的對時間隔的計時，即時修改時間質量信息，完成時隙同步。

2.2 逐級擴散同步

逐級擴散同步的基本思想是以參考站為基準，逐級向下建立同步。同一同步組內組員按節點序號大小的順序，采用不同起始時刻進行下一級同步組構建及維護。

如圖1所示為分布式時間同步自組網拓撲示例。

0節點相當于同步基準站，它發送同步信息給它周圍的鄰節點1，4，5。1，4，5稱為一級節點，也就是同一同步組的組員。按照以上思想，它們按序號大小用不同起始時刻構建相應的下一級同步組。于是1先向它的下一級節點發送同步信息，也就是向2節點發送同步信息，2成為二級節點。之后，4向它的下一級節點發送同步信息，也就是10，14和7節點，他們也是二級節點。同理節點5向下發送同步信息，使得6成為二級節點。這時，二級節點開始向下建立同步。2再向它的下一級節點，也就是3傳送同步信息，3是第三級節點。同理，10向9，6向12，14向15發送同步信息，它們也都是第三級節點。8和13是第四級節點，11是第五級節點。

網絡中“葉子”節點不需要發送同步信息。某節點發現在正常發送狀態下相當長時間內沒有子節點存在，轉入特殊發送狀態，將同步信息發送時間間隔增大，甚至停止發送。當網絡某節點發現其子節點丟失，并在一定時間內沒有其具體信息，則向相鄰的“葉子”節點發送查找指示，從而重新恢復“葉子”節點的正常發送狀態。當處于正常發送狀態的“葉子”節點收到進入特殊狀態指示后進入特殊狀態并停止發送同步信息。

由圖1的逐級擴散的同步方式，可以得到不同等級的同步組。圖2為同步組等級樹形關系。

其中的每一個節點都是子節點的組首，都是父節點的組員。例如，1是0的組員，2的組首。

2.3 節點管理

（1）當新節點加入時，重新推選時間參考節點，以時間參考節點為中心向外擴散，重新構成逐級擴散的同步網絡，根據時間參考節點定時廣播對時和路由信息，新節點和其他節點分別修改自身的時間參考點ID信息、時間等級信息和時間質量信息。

（2）當節點移動時，以時間參考節點為中心向外擴散，重新構成逐級擴散的同步網絡，根據時間參考節點定時廣播對時和路由信息，移動節點及其相關節點分別修改自身的時間參考點ID信息、時間等級信息和時間質量信息。

（3）當節點退出時，重新推選時間參考節點，以時間參考節點為中心向外擴散，重新構成逐級擴散的同步網絡，根據時間參考節點定時廣播對時和路由信息，其他節點分別修改自身的時間參考點ID信息、時間等級信息和時間質量信息。

（4）當一個節點有一個以上提供對時的節點時，優先選擇時間等級高的節點，其次選擇時間質量好的節點。

2.4 同步分區

同步時標傳遞是全網同步定時關鍵，網中各組首都要發送同步時標。發送時序非常重要，不允許兩個相鄰組采用相同時刻發送同步時標。因此全網組首發送同步時標順序應相對固定。

兩個不存在任何連通關系的組可采用相同時刻進行時標發送。通過組間信息交換和組首協調，不同組可以選擇不同時刻進行時標發送。此策略可采用圖論相關知識完成。0級同步組根據連通關系確定所涂顏色，相鄰節點顏色不同。

對整網進行涂色即可獲取每個節點發送時標的時刻，相同顏色采用相同時刻，不同顏色采用不同時刻。相同時刻可能只距離一跳，會造成干擾，因此色距取值不小于2。從而解決全網同步時標合理安排問題，避免發送碰撞和干擾問題。不同顏色的時刻根據系統干擾要求進行安排，優先使用較前的時刻。

由于網絡同步是擴散型的，必須保證同步時標定時發送，同時還要保證各級之間數據交換正常。為此，不同級采用不同的同步定時區，每級在相應的同步區進行同步時標發送。圖3為6級分布示意圖。

如果將同步時標周期分為三或四個部分，每一部分為同步定時區，那么同步時標長度的上限就可被確定。由圖3中可以看出，采用四區制時，上下級交換和同級交換具有相同時間，而三區制則同級交換時間大于上下級交換。采用哪種制式可根據業務要求和網絡要求進行選擇。區數小于3是不可能進行擴散組網的，由于時標長度有限和控制難度，采用大于4的區數相對4而言，信道利用和交換比例沒有大的提高，但控制復雜度相對高。因此，網絡同步逐級擴散，不同級采用不同同步定時區，同級節點采用不同時刻（顏色）發送同步時標。

圖4是采用四區制的分配方案，其中圓內標識的第1個數字表示級數，第2個字母表示區號，第3個字母表示時刻。

3 仿真驗證

3.1 網絡拓撲

在QualNet網絡模擬器中設計開發了等級化分布式時間同步算法，并對多跳網絡進行了模擬，對實驗結果進行了可視化處理。某次多跳實驗的戰術拓撲場景如圖5所示。

模擬網絡參數設置：網絡節點數：30；覆蓋范圍：1 500 m×1 500 m；通信距離：252 m；時間同步收斂條件：網絡中任意節點與根節點的最大時鐘偏差≤1 ppm；每次仿真交互步進記錄一次時間的變化情況。

3.2 實驗結果

記錄每次計算時刻每個節點的時鐘值，并繪制了可視化顯示，從而直觀地對分布式時間同步過程進行觀察和判讀。

如圖6所示為前24次時刻的時鐘變化情況。可以清楚地看到，表示場強的3?D表面圖隨笛卡爾坐標的分布情況。隨著迭代次數的增加，整個勢場從凹凸不平的類似山巒起伏的表面趨于向平滑演進，第24次迭代結束時，整個勢場呈現出較為平滑的平面，但是其右方的地勢較高，向左方傾斜。說明此時每個節點都和其自身鄰居進行了局部同步，但是整個網絡還未同步，整個勢場具有一定的梯度。

初始化和網絡仿真結束對應的時鐘如7圖所示。可以看到，在滿足收斂條件后的時鐘被“拉平”到了一個一致的時鐘，整個網絡達到全網同步，整個過程需要137次仿真步進。

經過大量的網絡仿真實驗，實現等級化分布式時間同步所需的交互次數和網絡層級數量及每一級的節點數量有關，對于小規模網絡，所需的入網同步交互時間僅為幾秒鐘內即可，完全滿足分布式自組網的TDMA時間同步要求。

4 結 語

本文針對分布式同步方法提出了一種基于質量的等級化分布式時間同步算法。該算法擯棄了參考節點固定的弊端，采用參考節點推選制度，當參考節點被破壞或退出時，會推選出新的時間參考節點，與傳統的TDMA協議相比，其抗毀性明顯增強。同時，該方法采用分層的時間等級和時間質量相結合的同步機制，使得在網的每個節點都能和自己周圍最靠近時間參考點的節點進行對時同步。仿真結果表明，本文提出的基于質量的等級化分布式時間同步算法提高了同步的精度，完全能夠滿足分布式自組網的TDMA時間同步要求。

參考文獻

[1] 鄭相全.無線自組網技術實用教程[M].北京：清華大學出版社，2004.

[2] 劉慶剛，李大雙，朱家成.多跳TDMA組網同步的分布式控制方法[J].通信技術，2012，45（5）：26?32.

[3] 程楠.Ad Hoc網絡TDMA分布式動態時隙算法[J].計算機應用研究，2005，32（1）：222?225.

[4] 孫獻璞，張艷玲.自組織網絡的互同步技術研究[J].西安電子科技大學學報：自然科學版，2005，32（2）：216?219.

[5] 漆璐，陳旿.Ad Hoc網絡時鐘同步研究[J].計算機應用研究，2011，28（12）：4702?4704.

[6] 羅義軍.Ad Hoc網絡中時間同步方法的研究[J].長江大學學報：自然科學版·理工卷，2007（1）：63?65.

[7] 余毅敏，余奇.同線多跳自組網中的時隙同步問題研究[J].科技信息，2010（5）：461?463.

[8] 楊琦，石江宏，陳輝煌.無線自組織網絡分布式時隙同步算法[J].系統工程與電子技術，2011，33（4）：888?893.

[9] 馮文江，袁遠，胡致遠.實現自組網互同步的一種單源同步法[J].電路與系統學報，2009，14（3）：23?27.

[10] 張存利，吳怡，黃鴻強，等.基于802.11網絡的無線視頻傳輸系統設計[J].現代電子技術，2010，33（4）：70?72.

[11] 王英力，莊奕琪，湯華蓮，等.無線視頻傳輸系統的設計[J].現代電子技術，2008，31（1）：18?20.