一种基于数据帧的无线自组网同步算法

杨　勇，张富琴，张　凡

(1.陕西烽火电子股份有限公司 西安技术研究所，陕西 西安 710075)(2.西安烽火电子科技有限责任公司，陕西 西安 710075)



一种基于数据帧的无线自组网同步算法

杨勇1,2，张富琴1,2，张凡1,2

(1.陕西烽火电子股份有限公司 西安技术研究所，陕西 西安 710075)(2.西安烽火电子科技有限责任公司，陕西 西安 710075)

无线自组网是一种无中心节点，能够在任何时刻、地点快速构建起的一个移动通信网络，具有组网快速、使用灵活、不受地理环境限制等优点。然而自组网中复杂的节点同步问题极大地制约了无线自组网的实际应用。为了解决此问题，本文提出了基于数据包头的时间同步算法。该算法借助同步头、路由信息和数据信息组成的数据帧来完成节点相互同步。理论及仿真实验结果均表明该算法具有复杂度低、时延小，抗毁性强等特点，为无线自组网在实际中的应用奠定了理论基础。

自组网；时分多址；时隙同步

无线自组网[1](Ad Hoc Network)也称多跳无线网，是由一组带有无线通信收发装置的移动终端节点组成的一个多跳的临时性无中心网络，可以在任何时刻、任何地点快速构建起一个移动通信网络，并且不需要现有信息基础网络设施的支持，网中的每个终端可以自由移动，地位对等[2]。时分多址(Time Division Multiple Address ,TDMA)是目前在无线自组网络中普遍采用的一种信道接入方法，其中网络时间同步为一个基本要求[3-4]，目的是实现TDMA战术网络的无冲突通信。而对于传统的有中心网络而言，存在一个固定的节点作为整个网络的核心，其优点是结构简单、便于网络时钟管理以及业务交换。然而其弊端也显而易见，由于网络中任意两个节点之间的信息交换均需通过中心节点，当中心节点的负荷过大无法及时处理相关信息时，便会出现网络堵塞不能满足业务需求。对于分布式网络而言，采用设置中心节点或设置临时中心节点的办法统一时钟[5-7]，并没有实现真正意义上完全的无中心网络，因此设计一种针对所有节点平等并切实可行的同步策略是非常重要的。

本文对现有的无线自组网的TDMA接入的同步算法优缺点进行了比较论述，并针对要实现完全无中心的分布式无线自组网的应用场合，提出了一种完全无需中心节点的时隙同步方法。该方法利用特殊设计的数据帧结构和同步信息发送策略，在数据帧中增加了同步头信息和路由信息，实现了完全无需中心节点的时分多址的时间同步。利用该方法构建的网络，由于没有固定或临时的中心节点，使得全网同步延时小，实现了网络中节点的完全平等，增强了系统的抗毁能力。

1　时间同步技术

定时同步的主要作用是使各节点的时间基准保持一致，各个节点保持同步[8-10]，从而能以TDMA的方式使用公共的无线媒介[11]。目前，常用的TDMA定时同步技术主要有：1)高精度时钟法。各节点采用高精度的时钟如原子钟、铷钟等产生自己的时间基准。 2)外部时间基准法。利用全球定位系统(Global Positioning System,GPS)或北斗时标作为时间基准。 3)分布式同步法。一种是中心式的，即以某节点为中心，其它节点与它同步；另一种是互同步技术，节点之间相互计算同步误差，利用数学迭代方法逐步收敛到同步位置上。然而上述三种同步技术均存在自身的不足。

高精度时钟法的缺点是网络中各个节点都需要装备高精度时钟法，成本高、体积和功耗较大[12]。外部时间基准法的缺点则是网络的运行必须依赖于GPS或北斗时标信号，一旦时标信号不可用时，网络便无法运行[13]。中心式的分布式同步法的缺点在于不管是设置或者以某种规则产生，都必须产生中心节点，全网的节点都和该节点进行对时同步，一旦中心节点退网或者被破坏，则全网节点就没有了对时标准，网络很快会处于失步状态，引起数据的收发的碰撞，从而产生倒置错包、丢包现象[14]。而利用数学迭代方法实现的互同步技术，网络收敛慢，定时精度低[15]。为了解决现有TDMA定时同步技术中存在的问题，本文提出了基于数据包头的时间同步算法。

2　基于数据包头的时间同步算法

2.1算法描述

TDMA多址接入协议是将时间分割成周期性的时帧(Frame)，每个时帧再分割成若干个时隙(Slot)(无论帧或时隙都是互不重叠)，然后根据一定的时隙分配原则，使每个用户只能在指定的时隙内发送。在常规实现过程中，在每个时隙内，根据功能不同分别发送数据信息、路由信息等。本算法首先根据每个节点配置ID号，并将其ID号利用一定的对应关系与对应发送时隙对应，确定节点的发送时隙。其次将每个节点对应发送时隙内的内容进行一体化设置，除了需发送数据外，增加相应的同步头和路由信息，将同步头、路由和数据信息组成新的数据帧在节点分配的时隙中发射。然后在每个节点内设置时隙定时器和时隙计数器、时帧计数器用于实现各节点之间的时隙长度计时和时间同步和时间更新，使节点间相互时间基准基本一致。最后各节点在接收时隙内接收相邻节点的数据并完成与其同步和数据传输。

对于每个节点，具体时帧结构如图1所示。每个时帧由M个时隙组成，M个节点在对应时隙上发送数据，在其余时隙处于接收状态。节点发送数据帧由四部分组成。

图1　时帧结构组成示意图Fig.1　Thestructure of the frame

1)时隙保护。用于克服在下次同步之前引起的时间偏差。该时间偏差主要是由晶体偏移误差、同步误差和数据处理延时等不确定性引起。该时隙保护长度设置取决于系统采用晶体的精度、同步误差和数据传输延时的不确定值等。

2)同步头。将源节点地址采用Walsh序列、m序列或其他序列扩频而成，主要用于节点间时间相互同步和发送源节点地址值。同步头长度选择取决于系统设计的同步精度需要和网络中节点数大小。

3)路由信息。每个节点都记录与自己相邻的一跳节点和相邻的多跳节点，记录该信息的数据结构可以称之为拓扑结构表。拓扑结构表通过节点在自己时隙上发送自己的邻节点信息来更新，拓扑结构表的数据结构如图2所示。

图2拓扑数据结构示意图
Fig.2The topology of data

说明：

DN:记录拓扑信息的目的节点，常用bit位数表示，长度为节点号取对数，若网中最多32个节点，则DN占用5bit；

Next:记录到达该目的节点的中转节点，如果是一跳节点则该项还是本节点，常用bit位数表示，长度为节点号取对数，若网中最多32个节点，则Next占用5bit；

Metric:记录该节点是一跳节点还是多跳节点，若因网中最大6跳，则Metric占用3bit；

Seq:路由序列号，用来避免路由环路，最大63，即占用6bit；

Stable:记录该节点的存在时间(为了能较及时的感知节点丢失)，最大31，则占用5bit。

4)数据：待发送数据。

2.2系统同步过程

1)系统初始同步过程。每个节点开机后都先侦听周围节点的同步头信息从而获得同步定时，根据预先的分配占用时隙。如果在一个时帧的时长范围内，没有收到其他节点的消息，则退避任意时长后在预先分配给自己的时隙中发送自己的数据帧。而如果在退避的时间里收到其他节点的消息，则同样获得同步定时。具体流程如图3所示。

图3　初始同步流程图Fig.3　The flowchart of initial synchronize

获得初始同步后，节点在预先分配好的属于自己的时隙上发送数据帧，而在其他节点的时隙上接收数据，根据收到其他节点同步头信息来估计的两节点之间的传输延时和本节点与其他节点的时隙差距来调整自己的同步定时。

2)系统时间和路由维护过程。在不是全连通的网络中，所有节点之间不一定都是1跳可达的，有多跳节点的存在。为了保证每个节点传输，其他节点都能收到，则需要有节点对1跳不可达的节点进行中转，为了确定由哪些节点对数据进行中转，则需要每个节点都能实时的掌握网络的拓扑结构，且因为根据TDMA协议设计的需求，每个节点在自己的时隙上需要发送数据帧以便其他节点进行对时，在这种情况下，节点在自己时隙上，不论有没有数据要发送，都发送拓扑信息。具体可分为：

① 系统时间和路由更新策略。为了能使各节点快速的掌握网络的拓扑信息，节点在自己的时隙上发送自己数据帧信息。节点没有数据发送情况下，每个时隙上只发送同步头和路由信息，而如果有数据发送时，则发送完整数据帧信息。节点收到路由信息，比较收到信息的序号和自己路由表中的序号(目的节点相同)，选择序号大的路由信息更新拓扑结构表，当序号相等时，选择跳数小的信息。

② 节点序号的更新和维护。在拓扑结构表中给每个路由选项都设定一个序列号，即Seq。系统的启动时间为起始时间，对应的Seq为0，以后每过一个同步周期，序号加2。当发现路由节点不可达，就将序号加1(此时是奇数)。则根据序列号节点就很容易的识别哪条信息更新、更能代表当前的网络拓扑结构。

③ 中转节点选择。节点有数据要发送时，首先看网络中有没有和自己多跳的节点，如果没有则将中转节点个数置为0直接发送出去，如果有和自己相距为n跳的节点，则在自己的拓扑结构表中查找去往该多跳节点的中转节点，寻找中继节点的时候尽量找下一时隙和自己的时隙离的近的节点，以便减小延时。

3　理论计算仿真及实物验证

基于数据包头的时间同步算法采用的是异步组网模式，不需要全网精确同步，只需在节点时隙上维护网络粗同步及在节点间数据交互前完成相互精确同步即可，完全无需中心节点。由于采用的同步方法是基于TDMA多址接入技术，在不考虑图1中数据帧中时隙保护大小影响的前提下，采用多个独立的、有休假的、单个输入随机输出确定排队模型进行分析。令D为系统延时，则有：

(1)

其中，m表示用户数，S表示归一化的最大吞吐量即系统效率，为单位时间内系统实际传输业务量与信道允许的最大业务量之比。从上式可以看出系统时延D随S增大而增大。

设定信道总容量为C(bit/s)，每个用户的分组到达率为λ(分组/s)，数据帧即一时隙内发送数据的固定长度L(bit)，分组的服务时间即一帧内一个时隙的宽度τ = L/C。根据S的定义：

(2)

从上式可以看出，在信道总容量C一定的情况下，系统效率随分组的固定长度的增加而增加。由于本时间同步算法利用了分组数据来发送同步头和路由信息，因而数据帧中有效数据减少，导致系统效率降低。在数据帧长度为L(bit)中，设同步头和路由信息占用L1(bit)，有效数据为L2(bit)，则：

(3)

将式(3)代入式(2)后得到：

(4)

从上式明显看出，系统效率S随同步头和路由信息占用L1增大而减小，并乘系数变小。利用Matlab仿真工具，在用户数m为16和32的情况下分别进行仿真验证,仿真结果如图4～5所示。

图4　时延-吞吐量特性Fig.4　Time-delay Vs.throughput

图5　同步路由开销与吞吐量关系Fig.5　Cost of route Vs.throughput

从图4、图5可以看出，由于同步路由信息占用了数据信息位，降低了系统吞吐率，并随着节点数的增多，系统吞吐率下降。但同时，随着系统吞吐率的减小，带来了时延的减小。

为了验证基于数据包头的时间同步算法在实际中的性能，我们将此算法应用在了某通信系统中并进行了组网、信息传输测试。该通行系统要求16个用户间实现话音及数据传输。系统参数如下：系统总带宽C = 242.2kbit/s，m = 16，λ = 1，L = 2.4kbit，支持单跳，同步和路由同步开销L1= 100bit(其中DN占用4bit，Next占用4bit，Metric占用1bit，Seq占用6bit，Stable占用5bit，同步信息占用80bit)。通过反复验证和实验，系统同步稳定可靠，系统吞吐率达到0.8以上，效果良好。目前该算法已成功应用于某型产品中并已定型。

4　结　论

本文对TDMA多址接入的同步算法进行了论述，并提出了一种完全无需中心的全网同步方法，该方法将同步头、路由和数据信息组成新的数据帧，利用数据帧发送的同时完成节点相互同步，只需实现节点相互同步，而无需全网同步。与传统的TDMA协议相比，其时延小，抗毁性明显增强。同时，由于同步路由占用数据信息位，降低了系统的吞吐率；节点越多，系统的吞吐率也越低。因而该方法适用于节点数不多的小型网络，可以完全满足TDMA组网要求。

[1]于弘毅.无线移动自组织网[M].北京：人民邮电出版社，2005:11-14.

[2]郑相全.无线自组网技术实用教程[M].北京：清华大学出版社,2004:3-4.

[3]刘庆刚，李大双，朱家成.多跳TDMA组网同步的分布式控制方法[J].通信技术，2012，45(05)：26-32.

LIU Qinggang,LI Dashuang,ZHU Jiacheng.A distributed method of synchronization control in multi-hop TDMA network[J].Communications Technology,2012，45(05)：26-32.

[4]CARLOS H R,THOMAS K.A mutual network synchronization method for wireless ad hoc and sensor networks[J].IEEE Transactions on Mobile Computing,2008,7(5):633-646.

[5]THAKER S S,NANDI S,GOSWAMI D,et al.Clock synchronization in IEEE802.11 ad hoc networks[J].Lecture Note in Computer Science,2004,3356(1):180-189.

[6]CHEN G N,WANG C Y,HWANG R H.Muti-hop time synchronization protocol for IEEE 802.11 wireless ad hoc network[J].Lecture Note in Computer Science,2006,4138(1):664-675.

[7]WANG C Y,WU C J,CHEN G N.Efficient power saving protocol for multi-hop mobile ad hoc networks[C]//Third IEEE International Conference on Information Technology and Applications,Sydney,2005:271-276.

[8]张晓辉，刘丁.基于分层结构的可变网络时延补偿方法研究[J].西安理工大学学报,2012,28(3):258-263.

ZHANG Xiaohui,LIU Ding.Research on compensation method of variable network time delay based on layered structure[J].Journal of Xi'an University of Technology,2012,28(3):258-263.

[9]ZHONG X F,WANG Y Z,MEI S L.Synchronization in TDMA ad hoc network[C]//Wireless Technologies for Global Security,Los Angeles,USA,IEEE,2005,7(2):5011-5014.

[10]徐明霞.Ad hoc 网络中的时分多址接入及跨层设计研究[D].杭州:浙江大学,2007.

XU Mingxia.Research on TDMA and cross layer design of Ad hoc[D].Hangzhou:Zhejiang University,2007.

[11]杨勇.一种等级化分布式时间同步算法[J].现代电子技术,2013,36(17):37-40.

YANG Yong.A hierarchical distributed time synchronization algorithm[J].Modern Electronics technique,2013,36 (17):37-40.

[12]ZHOU D,HUANG L F,LAI T H.On the scalability of IEEE 802.11 ad-hoc-mode timing synchronization function[J].Wireless Network,2008,14(4):479-499.

[13]HOFMANN B,LICHTENEGGER H,COLLINS J.Golbal position system:theory and practice[M].Berlin:springer Verlag,1997:1-20.

[14]FUKS H,LAWNICZAK A T.Performance of data networks with random links[J].Mathematics and Computers in Simulation,1999,51:101-117.

[15]MITTAL S,PINKI E.Performance evaluation of AODV,DSR,DSDV and TORA routing protocols[J].International Journal of Multidisciplinary Research,2012,2(2):214-221.

(责任编辑杨小丽)

A synchronizing algorithm for Ad Hoc Network based on data frame

YANG Yong1,2，ZHANG Fuqin1,2，ZHANG Fan1,2

(1.Shaanxi Fenghuo Electronics Co.,LTD,Xi’an Institute of Technology,Xi’an 710075，China)(2.Xi’an Fenghuo Electronic Technology Limited Liability Company,Xi’an 710075，China)

Ad Hoc Network is a kind of mobile communication network which has no central nodes and can be established at anytime and anywhere.It has the advantage of simple,fast organization and no geographical restrictions.However,application of the Ad Hoc is restricted greatly by the complex problem of synchronizing among different node.To solve this problem,a synchronizing algorithm for Ad Hoc Network based on data frame is proposed.The new algorithm utilizes the data frame composed of synchronize package,route information and data information to process the synchronization among different nodes.The simulation and experimental results show that the proposed algorithm has the character of low time-delay and anti-destroying and make a fundament for application of the Ad Hoc.

Ad Hoc Network; TDMA(Time Division Multiple Address); slot synchronize.

10.19322/j.cnki.issn.1006-4710.2016.01.019

2015-09-20

陕西省科学技术研究发展计划资助项目(2012K06-03)

杨勇，男，高级工程师，研究方向为无线通信系统设计和电台设计。E-mail:yong0406@163.com

TN929.5

A

1006-4710(2016)01-0106-04