（通信与信息系统专业论文）士兵电台mac层协议的设计与实现(1).pdf

摘要 随着信息技术的不断发展，人们对无线通信的需求越来越强。近年来，移动 通信技术得到了飞速的发展和普及，各种新的技术纷纷涌现。a dh o c 网络作为一 种特殊组织形式的网络，在军事、民用领域得到了广泛的应用。它使用方便、灵 活、快速，但是它无中心、无组织性、动态变化的拓扑结构，使得它在应用过程 中有很多工作去做。 本文根据实际的网络要求，在研究已有协议的基础上，设计了一种适合自己 网络的m a c 协议。我们首先对其帧结构进行了描述，详细地讲述了它的工作原理； 然后我们对协议的整个工作流程，各个模块给出了相应的设计；最后我们描述了 了协议具体的实现方法和其中遇到的问题以及注意事项，这有助于我们对类似问 题的研究。 关键词：移动自组织网媒质介入控制时分多址接入a r ml i n u x a b s t r a c t p e o p l e sd e m a n do nm o b i l ec o m m u n i c a t i o ni n c r e a s e sw i t ht h er a p i dd e v e l o p m e n t o fi n f o r m a t i o ns c i e n c e i nt h er e c e n ty e a r s ，m o b i l ec o m m u n i c a t i o ni sd e v e l o p i n gv e r y q u i c k l y a sas p e c i a ln e t w o r k ，a dh o en e t w o r ki sw i d e l ya p p l i e di nm i l i t a r ya n dc i v i l d o m a i n a dh o cn e t w o r kh a si t sc h a r a c t e r i s t i c so fc o n v e n i e n c e ，a g i l i t ya n ds p e e d i n e s s b u ti t sa c e n t r i c ，i n o r g a n i z a b l e ，d y n a m i ct o p o l o g ys t r u c t u r em a k e st h a tt h e r ei sal o to f w o r k t ob ed o n e i nt h i sp a p e r , a c c o r d i n gt ot h ep r o p o s e dr e q u i r e m e n to ft h en e t w o r k ，w ed e s i g na m a c p r o t o c o lf o ro u ro w nn e t w o r k f i r s t l y , w ea n a l y z et h es t r u c t u r eo fi t sf r a m ea n d t e l lo ft h et h e o r yo fh o wi tw o r k s ；s e c o n d l y , w ea n a l y z et h ef l o wa n dd e s i g nt h em o d u l e s o ft h ep r o t o c o l ；a tl a s t ，w et e l lo ft h ec o n c r e t em e t h o dt h a th o wt oi m p l e m e n tt h e p r o c o t o la n dt h ep r o b l e m st h a th a v eb e e nm e ta n ds o l v e d t h i sc a nh e l pu st os o l v et h e s i m i l a rp r o b l e m s k e y w o r d s ：m o b i l ea dh o en e t w o r k m a ct d m aa r ml i n u x 第一章绪论 第一章绪论 1 1 引言 随着信息技术的不断发展，人们对移动通信的需求越来越强。近年来，移动通 信技术得到飞速发展和普及。人们使用无线终端( 手机、p d a 、笔记本等) ，通过固 定的有线基础设施( 基站等) 来实现移动通信。但对于某些特殊场合，不可能有这种 预先部署的固定设施可以利用。比如，战场上部队快速展开和推进、发生地震或 水灾之后的营救、野外科学考察、偏远山区、临时会议等。在这种情况下，一种 特殊的网络，移动自组织( a dh o c ) 网络应运而生。移动自组织网不需要有线基础设 施的支持，各个主机之间通过彼此组成的网络来实现通信。 目前a dh o c 网络已经得到了国际学术界和工业界的广泛关注，并正得到越来 越广泛的应用，已经成为移动通信技术向丽发展的一个重要方向，并将在未来的 移动技术中占有重要地位，而其中军事应用是移动自组织网技术的主要应用领域。 因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字化战场 通信的首选技术，并已经成为战术互联网的核心技术。为了满足信息战和数字化 战场通信的首选技术，并已经成为战术互联网的核心技术。 移动自组织网没有固定的基本结构，随着节点的移动、入网或者退网，网络的 拓扑和规模都会发生相应的变化。因此，如何解决移动自组织网中的传输调度问 题成为目前研究的热点。最初，人们把c s m a 应用于移动自组织网中的m a c 层 进行接入控制，但是该协议对于业务类型的区分和业务的q o s 控制能力较差。后 来，人们发现，在移动自组织网中，彼此充分分离的不同节点可以使用相同的时 隙而彼此互不干扰，因此，该网络允许空间上的t d m a 时隙复用。而且，采用t d m a 可以有效地进行资源管理，但静态地t d m a 效率很低，而且很难使用网络规模地 动态变化，对移动性支持较差。于是，移动自组织网中的动态t d m a 协议引起了 人们越来越朵的关注，也逐渐成为目前人们研究的热点。 1 , 2 士兵电台的m a c 协议 移动自组织网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) ，对分组无线网的 研究源于军事通信的需要。早在1 9 7 2 年，美国的d a r p a 就启动了分组无线网项 目p r n e t ，研究在战场环境下利用分组无线网进行数据通信。在此之后，d a r p a 于19 8 3 年启动了高残存性自适应网络s u r a n ( s u r v i v a b l ea d a p t i v en e t w o r k ) 项目， 2士兵电台m a c 层协议的设计与实现 研究如何将p r n e t 的研究成果加以扩展，以支持最大规模的网络。1 9 9 4 年，d a r p a 又启动了全球移动信息项e l ( g l o b a lm o b i l ei n f o r m a t i o ns y s t e m s ) 项目，旨在对能够 满足军事应用需要的、高抗毁性的移动信息系统进行全面深入的研究。成立于1 9 9 1 年的i e e e 8 0 2 1 1 标准委员会采用了“a dh o e ”网络一词来描述这种特殊的自组织对 等多跳移动通信网络，a dh o e 网络( 即移动自组织网) 就此诞生。 由于最初的动机之一就是满足战场生存的军事需求，因此，从2 0 世纪7 0 年 代到9 0 年代早期，我们很难从公开刊物获得有价值的理论和技术成果。随着移动 自组织网在警察与医疗部门的抢险救灾、传感器网络、等众多领域的应用，到了 9 0 年代中期，随着一些技术的公开，a dh o e 网络开始成为移动通信领域一个公开 的研究热点。于是，越来越多的应用于移动自组织网的m a c ( 媒质介入控制) 协议 涌现出来。到目前为止，移动自组织网的m a c 协议基本上有两大类。 ( 1 ) 随机访问协议 随机访问协议又包括：c s m a c a 随机访问协议、m a c a 协议、时隙a l o h a 竞争访问协议等。这一类协议都是为了解决随机竞争时的冲突和碰撞问题，适合 于对数据的传输。但是这一类协议很难为特定的业务划分相应的带宽，对语音和 数据、同步和异步混合的业务流的服务质量保证很差。 ( 2 ) 链路组织协议 链路组织协议主要是t d m a 协议，该协议中根据时隙分配方案的不同划分为 全分布无中心令牌环控制、全分布无中心无冲突矢量时隙分配法、有中心分群控 制法、时隙窗选择法。这一类协议对不同业务流的服务质量保证较好，并且能够 适应网络拓扑的变化，对移动性的支持比较好，时目前研究移动自组织网中m a c 协议考虑的主流方向。 因此，本文将根据我们网络的需求，设计一种最适合我们自己的动态的t d m a 协议，并详细论述该协议的实现过程。 1 3 本文研究的主要内容 本文首先概述了动态t d m a 技术在移动自组织网中的重要性以及优势所在。 在第二章中，主要阐述根据m a c 层协议的设计要求，分析设计过程以及其中的难 点，最后对我们设计的m a c 协议的原理进行了描述，对可行性及优越性进行了分 析，对工作流程进行了细化，对各个模块的调度进行了描述。第三章中描述了整 个系统的设计，交叉编译的环境的建立过程，l i n u x 内核的编译等，以及协议的实 现方法、应该注意的问题、测试结果。第四章，结束语。 第二章m a c 层协议的设计及j r 作原理 第二章m a c 层协议的设计及工作原理 本章主要阐述根据m a c 层协议的设计要求，分析设计过程以及其中的难点； 然后对我们设计的m a c 协议的原理进行了描述，对可行性及优越性进行了分析； 最后，描述了发送和接收的流程和各个模块之间的调度。 2 1 设计要求 2 1 1 士兵电台的动态t d m a 协议设计要求 通过上面对各种移动自组织网下的动态t d m a 的研究和分析，我们可以得出 在a dh o c 网络中设计一个动态t d m a 方案要考虑的问题，这是设计动态t d m a 协议需要满足的最基本的条件： ( 1 ) 怎样动态分配时隙是最关键的问题。这既要保证每一个已入网的节点可以 按照其传输业务的多少获得合理时隙传输，又要保证每一个请求入网的节点快速 有效的接入网络并且在已有的时隙分配方案的基础上获得自己相应的时隙。 ( 2 ) 在传输的基本问题上，就要考虑使用t d m a 的条件下，节点不能同时收发 ( 无初级冲突) ，并且一次不能接收大于一个包( 即无二次冲突) 的问题。即从发送方 来说，如果我们不考虑捕获的影响，当节点发送一个包给邻居节点时，它就阻塞 了所有其它邻居节点接收其它源的包。从接收方来看，要成功的接收一个包，就 要组织除指定的发送节点发送以外的所有节点进行发送。在多跳的网络中实施这 样的方案是需要技巧的，这就要我们设计协议的时候给予充分的考虑。 ( 3 ) 合理而有效的解决隐藏终端的问题。根据无线传输的范围有限，两个节点 可能足够的远以至于相互之间直接发现不了对方的存在，但是它们可能会在中间 的另一个节点发生碰撞，即使是在i e e e 8 0 2 1 1 协议中用到的四次握手协议也不能 完全阻止这种碰撞。因此这是移动自组织网中必须解决的一个重要问题。 ( 4 ) 对网络移动性的支持。由于移动自组织网中各个主机的自主性，使得网络 的拓扑结构的不断变化，那么动态t d m a 协议应该可以随着这些变化调整自己的 时隙分配方案，从而保证网络对移动性的支持。 ( 5 ) 协议执行时的公平性。一个协议的另一个重要的衡量标准就是保证网络中 的各个节点在有业务要发送的时候要可以获得机会均等的传输机会，不能因为节 点在网络中的位置不同而造成节点之间的不平等。 ( 6 ) 协议的q o s 。所设计的协议要使得网络能动态的满足业务流的带宽需求， 4 十兵电台m a c 层协议的设计与实现 高优先级的业务要能有更大的权力来获得带宽，这是设计动态t d m a 协议时必须 考虑的问题，也是最难解决的问题。 2 1 2d t - t d m a 协议的设计要求 根据系统的要求，我们对我们的动态令牌( d t - t d m a ) t d m a 协议提出以下设 计要求： ( 1 ) 支持两种组网方式 典型组网方式 单基站有中心网络，实现多个移动用户设备围绕这个中心组成无线局域网， 以及移动用户之间通过基站转接进行语音通信。 无中心自组织网络 在没有基站或基站失效的情况下，系统应具备自组织网的能力，各个设备之 间能够以自组织网络的形式进行通信。 ， ( 2 ) 要求该协议能支持动态拓扑变化 在网络有中心节点的情况下，由中心节点对该局域网内的其它节点进行协调。 当节点失效或被毁，整个网络要快速转化为白组织网络。 ( 3 ) 要保证语音和数据的传输 语音属于同步业务，对q o s 要求较高；数据传输属于异步业务，对时延要求 不高。 另外，该协议针对的网络用户数在1 6 个左右，单跳的通信距离为l 公里左右。 该协议适用于用户数相对较少，通信距离不大于三跳的网络中，由此我们设 计了d t o t d m a 协议。 2 2d t - t d m a 协议设计的难点和分析 2 2 1 实现m a c 层的主要功能 动态令牌t d m a 协议能够完成的功能如下： ( 1 ) 完成新用户设备的接入。 ( 2 ) 给每一个用户都能分配相应的时隙， ( 3 ) 可以进行资源预约。 ( 4 ) 具有带宽管理的功能。 ( 5 ) 能够提供q o s 保证。 ( 6 ) 在整个协议的运行过程中，能够维持网络同步。 第二章m a c 层协议的设计及工作原理 2 2 2 设计难点 经过以上分析，我们看到在有中心的网络中很容易保证资源被合理分配，关 键是要提高系统的抗毁性，就必须保证a dh o e 模式下正常传输。这样要设计该协 议就有几个理论难点【1 7 】【1 8 】需要解决： ( 1 ) p h 何在a dh o c 模式下既保证语音传输的实时性，又保证流业务和数据高效 传输，这也就是q o s 问题。 ( 2 ) 自组织网为了维持拓扑信息的及时更新，要定期发送自组织信息，如何 发送自组织信息，一方面不能带来太大的丌销，自组织信息收集周期可以调节， 领一方面自组织信息的发送不能与j 下常通信发生冲突。 2 2 3 设计分析 在第一章绪论中我们提到，在链路组织协议中的全分布无中心令牌环【2 】 1 5 】【1 9 】 控制法适合于较小规模的自组织网络，且对移动性支持较好。因此我们的 d t - t d m a 协议拟选定该方法来实现m a c 接入协议。 令牌环自组织网协议又可以分为固定帧长的令牌环协议和可变帧长的令牌坏 协议。 固定帧长的令牌环协议需要精确的全网定时来保证令牌的传输无误，在这个 网络中各个节点的通信信标信息来是否自己活得令牌。 可变帧长的令牌环协议需要传输专门的令牌来保证各个节点得到发送权。可 变帧长的令牌环协议中令牌的传递规则是协议的关键。令牌的传递又分为令牌环 传递和令牌随机传递。 令牌传递需要各个节点参与令牌环并在该环中找到自己在令牌环中的上一节 点和下一节点。为了保证令牌的稳定传输还需要发送令牌请求包和令牌确认包。 这种方式的令牌传输时延大，需要较多的信息来维持令牌的传输，但很稳定，令 牌不易丢失。 随机令牌传递是由令牌发起节点发起令牌的传输令牌传输给这个节点的邻居 节点，再由这个节点的邻节点传给其它的邻节点，令牌随机传递不用为令牌的传 输维持环路，令牌从一个节点传输到下一个节点的顺序完全是根据网络拓扑动态 改变的。令牌随机传递的规则可以是链路数最小的节点优先获得令牌，也可以是 链路数最大的节点优先获得令牌，也可以是两种规则交替进行，以保证网络中各 个节点的公平性。令牌每传递一周令牌序号加，令牌记录曾经获得者和未获得 者名单，当网络中所有的节点都被记录到其中，则令牌传回，开始下一轮的令牌 传输，这种随机传输方式在一般情况下传递很快，不需要为维持令牌而花费额外 6 士兵电台m a c 层协议的设计与实现 的开销，但令牌容易丢失，如何保证所有节点都能获得令牌、令牌丢失的监测和 再生、如何防止令牌死循环传输是问题的关键。 我们结合以上协议提出动态令牌t d m a ( d t - t d m a ) 协议，该协议选用令牌随 机传输的方式来提高系统容量，运行效率高、稳定可靠，很适合小范围的移动自 组织网络。协议采用令牌传输的机制来实现各个节点动态讲令牌传输到邻节点的 邻节点，令牌这样一级一级的传递，直到一个节点的所有邻节点都获得令牌，则 终止令牌传输。发起令牌的群首在网络各个用户中动态选择，每4 0 m s 为一周，更 换一次群首。群首的更换以定时为基准，各个用户根据收到的最新的动态群首链 信息和上一次勤务跳来决定自己在何时发起令牌。协议根据简单、可靠、易于实 现的原则来设计。 2 3d t - t d m a 协议的描述 2 3 1 帧结构设计及参数设计 本协议的帧结构2 2 】1 3 1 1 分为超帧、t d m a 帧、用户时隙、微时隙这四个层次。 帧的层次关系如下图2 1 所示。 关于帧结构的说明： ( 1 ) 超帧： 超帧是由6 6 个t d m a 帧所组成的。前两个帧给系统保留，用作并网帧听。 后6 4 个t d m a 帧留给用户用于正常传输。每个t d m a 帧占用固定的时长为4 0 m s 。 相当于每2 6 4 0 m s 中留出8 0 m s 用于并网帧听。因为每一个t d m a 帧都会有一次勤 务跳，因此8 0 m s 内至少可以接收到一次完整的勤务跳。并网用户就可以利用接收 到的勤务跳信息来进行并网。 ( 2 ) t d m a 帧 t d m a 帧的帧长是固定的，在一个t d m a 帧内网内的令牌传递一周。每一个 t d m a 帧内选取一个群首，群首首先发起令牌，再按照随机令牌传递的规则将令 牌传递给它的邻节点，邻节点再将令牌传递给另一个邻节点。令牌传递的规则是 按照随机令牌传递规则，令牌的随机传递按照链路数最大的节点优先传输，或链 路数最小的节点优先传输，也可以按照两种规则交替传输，这样可以有利于保证 各个节点的公平性。下一个t d m a 帧要更换群首，这样就不会出现网络过分依赖 某一个节点，有利于提高网络的抗毁性。每一个节点发送数据的时候，会把动态 群首链信息也广播出去，其他节点根据当前群首和动态群首链信息来判断下一个 t d m a 帧的群首是谁。下一个群首根据收到的上一次勤务跳，来决定自己应该在 第二章m a c 层协议的设计及工作原理 超帧 n 一。 ， i2 3 4 j “6 56 6 一1 0 m s ；x ，i s l 。l 1 6 | - t 加is i l i 拍li b o 二二二二二2三二!三刿动态群首发送h、-：j8：ivs二ms：、一飞，i -233 23 3 l 1b 一 夕 ， 用户微时隙 、 023ms ， 5 2 4 b i t q k 务信息( 语爵或数圭i ) 图2 1d t - t d m a 协议的帧结构 什么时候发起勤务跳，然后发起下一个t d m a 帧的令牌。 本系统设定跳速为4 0 0 0 跳秒，每一跳为一个微时隙，在一个微时隙内没有收 发转换，这样便于物理层的调制和解调，每一个微时隙占用0 2 5 m s 。每一个t d m a 帧内包括1 6 0 个微时隙，其中前8 个微时隙用于由动态群首发起勤务跳，紧接着 的8 个微时隙用于迟入网用户发送入网请求。剩余的1 4 4 个微时隙，根据用户需 要动态组合。群首首先发起一个令牌，根据令牌，群首的邻节点得知下一个获得 令牌的用户是哪一个节点，同时在令牌头中，群首也会根据业务需要指出自己占 用多少个微时隙。当令牌传递到下一个用户的时候，下一个用户根据需要占用一 定的微时隙，再将令牌一个节点一个节点的向下传递。若一个用户无数据要发送， 则只发送一个令牌报头，即将令牌传递给下一个节点，令牌的传输不需要a c k 。 一个t d m a 帧的长度固定为4 0 m s ，即便令牌传输完毕，没有数据要发送也不能开 始下一个t d m a 帧，只有当时间到达4 0 m s 的时候才可以开始下一个t d m a 帧。 ( 3 ) 用户时隙 在一个t d m a 帧中，一个用户获得令牌即获得发送权。从一个用户获得令牌 开始发送数据到结束发送数据称为一个用户时隙。在这个时间段内，只有一个用 户发送数据，其他用户都处于接收状态，因此称为用户时隙。一个用户时隙是由 多个微时隙所组成的，用户根据自己业务量的多少，决定占用微时隙的多少，用 士兵电台m a c 层协议的设计与实现 户在一个用户时隙内最多占用5 1 2 k b p s 的带宽，因此用户占用的时隙数不得超过 3 3 个微时隙，即3 3 跳。每一个用户时隙的第一个微时隙用于发送一个大报头，这 个大报头内包含的主要信息为如下格式( 总共占掉2 4 7 个b i t ) ，如图2 2 所示。 帧同步l 帧类型i 令牌序列号i 令牌传递信息l 网络号i 当前群首信息 1 3 b i ti4 b i t6 b i tl4 b i t8 b i t4 b i t 微时隙占用信息l 动态群首链l 动态链表信息 8 b i t i 8 0 b i t1 2 0 b i t 图2 2 令牌控制信息的格式 帧同步是1 3 b i t 的巴克码，用于给用户指示这一帧的开始。帧类型用来标示这 _ 帧是什么类型的。令牌序列号是用来指示令牌位于超帧中的哪一个t d m a 帧， 每一次发起令牌，令牌序列号都要在上一次的基础上加l ，当令牌序列号为全1 时， 即令牌已经传输了6 4 周，则留下两帧的时间用于并网帧听，然后将令牌序列号清 零，重新开始记数。其中令牌传递信息占4 b i t ，4 b i t 可以标示1 6 个用户，令牌传递 信息用来给其他节点指示令牌下一步传递给谁；网络号表示目前该网络的编号是 几，用于避免很多用户之间的干扰，这样可以在有限范围内组网，可以按战术编 队组网等。用于当前群首信息也占用4 b i t ，用来标示当前这一个t d m a 帧内令牌 的发起者；微时隙占用信息表示该节点要占用多少个时隙。动态群首链最多有1 6 个用户，这1 6 个用户根据入网先后依次排列，这个顺序基本上不变，除非有新节 点加入和节点离开网络，顺序才会发生改变。各个用户根据当前群首、勤务跳的 定时信息、动态群首链联合起来决定下一个t d m a 帧中谁来发起令牌，如图2 3 所示。 n a ls 1n a 2s 2n a is il i n kt a b l e 4 b i tl b i t4 b i tl b i t4 b i tl b i t1 2 0 b i t 动态群首链动态链表 图2 3 动态群首链的结构 n a l ：节点l 的地址s 1 ：节点1 的状态 n a 2 节点2 的地址s 2 ：节点2 的状态 n a i 节点i 的地址s i ：节点i 的状态 s i ：共1 个b i t ，0 表示未获得令牌，1 表示已经获得令牌 i ，玳kt a b i e ： t a bn a ln a 2n a i n a lo l 0 n a 21o l 第二章m a c 层协议的设计及工作原理9 n a iolo 幽2 4l i n k t a b l e 图2 4 是一个能表示双向链路的链路表，图中的l 表示有连通，0 表示无连通， 由于系统最大支持1 6 个节点，而且不分群，因此每个节点都有必要维持一个整 个网络的连通表。若认为双向链路中的上下行链路一般情况下通断情况相同，则 可以采用上三角矩阵，或下三角矩阵来表示连通情况。若采用全矩阵则要占用 1 6 1 6 = 2 5 6 个单元。若采用三角矩阵则要占用1 6 + 1 5 十+ 1 = 1 2 0 个单元 在这里每个节点的地址只有4 个b i t ，实际上这是一个逻辑地址，或者称为用 户的站号。用户的物理地址在网络中和逻辑地址是一一对应的，但在一个网络中 同样的逻辑地址只有一个，当用户入网和退网的时候，这个用户的邻节点会把物 理地址和逻辑号的分配对应信息，传递给其他节点。 ( 4 ) 用户微时隙 个用户微时隙为一跳，一个用户连续预约多个微时隙，由这多个微时隙组 成了一个信道，在这个信道内用户通过以下几种方式使用该信道。 ! 里塑量童重旦l 墼塑堡堡l 鍪塑l 垒堡鉴笪叠i 垒竺鉴 由微时隙组成的信道( 经过愉悦) 图2 5 用户微时隙的使用方式 在这个信道上用户只发送不接收，因此效率很高。 其中图中的t d m 语音复用结构、语音信标的结构、数据信标的结构、a c k 信标的结构分别如图2 6 、2 7 、2 8 、和2 9 所示。 图2 6 t d m 语音复用结构 帧同步帧类型源地址目的地址下一站地址帧长 c r c 1 3 b i t4 b i t4 b i t4 b i t4 b i t1 6 b i t3 2 b i t 图2 7 语音信标的结构 帧同步帧类型源地址目的地址下一站地址帧长 c r c 1 3 b i t4 b i t4 b i t4 b i t4 b i t1 6 b i t3 2 b i t 图2 8 数据信标的结构 f 帧同步 帧类型 源地址目的地址下一站地址c r c | 1 3 b i t 4 b i t4 b i t 4 b i t 4 b i t3 2 b i t 图2 9 a c k 信标的结构 这里的a c k 是用于对上一次该节点收到的数据的响应。 1 0 十兵电台m a c 层协议的设计与实现 2 3 2 自组织网的建立( 邻居的发现、拓扑的生成、令牌发起者的选择) 假设各节点的分布情况如图2 1 0 所示。 4 g 图2 1 0 网络的拓扑图 ( 1 ) 网络的建立过程： 当网络刚启动的时候，每一个节点都不知道自己的邻节点有哪些，也不知道 整个网络的拓扑。但最先开机的用户( 0 用户) 会检测信道一个超帧的时f b j ( 2 6 4 0 m s ) ， 在2 6 4 0 m s 内没有检测到任何无线电活动，那么该节点( o 节点) 就为群首发起令牌， 这时因为网络中只有二个节点，因此获得令牌得节点( 0 节点) 也无数据要发送，这 时只发送一个t d m a 帧的帧头，用于通知其他用户网络中该节点的存在。当其它 用户收到该节点发出的信息，就知道这时网络中已经有节点发起令牌，其它节点 在t d m a 帧中的迟入网申请时隙内选择一个时隙发出请求入网信号。请求入网信 号的格式如图2 1 1 所示。 帧同步请求入网节点的物理地址 c r c 1 3 b i t3 2 b i t1 6 b i t 图2 1 i 入网请求信号结构 其它节点接收到这个节点发出的请求入网信号，只有群首给出回应，群首负 责给这个节点分配相应的逻辑号，并将这个分配信息作为数据发送给新入网的节 点，当新入网的节点收到这个信息的时候，首先取出自己的逻辑号，然后取出大 报头中的拓扑信息。其他节点收到邻节点的t d m a 帧头，然后取出其中的拓扑信 息，更新自己的网络拓扑。 入网回应信息的格式如图2 1 2 所示。 帧同步 帧类型 逻辑号 物理地址c r c 1 3 b i t4 b i t4 b i t3 2 b i t1 6 b i t 图2 1 2 入网回应信息的格式 第二章m a c 层协议的设计及工作原理 ( 2 ) 令牌的传输： 令牌在网络中传输要遵循一定的规则。本方案按照随机令牌传递的规则，不 用维持令牌环而花费额外的开销。假设网络中各节点的拓扑结构如图2 1 0 所示。 群首按定时关系发起一个令牌，令牌在网络中传输的规则分为链路数大的优 先传输和链路数小的优先传输两种情况，为了保证网络的公平性，同时也为了避 免令牌的传输带来过大的网络流量，本协议设计令牌的传输顺序为两种规则交替 进行。群首产生一个新令牌，令牌序列号加l 。群首是动态变换的，每一个用户根 据当前群首和收到的群首链的信息来判定自己是不是下一个群首，如果是，则根 据定时关系在下一个t d m a 帧中发起令牌，如果不是则等待别的节点将令牌传递 给自己。动态群首链信息除了有新节点加入和节点离开时，一般不变，动态群首 链中的各个节点也不一定是邻节点。动态群首链在每个节点发出的大报头中都含 有该信息，这样该节点的邻节点就可以接收到该信息，因此网络中的每个节点都 可以获得网络中的最新的动态群首链信息。 令牌从0 节点出发后按照链路数最小或最大的节点优先获得令牌的原则传递 令牌，已经获得过令牌的节点( 动态群首链中节点状态s i 为1 ) 不再获得令牌， 算法在剩余的未获得令牌的邻节点( 动态群首链中节点状态s i 为0 ) 集中计算选 出令牌要传递的下一个节点，当出现获得令牌的邻节点有两个节点链路数相同， 选择序号较小的节点传递令牌；当一个节点的所有邻节点都已经获得过令牌，但 是动态群首链中依然有节点没有获得令牌，则先将令牌传递给中继节点，然后在 传递给该节点，当动态群首链所有的节点都已获得过令牌，或一个t d m a 帧的定 时到，则终止令牌的传输，开始下一个t d m a 帧。 在图2 1 0 中各节点的链路数如图2 1 3 所示，小括号内是该节点的链路数。 数。 4 ( 3 图2 1 3 各个：肖点链路示意图 则令牌从0 出发后，应该按照以下次序传递令牌，小括号内是该节点的链路 1 2 士兵电台m a c 层协议的设计与实现 0 ( 5 ) - - - ) 9 ( 3 ) - - 1 ( 4 ) - - ) 3 ( 3 ) - - ) 4 ( 3 ) - - ) 5 ( 4 ) - - ) 6 ( 3 ) - - ) 7 ( 4 ) - - - ) 8 ( 5 ) - - ) 2 ( 6 ) 这种令牌传递方法，使得令牌在网络中每次传输均能按最小跳数传输，大部 分情况下，令牌只需跳即可传输到下一个节点。而且这种方法对网络的拓扑变 化适应性较好，令牌不用按照固定的线路去传输。当令牌在传递过程中不能一跳 直接传输到目的节点，那么发送令牌的节点就在本节点的拓扑路由表中查找该节 点的位置，并通过中继节点将令牌传递给下一个节点。 下面我们考虑在出现以下情况的时候按照本令牌算法，令牌的传递规律。 图2 1 4 情况一下的拓扑结构 2 啦) 假设网络的拓扑结构如图2 1 4 所示，其中1 节点最先开机，l 节点发起令牌， 则令牌传递如下： 1 ( 2 ) - ) 2 ( 2 ) - ) 3 ( 2 ) - - ) 4 ( 3 ) - - ) 5 ( 3 ) - - ) 6 ( 2 ) - - ) 7 ( 2 ) - - ) 8 ( 2 ) 由此可见令牌按照较为高效的方式在网络中传输，而不用为了环路维持开销。 牌。 l 瞧) 2 娌)3 ( 3 )4 眨) 5 ( 1 ) 图2 1 5 情况二下的拓扑结构 假设网络的拓扑结构如图2 1 5 所示，其中4 节点先开机，则4 节点先发起令 令牌传输按以下顺序： 4 ( 2 ) 专5 ( 1 ) 专4 ( 2 ) 【中继】专3 ( 3 ) 专1 ( 2 ) 专2 ( 2 ) 根据以上分析，我们看出这种令牌传递算法传输效率很高。 第二章m a c 层协议的设计及t = 作原理 ( 3 ) 自组织网拓扑的维持： 当网络建立起来，通过初始化j 下常运行以后，自组织网具有移动性 拓扑会经常发生变化，这种拓扑的变化如何能够及时被各个节点所感知就是 拓扑的维持问题。 假设一个节点的邻节点为一个集合附，e 】，在某一时刻，该节点发生移动，该 集合中的e 不再是该节点的邻节点，在这种情况下该节点依然能接收到某些节点 发出的信息，而却在连续几个t d m a 帧内不能接收到n 集合中的节点发出的信息， 这时说明这些节点已经不再是该节点的临节点。 另一种情况是集合中的e 被j 所代替，则集合变成 n ，j 】，则 兑明有一些新节 点变成了该节点的临节点，则该节点接收到j 中节点发出的信息时，就说明j 已经 变成自己的邻节点，则马上将j 置为自己的邻节点。 最极端的情况是集合i n ，e 5 h 的n 和e 都被另一个子集所代替，这时集合变成 i f , j ，则因为所有的节点都已经发生变化，因此该节点无法从别的节点处得到令牌， 但是因为t d m a 帧的群首是动态更换的，当轮到该节点充当群首的时候，该节点 就获得发送的机会，这样其他节点就可以感知到该节点的移动和存在。通过以上 分析我们可以看出，该协议较好的支持了移动性。 “) 令牌的合并、分裂、丢失和再生 首先考虑单个网络的情况，在一个正常工作的网络中，一个令牌从节点l 传 输到节点2 ，因为两种情况令牌传输可能出错，一是通信故障，可能是链路质量不 佳或者2 节点被打掉，二是2 节点发生了移动，则l 与2 之间变的不可直达，这 样令牌因为无法被接收到而发生丢失。为了应对这种丢失，就有必要加入令牌重 发或换发的机制。具体方法如下：首先若令牌被正确接收，则1 节点应该在1 传 输结束后的下一跳中马上听到2 发出的包头信息，若连续两跳没有任何回应，则 重发令牌，若重发2 次都没有任何回应，说明2 节点被打掉，或链路出现故障， 或该节点将令牌传递给其他的邻节点。若1 2 之间有故障，而2 与其他节点还能连 接的情况，或2 被打掉的情况下，若1 连续两个t d m a 帧没收到2 的回应，则将 1 2 链路置0 若所有与2 连接的链路都被置0 ，说明2 脱离网络，但是在动态群首 链中仍为它保留4 秒左右，4 秒以后从动态群首链中删除它，释放逻辑号资源。( 注： 逻辑号与物理地址的对应关系只有该节点自身知道，其他节点只知道有这样的一 个逻辑号) 当出现两个单独的网络要合并成一个网络的时候，假设由两个小网络l 和2 ， 且l 的规模比2 小。在并网的时候，首先1 或2 会在并网监听帧内收到另一个网 络的勤务跳，因为1 比2 的规模小，因此1 网络收到勤务跳的节点，改变跳频规 律与2 网络同步，不再参与1 网络的令牌传输，并在迟入网时隙内发出入网申请。 如此循环，l 中所有的节点都会打散并入2 网络。当两个网络规模相同时，首先监 1 4 士兵电台m a c 层协议的设计与实现 听到对方勤务跳的网络，主动把自己的网络拆散，加入另一个网络。 在同一个网络的情况下，因为令牌的传输没有a c k ，因此令牌的传输难以预 料，若因为极限情况，在一个网络中出现了两个令牌，且序号一样，则在这个t d m a 帧内，网络可能因为某些令牌的冲突而无法正常运行，但在下一个t d m a 帧内， 两个令牌会一起消失，且群首已经发生变化，因此网络会恢复正常。 当一个网络分裂成两个网络，另一个网络中的节点会根据最后接收到动态群 首信息来在一定时刻发起令牌。 ( 5 ) 业务传输的q o s 保证 业务分为两类：同步业务和异步业务，同步业务目前主要支持语音异步业务 主要支持数据，同步业务的传输对时延要求较高，语音业务极限延迟不得超过 1 2 0 m s ，异步业务对时延要求不高。 因为该协议一个t d m a 帧长为4 0 m s ，因为系统必须支持3 跳远的距离可以传 语音，这样语音最长时延为1 2 0 m s 。 在一个t d m a 帧内，一个用户最多占用3 3 个时隙，其中一个时隙用于传包 头，其余的3 2 个时隙可以用来传输语音或数据或a c k 。若用户没有这么多业务， 则可以占用较少的时隙，但最多不得超过3 3 个。这样不会因为一个用户占用过多 的时隙而影响了其他用户的q o s 。 这种措施在一定程度上可以保证一个节点不会占用太多的带宽，因为群首节 点优先传输，因此在一个t d m a 帧内群首节点显然比其他节点有更多的传递数据 的机会。因为网络的群首是动态更换的，因此每一个节点都有机会发起一个t d m a 帧，因此网络瞬时网络是不公平的，但在时间平均上网络是公平的，而且群首更 换一遍要花掉1 6 4 0 = 6 4 0 m s ，因此基本上对各个节点是公平的。 2 4 网络运行的流程 2 4 1m a c 层协议总体流程 对于一个要入网或者退网的用户，均需要通过群首来进行，群首是动态变化 的。对于要发送用户的数据，需要在得到令牌以后方能发送数据，其余的时间均 处于接收状态。收发转换是根据用户得到或者失去令牌来决定的。图2 1 6 为整体 m a c 协议的流程图。 第二章m a c 层协议的设计及r 作原理 2 4 2 建网流程 图2 1 6 协议总体流程图 当节点开机后，在扫描了一个超帧，也就是2 6 4 0 m s ，如果没有任何无线电活 动，那么该节点即为0 节点，同时作为群首节点开始建网，流程如图2 1 7 所示。 图2 1 7 建网流程图 1 6 士兵电台m a c 层协议的设计与实现 2 4 3 入网流程 最先开机的节点( 0 节点) 建立网络以后，在该网络传输范围内( 即其后丌机的用 户在该节点的通信范围内) 开机的节点即可通过该节点的勤务跳和迟入网时隙申请 入网( 开机检测到群首发起的勤务跳，在迟入网时隙申请加入该网络，待群首检测 到迟入网信号后，群首发送应答信息，包括分配给入网节点的逻辑号以及拓扑信 息，该节点同时更新自己的网络拓扑信息) 。流程如图2 1 8 所示。 图2 1 8 入网流程图 第二章m a c 层协议的设计及：r 作原理 1 7 2 4 4 发送接收流程 对于每个用户，电台的工作分为发送和接收两个过程。发送过程，即是要发 送上层来的业务，同时也有接收正确时产生的a c k ，以及重发超时的帧。将各种 业务按照其格式进行装帧，通过驱动交给硬件设备，进而发送出去。接收过程， 即是通过驱动，收到硬件传来的比特流，进行分帧处理，帧类型的判断，c r c 校 验，同时产生a c k 等等。这部分内容，是电台工作的核心内容。发送和接收的流 程分别如图2 1 9 、图2 2 0 所示。 图2 1 9 发送流程图 比特流 帧| 一步 0 婴y i 一 i 判断帧类型 大报头 数据帧觚 h 滑动窗口 上上 i 依据l i n k 到锱嚣 i t a b l e 更改规 i 则进行更改 工n 直接递交网 络层 图2 2 0 接收流程图 ! !士兵电台m a c 层协议的设计与实现 二二二：2 二一 2 4 5 令牌传递算法的流程 。关于令牌的传输，在前面2 ，3 2 的( 2 ) 令牌的传输中有详细的描述，这罩就不在 赘述，图2 2 1 为令牌传递算法【2 7 1 的流程。 图2 2 l 令牌传递流程图 第三章m a c 层协议的实现 1 9 第三章m a c 层协议的实现 在这一章中，首先介绍了系统的组成；然后介绍了嵌入式l i n u x 系统，a r m 开发板以及在此开发板上进行l i n u x 内核烧制编译；接着介绍了协议的实现方法， 用到的数据结构以及系统支持和应注意的问题；最后给出了部分代码的测试结果。 3 1 系统的组成 图3 1 系统框图 图3 2 中央控制单元 如图3 1 所示，系统【3 1 1 有4 部分组成：$ 3 c 2 4 0 1 ，频率合成器，伪码发生器和 通信收发机。 士兵电台m a c 层协议的设计与实现 其中，中央控制单元由基于a r m 9 的嵌入式系统，主要由$ 3 c 2 4 1 0 嵌入式微 处理器、存储系统和外部接口组成。$ 3 c 2 4 1 0 是s a m s u n g 公司近期推出的一款基 于a r m 9 2 0 t 内核的3 2 位微处理器，资源丰富，带独立的1 6 k b 的指令c a c h e 和 1 6 k b 数据c a c h e 、l c d 控制器、r a m 控制器、n a n d 闪存控制器、3 路u a r t 、 4 路d m a 、4 路带p w m 的t i m e r 、并行i o 口、8 路l o 位a d c 、t o u c hs c r e e n 接 口、1 2 c 接口、1 2 s 接口、2 个u s b 接口控制器、2 路s p i 等，主频最高可达2 0 3 m h z 。 我们现在利用$ 3 c 2 4 1 0 出色的内核性能和丰富的外部接口构造一个嵌入式系统平 台，用于跳频电台的中央控制。图3 2 是中央控制单元的硬件框图。 本文的m a c 协议的程序实现后，最终就是在中央控制单元( a r m 处理器) 加 上嵌入的g c l i n u x 系统中运行的。m a c 协议主要完成与o f d m 部分的接口驱动、 数据的收发控制、对于将要发送和接收到的数据进行处理等( 其中本项目的跳频同 步部分程序也在系统中实现) 。 3 2 嵌入式l i n u x 操作系统 嵌入式操作系统是操作系统领域的一个重要分支。由于l i n u x 的独特优势，使 越来越多的企业和科研机构把目光转向嵌入式l i n u x 的开发和研究上。嵌入式 l i n u x 操作系统是嵌入式系统中很重要的部分之一，是联系应用软件和硬件设备的 桥梁。它既要满足一些特殊的应用场合，实现一定的功能，还需满足可靠性，体 积，功耗以及成本等诸多条件。 嵌入式系统通常对实时性、内存体积、资源有特定的要求，下面介绍l i n u x 在这些方面的技术可行性。 ( 1 ) 实时特性 简单的说，嵌入式系统常被错误的划分为实时系统，但其实它们中大多数并 不要求具备实时性。实时性是相对的，硬实时性是能在极短的时间( 微秒级) 内响应， 并以某种确定的方式处理事件。 对于大多数嵌入式系统来说，由1 到5 毫秒的实时响应时间就足够了。l i n u x 内核对实时进程的调度提供了一定程度的支持，能满足大部分软实时，无法实现 硬实时，不过采用r t - l i n u x 能很好的解决该问题。 f 2 ) 内存占用 l i n u x 的内核是长期驻留在内存中的，在简单的系统中，当系统启动后，内核 和各种应用进程均驻留在内存中，但也可以利用l i n u x 动态卸载程序的能力来节省 r a m ：应用程序只需在运行时，才临时装载在内存中，一旦运