２０１５年２月第１期 现代导航 ・５３・ 一种关于分布式网络调度协议的研究 石伟明 （中国电子科技集团公司第二十研究所，西安７１００６８） 摘要：多址接入控制协议是网络的重要组成部分，特别是在分布式网络中，它直接影响网 络的性能。随着技术的发展，如何将物理层和多址接入层有效的结合起来，如何在接入时可以有 效的利用资源，这些因素对网络性能上的提升具有重要意义和价值。本文研究了高通公司提出的 ＦｌａｓｈＬｉｎＱ通信系统，并且详细介绍了ＦｌａｓｈＬｉｎＱ通信系统所采用的分布式调度协议，该协议是一 种高效的并且有效利用空间资源的多址接入协议，相比于ＲＴＳ／ＣＴＳ机制的ＣＳＭＡ／ＣＡ机制的多址 接入协议有较大的增益。协议可以在信号覆盖范围之内实现多条链路的并行传输，增加了网络的 吞吐量，改善了网络的性能。 关键词：分布式网络；ＯＦＤＭＡ技术；分布式调度协议 中图分类号：ＴＮ９１１ 文献标识码：Ａ 文章编号：１６７４．７９７６一（２０１５）０１—０５３．０５ Ｒｅｓｅａｒｃｈ ｏｆ ａ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｃｈｅｄｕｌｅｒ ｆｏｒ Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ ＳＨＩ Ｗｅｉｍｉｎｇ Ａｂｓｔｒａｃｔ：ＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏ１）ｐｒｏｔｏｃｏｌ ｉｓ ａｌｌ ｉｍｐｏｒｔａｎｔ ｐａｒｔ ｏｆ ｄｉｓｔｉｒｂｕｔｅｄ ｎｅｔｗｏｒｋ，ｗｈｉｃｈ ｉｓ ａ ｋｅｙ ｆａｃｔｏｒ ｔｈａｔ ａｆｆｅｃｔｓ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ａ ｎｅｔｗｏｒｋ ｄｉｒｅｃｔｌｙ．Ｗｉｔｈ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｔｅｃｈｎｏｌｏｇｙ，ｉｔ ｈａｓ ｇｒｅａｔ ｓｉｇｎｉｆｉｃａｎｃｅ ａｎｄ ｖａｌｕｅ ｉｎ ｔｈｅ ｎｅｔｗｏｒｋｓ ｔｈａｔ ｃｏｍｂｉｎｅ ｔｈｅ ｐｈｙｓｉｅａｌ ｌａｙｅｒ ａｎｄ ｍｅｄｉａ ａｃｃｅｓｓ ｌａｙｅｒ ｅｆｆｅｃｔｉｖｅｌｙ，ｔａｋｅ ｇｏｏｄ ｕｓｅ ｏｆ ｒｅｓｏｕｒｃｅｓ ａｎｄ ｂｒｉｎｇ ｔｈｅ ａｓｃｅｎｓｉｏｎ ｏｆ ｈｅ ｎｅｔｔｗｏｒｋ ｐｅｆｏｒｒｍａｎｃｅ．Ｔｈｅ ＦｌａｓｈＬｉｎＱ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｓｙｓｔｅｍ ｉｓ ｓｔｕｄｉｅｄ，ｗｈｉｃｈ ｉｓ ｐｒｏｐｏｓｅｄ ｂｙ Ｑｕａｌｃｏｍｍ Ｃｏｍｐａｎｙ．Ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｃｈｅｄｕｌｅｒ ｐｒｏｔｏｃｏｌ ａｄｏｐｔｅｄ ｂｙ ＦｌａｓｈＬｉｎＱ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｓｙｓｔｅｍ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｄｅｔａｉｌ．Ｔｈｅ ｐｒｏｔｏｃｏｌ ｉｓ ｅｆｆｅｃｔｉｖｅ ｕｓｅ ｏｆ ｓｐａｃｅ ｒｅｓｏｕｒｃｅｓ ａｎｄ ｈａｓ ｇｒｅａｔｅｒ ｇａｉｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ＲＴＳ／ＣＴＳ ｍｅｃｈａｎｉｓｍ ｏｆ ｈｅ ＣＳＭＡ／ＣＡ ｔｐｒｏｔｏｃｏ１．Ｔｈｅ ｐｈｙｓｉｃａｌ ｌａｙｅｒ ｏｆ ｈｅ ｔｐｒｏｔｏｃｏｌ ｕｓｅ ＯＦＤＭＡ ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ａｎ ａｎａｌｏｇ ｓｉｇｎａｌ ｄｅｔｅｃｔｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｔｏ ｐｅｒｃｅｉｖｅｄ ｃｈａｎｎｅｌ ｉｎｆｏｒｍａｔｉｏｎ．Ｗｉｔｈ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ， ａ ｐａｒａｌｌｅｌ ｔｒａｎｓｍｉｓｓｉｏｎ ｏｆ ｍｕｌｔｉｐｌｅ ｌｉｎｋｓ ｃａｎ ｂｅ ｉｍｐｌｅｍｅｎｔｅｄ ｗｉｈｉｔｎ ｔｈｅ ｓｉｎａｌｇ ｃｏｖｅｒａｇｅ，ＳＯ ｔｈｅ ｔｈｒｏｕｇｈｐｕｔ ｏｆ ｎｅｔｗｏｒｋ ｉｓ ｉｎｃｒｅａｓｅｄ ｎｄｔａｈｅｐｅｒｆｏｒｍａｎｃｅｉｓｉｍｐｒｏｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ；ＯＦＤＭ：Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｃｈｅｄｕｌｅｒ Ｐｒｏｔｏｃｏｌ 技术应运而生。高通公司开发的ＦｌａｓｈＬｉｎＱ协议， ０引言 随着信息技术的不断发展，人们对移动通信的 该协议是一种高效的无线多址接入协议，它利用 ＴＤＤ ＯＦＤＭＡ专用同步技术，可以在一公里的范围 内发现其他设备，支持附近数干个设备组建分布式 网络，创建出一个“本地网络”，用户间可以使用 应用程序进行直接交互。其中它一个个重要特点是 在功率非常低的状态下，进行自主发现以及和感兴 趣的节点进行业务交互，并且在感应范围内的设各 需求越来越强。针对于各种不同场景下的通信网络 收稿日期：２０１４．０９．２３。石伟明（１９８８一），硕士研究生， 主要研究方向为移动通信以及ＤＳＰ软件开发。 ・５４・ 现代导航 ２０１５笠 可直接进行通信，无需消耗基础设施资源。 １ ＦｌａｓｈＬｉｎＱ研究的意义 ＦｌａｓｈＬｉｎＱ分布式调度协议基于ＯＦＤＭＡ物理 层的基础上，建立了一种基于ＳＩＲ模型的分布式极 大匹配类型（ｍａｘｉｍａ１．ｍａｔｃｈｉｎｇ．ｔｙｐｅ）调度协议， 这种协议与分布式网络中的基于Ｉ Ｓ／ＣＴＳ机制的 非同步协议ＣＳＭＡ／ＣＡ的主要不同点为： （１）引入了一种新的同步ＰＨＹ，不需要 ＲＴＳ／ＣＴＳ机制预约资源； （２）链路的传输是基于ＳＩＲ，而不是像８０２．１１ 中基于ＳＮＲ。 ＦｌａｓｈＬｉｎＱ协议建立了一种基于模拟能量水平 （ａｎａｌｏｇ ｅｎｅｒｇｙ．１ｅｖｅ１）的信令机制，利用该信令机 制可以进行基于ＳＩＲ的分布式调度。这种信令机制 和相对应的分配算法允许高效的信道感知空间资 源分配；与ＣＳＭＡ／ＣＡ系统中的Ｉ Ｓ／ＣＴＳ机制相比， 这种新型架构增加了空间频谱资源的重用性，从而 可以大大提高频谱利用效率。 ＣＳＭＡ／ＣＡ系统利用ＲＴＳ／ＣＴＳ机制，相当于分 别在发射节点和接收节点周围画了一个具有固定 半径的保护圈，任何在该保护圈内的节点都不允许 同时传输。然而，从通信理论上讲这种保护是既不 必要也不充分的：因为只要接收节点处的ＳＩＲ足够 大，那么在接收节点处就可以成功接收发送端来的 数据包。因此，我们只要保证接收节点处的ＳＩＲ足 够大即可。这意味着接收节点处的保护圈的半径应 该是可变的，即应该与收发节点之间的距离成比例 的。这个条件可以保证接收节点处有一个固定的 ＳＩＲ保护。因此这种基于ＳＩＲ的机制可以允许更多 的并发传输，从而大大提高了空间的吞吐量增益。 分布式调度协议在每个业务时隙为链路分配 不同的优先级，在首先保证高优先级链路能够传输 的情况下，如果低优先级链路的传输不会对高优先 级链路带来过多的干扰，同时高优先级链路的传输 不会对低优先级链路的接收端造成过多的干扰，那 么允许这两条链路同时传输。 ＦｌａｓｈＬｉｎＱ技术的研究的意义如下： （１）建立了一种新的模拟信令机制，利用该 机制可以进行多节点的分布式协调； （２）进行分布式的信道感知空间资源分配； （３）支持ＱｏＳ和公平性。 ２ Ｆ１ａｓｈＬｉｎＱ分布式调度协议的介绍 ２．１基于ＳＩＲ的调度算法 高通公司提出的ＦｌａｓｈＬｉｎＱ协议的核心是基于 ＳＩＲ的分布式调度算法，在介绍ＦｌａｓｈＬｉｎＱ协议之 前先了解如何利用ＳＩＲ分布式调度算法在分布式网 络中进行链路的调度，基于ＳＩＲ分布式调度算法的 原理如下： 假设链路ＡＢ的优先级比链路ＣＤ的优先级高， 通过直接功率信号低优先级链路接收端测量是否 对自己传输造成影响，高优先级接收端通过公式换 算，发送反向功率回声信号，低优先级发送端通过 测量，判断自己是否对高优先级的传输造成干扰。 如果传输互不干扰，那么高低优先级链路可以同时 传输，否则保证高优先级链路传输，低优先级链路 发送端保持静默。 、 ＇＿１＿ ／√ 、 、 ｈ＇ＬＬ＿ａｒｔ ／／ 、、、 ：≯：：： ／／ ＩＩ 、、＿ ｒ ｃ ＿＿ ＿ ， 、 图１分布式调度算法 ＞ （１） ｅ￣ｌｈ８ ｌ。 ＞ 。ｒ 和 都是一个ＳＩＲ门限值，两条链路的 直接增益和跨链路增益分别为｛ ｌ。，Ｉｈｃｏｌ ）， ｛ｌ 。 Ｉ ）； 和ｃ分别发送功率信号 和 ， 式（２）的分子为Ｄ点接收功率，分母为 对Ｄ的 干扰，那么由式（２）确定。点的ｓＩＲ： ｅ￣ｌｈｃｏｌ：（高 优先级发送节点 是否对低优先级链路的干扰）是 第１期 石伟明：一种关于分布式网络调度协议的研究 ．５５． 机分配优先级，在用户的传输发生冲突时，保证高 否满足；假设 端发送的反向功率回声为 ｒ ， 优先级的用户优先接入信道。低优先级的用户只有 在满足ＳＩＲ约束且不影响高优先级用户正常传输的 情况下，才能同时在当前时隙调度。通过在每个业 务时隙为用户重新分配优先级来保证用户的调度 公平性。 其中Ｋ为一个定义好的系统常数。Ｃ处的接收功率 ，ｃ可以通过下式来ｇ￣ｇＡＢ链路的 在一个协议帧内主要完成以下三个过程：对等 发现、寻呼过程、数据传输；其中对等发现过程和 ｓ－Ｒ： ＝壶硎用该公式可以确 （低优先级链路对高优先级链路的干扰）是否满 足。 寻呼过程在控制时隙完成，数据传输阶段在业务时 隙完成。对等发现阶段可以通过接收其他节点广播 出的自身信息获得本地节点发现列表；如果自身有 业务时，在寻呼阶段通过监听ＣＩＤ使用情况，选择 空闲ＣＩＤ和感兴趣的节点建立连接；数据传输通过 ＳＩＲ分布式调度算法，判断自身和最高优先级链路 是否可以并存，如果可以并存，那么选择合适的传 输速率进行业务的交互。图２为ＦｌａｓｈＬｉｎＱ分布式 调度协议的帧结构示意图。 如果两条链路同时满足式（１）、式（２），那么 两条链路分别满足传输所需的ＳＩＲ，虽然在信号的 覆盖范围之内，但是可以同时传输。 ２．２ ＦｌａｓｈＬｉｎＱ多址接入协议的流程介绍 ＦｌａｓｈＬｉｎＱ多址接入协议是一种分布式同步接 入协议，协议为当前时隙有业务传输需求的用户随 一ｌ Ｉ １ 寻呼 业务时隙 一业务时隙 Ｉ Ｉ对等发现 ／ 连接调度 速率调度 ＰⅡ ０Ｔ ＣＱＩ 数据传输 ＡＣＫ 图２协议结构示意图 ２．２．１对等发现过程 侦听所有子载波（设为Ⅳ个载波）上的广播信 ・５６・ 现代导航 ２０１５年 号，具体做法如下：测量每个子载波上的信号强度， 如果该子载波上的信号强度高于一定门限将当前 信号进行解码，获得发送该信号的终端ＩＤ信息并 且在本地维护一张节点发现表，记录收到的ＩＤ信 息，否则如果该子载波上的信号强度小于门限，则 将该子载波标记为可用将自身的ＩＤ信息调制到该 子载波上进行发送，节点一般９０％多的时间都处于 监听状态。 ２．２．２寻呼过程 寻呼过程分为以下几个过程： （１）ＣＩＤ广播阶段 ＣＩＤ广播阶段，用于指示ＣＩＤ的占用情况和用 户的活动情况。已有ＣＩＤ的节点选择空闲子载波广 播当前用户的ＣＩＤ，未建立连接的节点侦听并记录 这些广播信息，为以后选择ＣＩＤ提供依据。 在该阶段包含一个Ｔｘ—Ｒｘ Ｂｌｏｃｋ，Ｔｘ—Ｒｘ Ｂｌｏｃｋ 由若干个时频资源块组成，各节点的具体操作步骤 如下：在Ｔｘ－ｂｌｏｃｋ中，已建立连接并且业务传输没 有完成的节点根据已有ＣＩＤ在其之前选定的资源 块上以最大功率广播ＣＩＤ信息，对应的接收端接 收，并获得当前信道信息（ＳＮＲ）；未建立连接的 用户监听已经占用的ＣＩＤ情况，为后续建立连接时 选取ＣＩＤ提供依据。在Ｒｘ－ｂｌｏｃｋ中，已有ＣＩＤ的 用户的接收端在相对应的资源块上以最大功率发 送回复信息；相应的发送端侦听该信号并从信号中 获取当前信道信息（ＳＮＲ），作为功率调整的依据。 （２）连接建立阶段 连接建立阶段也包含一对Ｔｘ．Ｒｘ Ｂｌｏｃｋ，有新 业务传输需求的节点随机选择一个空闲的ＣＩＤ，并 利用协议事先规定的映射函数，将ＣＩＤ映射到相应 ＴＸ—ｂｌｏｃｋ的时频资源块上传输寻呼请求信息；其他 节点全频监听寻呼请求，如果正确解调得到的请求 中Ｒｘ ＩＤ与本身ＩＤ相同，则该节点记录该ＣＩＤ并 检测该消息接收功率，更新该用户的信道信息 （ＳＮＲ），并且在ＣＩＤ对应的ＲＸ．ｂｌｏｃｋ时频资源块 上发送响应信息，完成握手过程，从而连接建立。 如果发送节点没有接收到响应信息，说明连接没有 建立成功。则说明在ＣＩＤ的选择过程中出现了冲 突。节点重新选择其他空闲ＣＩＤ，或调用ＣＩＤ复用 算法来完成连接的建立过程。如果该ＣＩＤ对应的发 送端成功接收到响应信息，则测量并获取当前信道 信息（ＳＮＲ），作为功率调整的依据，表明连接建 立成功。 （３）ＣＩＤ复用阶段 如果经过前两个Ｔｘ—Ｒｘ ｂｌｏｃｋ，由于没有选择到 空闲ＣＩＤ，使得发射结点仍未成功建立连接，则进 入节点进入ＣＩＤ复用阶段，调用ＣＩＤ复用算法， 根据ＣＩＤ的复用准则，确定一个局部唯一的ＣＩＤ 进行复用。如果选择到合适的复用ＣＩＤ，则成功建 立连接；否则，连接建立失败，节点不参与后续操 作，进行省电状态，等待下一个寻呼阶段的到来。 ２．２－３业务时隙 确定当前时隙的并发传输链路，确定每条链路 的传输速率，发送端进行数据传输，接收端进行确 认。如图２分为以下四个阶段： （１）连接调度阶段 确定当前时隙可以并发传输的链路；为每条链 路的连接ＣＩＤ对应一对单频（发端和收端各对应一 个），这些单频对出自于一个ＯＦＤＭ时频矩阵；且 每对频率对应于一个不同的优先级；在进行ＣＩＤ与 时间．频率块的映射时，可以是随机的，也可以利用 一个标识符和时间变量的哈希函数来产生选择的 符号和频率位置。在每个时隙的开始，产生一个新 的映射。 所有连接链路的发射端利用Ｔｘ．ｂｌｏｃｋ中分配的 时间一频率块向自己的接收端发出传输请求，所有连 接链路的接收端侦听Ｔｘ—ｂｌｏｃｋ，解码出与其对应的 发射端的时间．频率块，然后接收端计算ＳＩＲ，决定 是否放弃接收（判断高优先级链路的传输会不会对 自己的传输造成很大的干扰）。 如果接收端选择放弃接收，那么它不做任何回 应。否则，它在为其分配的时间一频率块上发送反向 功率回声作为响应信号。所有的发射器侦听这些时 间一频率块，解码出与其对应的接收端的时间一频率 块，然后发射端计算ＳＩＲ，决定是否放弃发送（判 断自己的传输是否会对高优先级链路的传输造成 很大的干扰）。此处的算法参照式（１）和式（２）。 如果某条链路的发送端和接收端都不放弃，那 么这条链路在该时隙可以进行传输。重复该过程， 直到达到最大并发链路数。 （２）速率调度 所有被允许传输的链路都将使用速率调度信 道来决定编码速率和调制。这个信道由一个发射器 发射的宽带ＰＩＬＯＴ和一个接收器发射的ＣＱＩ（信道 质量指示器）组成。发射端发射一个导频信号给接 收端，接收端根据该导频信号计算精确ＳＩＲ，确定 第１期 石伟明：一种关于分布式网络调度协议的研究 ・５７・ 它可以支持的数据速率，并将该速率告诉发端。 ＦｌａｓｈＬｉｎＱ协议是通过给不同的通信链路分配不同 这种逐个时隙进行的速率估计会达到比连接 调度更准确的ＳＩＲ估计。每条链路的编码速率和调 制方式都是根据真实的ＳＩＲ来选择的。 （３）数据传输 的优先级，优先级在每个业务时隙随机改变，然后 根据ＳＩＲ分布式调度算法完成链路的调度，最终完 成高效的分布式网络调度。正因为ＦｌａｓｈＬｉｎＱ协议 的分布式特性，它具有现有蜂窝网络不具备的特 所有的调度链路都在全频上进行传输。根据数 点，在未来生活中具有广泛的应用前景，如社交网 据包的长度，选择发射功率，从而达到控制干扰的 目的。如果数据包的大小比正常的业务帧要小，发 射器使用比发送正常帧要小的功率，它只需要使用 一个较低的编码速率来保持传输所需的ＳＩＲ即可。 这样数据包的传输就不会对附近的数据包传输造 成太大的干扰。 （４）ＡＣＫ传输 ＡＣＫ使用正交信道，该正交信道是基于成功接 收数据包的链路的ＣＩＤ来选择的。由于这是一个为 ＡＣＫ设计的专用信道，因此ＡＣＫ信号不会干扰其 它信号。 ３结束语 本文首先对ＦｌａｓｈＬｉｎＱ多址接入协议的核心～ 一ＳＩＲ分布式调度算法的原理进行了介绍。然后对 于ＦｌａｓｈＬｉｎＱ协议的运行流程进行了详细的说明， 络、广告推送。它在一定程度上可以满足一公里范 围内的通信需求，随着研究的深入，这项技术会更 好的服务于我们的生活。 参考文献： 【１】 盛敏．移动Ａｄ Ｈｏｃ关键技术研究［Ｄ】．西安电子科技大 学博士论文。２００３． 【２】 李奎元．ＯＦＤＭＡ系统同步技术研究【Ｄ】 匕京邮电大学， ２０１０． 【３］ 逯璐，蒋朝根．ＯＦＤＭ信噪比估计分析与设计【Ｄ】．西南 交通大学，２０１０． ［４】Ｘｉｎｚｈｏｕ Ｗｕ，Ｔａｖｉｌｄａｒ，Ｓｈａｋｋｏｔｔａｉ，Ｒｉｃｈａｒｄｓｏｎ，Ｊｕｎｙｉ Ｌｉ． ＦｌａｓｈＬｉｎＱ：Ａ ｓｙｎｃｈｒｏｎｏｕｓ ｄｉｓｔｒｉｂｕｔｅｄ ｓｃｈｅｄｕｌｅｒ ｆｏｒ ｐｅｅｒ－ｔｏ－ｐｅｅｒ ａｄ ｈｏｃ ｎｅｔｗｏｒｋｓ［Ｃ］，Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ， ａｎｄ Ｃｏｍｐｕｔｉｎｇ，２０１０ ４８ｔｈ Ａｎｎｕａｌ Ａｌｌｅｒｔｏｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｅｐｔ．２９ ２０１０－Ｏｃｔ．１ ２０１０．
