用于无线自组网络或个域网的分布式智能调度补偿优化（DISCO）的系统和方法

摘要

本发明提供了一种用于无线自组网络或个域网的分布式智能调度补偿优化(DISCO)的系统。本系统基于包括QoS要求、达到的QoS以及链接信道状态的链接信息，调度安排网络内多个链接的信息包传输。信道状态基于成功信息包传输概率被分类成良好模式、不良模式和边际模式。良好模式的成功信息包传输概率大于边际模式的成功信息包传输概率，而边际模式的成功信息包传输概率大于不良模式的成功信息包传输概率。

说明书

技术领域

[0001]本发明通常涉及无线通信，特别涉及一种用于无线自组网络或个域网的分布式智能调度方法和系统。

发明背景

[0002]在无线终端之间的无线通信已经变得越发普及。基本上有两种技术用于无线网络内的链接终端。第一种技术使用基础设施网络(infrastructure network)，其基本上是转发器系统，其中发射端或初始端联系转发器，然后转发器重新发送信号以允许在目标端上进行接收。基础设施系统的缺点是成本太高和地理限制。由于成本巨大，在所有区域铺设基础设施网络是不切实际的。此外，在紧急时期，如地震、火灾或供电中断，基础结构网络可能在最需要的时候失去效用。

[0003]用于链接终端的第二种技术是在一个有限地理区域内的所有用户之间形成一个无线自组网络。无线自组网络通常包括一群无线终端，它们使用无线射频链接互相进行通信。这些终端通过共享频谱进行通信，并以分布式方式访问媒体。参与自组网络的每个用户应该能够并且愿意转发数据信息包、并参与确定信息包是否从初始源发送到最终目标。与基础设施网络相比，无线自组网络有许多优点。例如，无限自组网络更稳健，其不依赖于单个终端，而是有许多冗余的容错终端，每个容错终端可以替代或扩充其最邻近的终端。另外，自组网络能够实时改变位置和形状。由于其高度的灵活性，无限自组网络被广泛应用在军事和民用应用里。

[0004]作为一个特别类型的自组网络，无限个域网(WPAN)尝试在个人携带的移动设备、家庭电子设备和个人计算机以及外部设备之间建立无线通信。一个WPAN的通信范围被限制在一个小区域内，通常是全向10米的范围。

[0005]对无线自组网络和个域网，服务质量(QoS)是很重要的。在一个网络协议堆栈内，一个有效的媒体访问控制(MAC)方案在提供QoS时扮演了一个重要角色。MAC方案应该尽可能保证信息包传输是成功的。通常，即使当一个时间周期被预留给一个信息包时，MAC调度器仅能够保证信息包将从源传递到无线信道，而不会与其它信息包冲突。但是，MAC调度器不能保证信息包被目标成功接收。这是因为无线信道是一个时变且易错的信道。所以，为了提供QoS，在设置MAC调度器时有必要考虑无线信道质量。

[0006]目前，在IEEE 802.i 1标准内定义的分布式协调功能(DCF)被广泛采用作为自组网络的MAC协议。但是，DCF是一种随机接入协议，并且存在公平问题。因此，它不能提供较好的QoS。已经有许多方案被提议或开发来改善公平特性。但是，大多数此类方案是基于随机信道接入方案：信道接入机会被调整，并受信息包损失影响，信息包损失可能是由信息包竞争和无线信道错误的联合效应引起的。

[0007]有两种MAC方案用于高速WPANs，即IEEE提议的IEEE802.15.3和WiMedia联盟提议的WiMedia MAC。这两种方案都采用时分多址(TDMA)和随机接入机制的混合来提供更好的QoS用于多媒体应用。IEEE 802.15.3是一个集中式调度方案，其中WPAN被分割成一组微微网(piconet)。在每个微微网内，选择一个无线终端作为中央控制单元，被称为微微网协调器(PNC)。PNC通过信标提供基本的时间安排(timing)，并协调在微微网内的接入控制。相反，WiMedia MAC是一种分布式方案，其中在每个无线终端周围形成逻辑群(logical group)，以协调媒体访问控制。系统的基本时间安排是一个超级帧，其还被分割成一个信标周期(beacon period)和一个数据周期(data period)。在信标周期，每个无线终端选择一个时隙来发送其自身的信标，其被用来交换控制信息并形成逻辑群。数据周期被分割成一连串的媒体访问时隙(MAS)。一个MAS或者是被一个无线终端通过分布式预留协议(DRP)预留，或者是被优先级信道接入(PCA)协议留下用于竞争接入。对每个无线终端，预留的时隙是由上层QoS要求确定。

[0008]基于信道状态来调度信道接入的一些方案已经被提议用于无线LANs和无线蜂窝网络。例如，调度可能是基于优先级进行，优先级是信道条件和公平准则的函数。调度方案也可能考虑信道状态和QoS要求。另外，根据流量分类和信道状态，一个半分布式方案可以被用来在接入点和无线终端上进行传输调度。但是，这些方案需要一个中央控制单元来运行调度器。中央控制单元也负责信息收集。此外，通过每个无线终端将信道状态报告给中央控制单元。因而，这种类型的控制调度器不适合非集中式的无线网络。

[0009]信道状态的准确对信道接入调度异常重要。由于无线信道的时变特性，无线终端报告的状态对下一个传输来说可能是过期的。为了获得更准确的信道状态，已经有信道预测机制被开发用于无线LANs和无线蜂窝网络。例如，信道历史信息可以被存储并被用于信道状态预测。但是，这种方案在一个很大的时间尺度内进行信道状态预测，目的在于为无线蜂窝网络内的用户预测路由。

[0010]总之，大多数当前方案是集中式方案，它们不适合自组网络，因为自组网络具有分布式网络结构。所以，期望开发一种完全分布式的基于预测的信道状态、上层QoS要求、以及达到的QoS的调度系统和方法。

发明概述

[0011]提供一种用于无线自组网络或个域网的分布式智能调度补偿优化(DISCO)系统。基于包括QoS要求、达到的QoS和链接信道状态的链接信息，该系统调度安排网络内多个链接的信息包传输。调度安排是通过量化每个链接的无线信道质量来实现的，每个链接的信道状态根据成功信息包传输概率分类成第一或良好模式、第二或不良模式、以及第三或边际模式。良好模式的成功信息包传输概率大于边际模式的成功信息包传输概率，而边际模式的成功信息包传输概率大于不良模式的成功信息包传输概率。

[0012]当一个链接信道状态处于不良模式时，该链接分配的时隙被那个时候具有更好信道条件的其它链接拿走。当该链接信道状态从不良模式变化到良好模式或边际模式时，将进行带宽补偿以保持公平。当一个链接信道状态是在不良模式上时，更少的信息包的将通过此链接传输。为了保持公平，更多信息包将随后通过该链接传输。这通过保持达到的QoS而实现。由于在该链接信道状态恢复后有较差的达到的QoS，将分配更多传输机会以达到较好的QoS。当信道状态处于边际模式时，DISCO系统尝试分配更多带宽给该链接，使得其能够使用更强大的纠错方法来改善其QoS性能。另外，DISCO系统也考虑QoS要求和达到的QoS。所以，DISCO系统能够改善QoS和整个网络带宽利用。

[0013]在一个实施例里，DISCO系统包括一个调度器、一个无线信道状态预测器、一个聚合器、一个广播器、一个信道质量监控器、以及一个数据存储设备。基于包括QoS要求、达到的QoS和链接信道状态的链接信息，调度器被用来进行网络内多个链接的传输调度。无线信道状态预测器被用来预测链接信道状态。聚合器被用来聚合QoS要求、达到的QoS和链接信道状态作为一个链接信息消息。广播器被用来广播链接信息消息。信道质量监控器被用来检测信道质量、计算达到的QoS、旁听和收集链接信息。数据存储设备被用来存储链接信息。

附图说明

[0014]图1是一个典型无线自组网络或个域网的示意图；

[0015]图2显示DISCO方案的一个调度单元的部件；

[0016]图3显示图2调度单元的输出链接处理单元的一个实施例；

[0017]图4显示图2调度单元的输入链接处理单元的一个实施例；

[0018]图5显示误码率(BER)和发送者和接收者的距离之间的关系；

[0019]图6显示信噪比(SNR)和发送器和接收器的距离之间的关系；

[0020]图7显示BER和SNR之间的关系；

[0021]图8显示一个链接信息消息的格式；

[0022]图9是一个描述DISCO方案的流程图；

[0023]图10是DISCO方案初始化过程的一个流程图；

[0024]图11a显示DISCO方案调度过程的一个主要控制流程；

[0025]图11b显示DISCO方案调度过程的一个详细控制流程；

[0026]图12描述具有WiMedia MAC的DISCO方案的实施。

具体实施例详述

[0027]现详细参照本发明的某些实施例，其范例也将在以下描述内提供。本发明典型实施例被详细描述，尽管对相关领域技术人员来说是很明显的，一些对理解实施例不是特别重要的特征，为便于描述不作显示。

[0028]此外，应该注意，本发明不限于以下所述的精确实施例，在不脱离本发明的精神和范围，本领域技术人员可以对其作出各种改变和修正。例如，在本披露和所附权利要求的范围内，不同所述实施例的元素和/或特征可以相互结合和/或替换。

[0029]在一个无线自组网络内，无线终端相互直接通信或通过中间端进行通信。假设每个无线终端仅装配一个全向天线，并且无线终端不能同时发送和接收。调度方案以一个自组网络或个域网为目标，其中所有无线终端都是处于其它终端的通信范围内。所以，所有无线终端能够相互旁听。在一个时间周期内，仅有一个传输可以是成功的，而且所有其它无线终端可以旁听到这个传输。在这些条件下，如果信息包传输不是成功的，失败应该是由无线信道错误引起的。所以，竞争状态要从无线信道错误中解除。此外，由于需要收集全局信息，如果所有无线终端处于各自范围内，很容易监控和收集全局信息。但是，对一个多跳网络，通过采用一种有效的全局信息广播机制，同样可以采用该方案。

[0030]通常，调度是指分配一组工作给一组受制于一组约束的资源。如在此使用的，调度是指基于某些要求(约束)分配传输时间(资源)给一个链接(工作)。

[0031]先参照图1，显示一个典型的无线自组网络或个域网100。网络100包括一组能够相互旁听的无线终端101a-101f。一个链接可以是在任何两个无线终端之间建立，如图内所示的链接102a-102e。一个无线终端可以建立多个链接。

[0032]一个无线终端有两种类型的局部链接，即一个输出链接，如果其充当发送器，以及一个输入链接，如果其充当接收器。在不同类型的链接上采取不同动作。如图2所示，DISCO方案的调度单元可以被分割成两个子处理单元，即一个输出链接处理单元201和一个输入链接处理单元202。每个无线终端可以有一个调度单元，其独立进行传输调度。输出链接处理单元201可以被用于链接信息收集和信道接入调度，而输入链接处理单元202可以用于广播所有局部链接的链接信息、监控信道状态、并测量所有局部输入链接的达到的QoS。有选择地，调度单元可以仅有一个处理单元，其具有如上所述的输出链接处理单元201和输入链接处理单元202的功能。

[0033]现在参照图3，其是图2输出处理单元201的一个实施例，包括一个信道状态预测器306、一个调度器301、一个信道质量监控器302、以及一个数据存储设备(如数据库303、304和305)。输出处理单元201的主要任务包括但不限于，旁听所有链接信息、更新数据库、预测信道状态、并基于预测设置一个所有链接的调度。通过旁听和更新数据库，监控器302可以被用来收集链接信息。数据库303、304和305可以被用来保留实现达到的QoS、QoS要求和无线信道状态。预测器306能够被用于进行信道状态预测。信道预测方法可能依赖于以下物理信道采用的技术。不同的预测方法、如Kalman-filter或最大似然方法，可以被用于预测无线信道状态。基于全局链接信息，调度器301可以被用来设置传输调度。全局链接信息是整个网络内所有链接的链接信息。尽管在此描述了示例的输出处理单元，但应该理解，其它类型的输出处理单元也可以被使用作为DISCO方案的调度单元的子处理单元。

[0034]参照图4，其是图2输入处理单元202的一个实施例，包括一个信道质量监控器401、一个聚合器403、一个广播器404以及一个数据存储设备(如数据库402)。输入处理单元202的主要任务包括但不限于，监控信道状态、计算每个输入链接的达到的QoS、通过聚合所有输入链接的信道状态和达到的QoS以及所有输出链接的QoS要求产生一个链接信息消息、并广播此消息。监控器401可以被用来检测达到的QoS，并监控信道状态。数据库402可以被用来保留历史信息以测量达到的QoS。聚合器403可以将所有局部输入链接的达到的QoS和无线信道状态以及所有局部输出链接的QoS要求结合在一起作为一个消息，其被看作链接信息消息。链接信息消息可以通过广播器404被发送到信道405。尽管在此描述了示例的输入处理单元，但应该理解，其它类型的输入处理单元也可以被用来作为DISCO方案的调度单元的子处理单元。

[0035]DISCO方案是一个基于链接的调度方案，其为每个链接而不是一个无线终端而设置传输调度。本方案可以基于全局链接信息来调度信息包传输。链接信息包括信道状态、QoS要求和达到的QoS。信道状态是指物理无线信道状态，其不包括竞争状态。QoS可以为吞吐量、延迟、延迟抖动、公平性或任何其它度量。达到的QoS是链接的实际QoS性能。QoS要求可以由上层设置。例如，对实时流量，上层可以明确地指定带宽要求或延迟要求，其可以进一步被转换成带宽要求。达到的QoS可以由接收器进行测量。

[0036]信道状态是信道质量的量化，其可以被分类成三种模式：第一或良好模式、第二或不良模式、以及第三或边际模式。当无线信道处于良好状态时，确定为良好模式，从而成功信息包传输概率很高。例如，当成功信息包传输概率大于95-99％，优选地是97％，信道状态被分类成良好模式。当无线信道处于不良状态时，确定为不良模式，从而成功信息包传输概率很低。例如，当成功信息包传输概率小于90-99％，优选地是95％，信道状态被分类成不良模式。当无线信道处于一个边际状态时，确定为边际模式，从而成功信息包传输概率是平均的。例如，当成功信息包传输概率大于或等于90-99％，优选地是95％，但小于或等于95-99％，优选地是97％，信道状态被分类成边际模式。良好模式的成功信息包传输概率大于边际模式的成功信息包传输概率，而边际模式的成功信息包概率大于不良模式的成功信息包传输概率。例如，在一些实施例里，良好范围是95-99％，边际范围是92-94％，而不良范围是小于92％。

[0037]信道状态可以通过无线信道的误码率(BER)来量度。可以定义信道质量信号的两个阈值β₁和β₂(β₁＞β₂)来进行分类。β₁和β₂值取决于应用要求。例如，β₁可以取值于大约10^-4和10^-1范围内，而β₂可以取值于大约10^-9和10^-2范围内。优选地，β₁被设置为大约10^-2，而β₂被设置为大约10^-4。当BER小于β₂时，信道状态被分类成良好模式。当BER大于β₁时，信道状态被分类成不良模式。当BER大于或等于β₂但小于或等于β₁时，信道状态被分类成边际模式。BER是由许多参数确定，如发送器和接收器之间的距离、数据率等。在这些参数中间，距离是一个重要参数。图5显示一个无线信道在BER和距离之间的关系(假设所有其它参数是固定的)。如果选择了β₁和β₂，可以相应地确定信道状态。

[0038]在一个真实系统里，BER被量度为一个测量时间内比特错误数目对接收到的比特数目的比率。为了获得更准确的测量，测量时间应该足够长以便能够获得一个实际统计概率。但是，DISCO方案利用一种信道质量测量方法。所以，作为一种替代方案，信道状态可以通过信噪比(SNR)来量度。SNR是在运行频率范围内收到信号强度对噪声的比率。当成功接收到一个信息包时，可以立即测量其SNR。SNR值越大，信道质量越好。参照图6，可以定义两个阈值α₁和α₂(α₁＞α₂)来区分信道状态。当SNR大于α₁时，信道状态被分类成良好模式。如果SNR小于α₂，信道状态被分类成不良模式。当SNR小于或等于α₁但大于或等于α₂时，信道状态被分类成边际模式。α₁和α₂值取决于预定义的BER阈值。

[0039]通常，SNR和BER之间的关系取决于一个调制方案。可以通过仿真找到一个SNR对BER曲线，以此确定SNR信号的两个阈值。BER和SNR之间的典型关系如图7所示。如果找到SNR和BER之间的关系，基于β₁和β₂可以确定α₁和α₂。

[0040]尽管一个无线信道的BER和SNR已经被用来量度信道状态，但应该理解也可以使用其它类型的方法来量度信道状态，包括但不限于使用信道强度、信息包差错率等。

[0041]在调度单元内，信道状态可以根据信道质量信号值而被存储。通过预测器可以预测一个链接的信道质量信号的新值。链接的未来信道状态可以通过这个值进行分类。信道状态数据库能够保留所有链接的信道状态。数据库也保留历史信息。历史信息的持续时间可能取决于预测方法的要求。

[0042]DISCO方案依赖于全局链接信息。这种信息可以从无线终端获得，其中每个终端周期性地广播链接信息。尽管所有无线终端都处于其它终端的传输范围内，但有时一个终端由于信道错误不能正确地从其它终端接收到链接信息消息。这个问题可以通过重复广播链接信息消息得以解决。

[0043]调度方案也被周期性地调用。在调度周期内，链接信息消息至少被广播一次。如果网络允许的话，与数据信息包相比，链接信息消息可以在一个更可靠的周期内被广播。例如，链接信息消息可以以更低数据率发送，而常规数据可以在同一信道上以一个更高数据率上发送。

[0044]图8显示链接信息消息的格式。输入链接处理单元能够聚合达到的QoS、局部输入链接的信道状态信息以及局部输出链接的QoS要求作为一个消息。消息可以包括起始区901、局部输出链接数目902、每个输出链接的消息项903、输入链接数目906、以及每个输入链接的消息项907。每个输出链接903可以包括该链接接收者904和一个QoS要求905。每个输入链接907可以包括该链接发送者908、一个达到的QoS 909和一个信道质量信号的当前值910。

[0045]参照图9、图10和图11，以下将描述在一个无线终端上运行调度方案的详情。

[0046]基于全局链接信息，调度器能够确定每个链接的调度。在调度过程里信道状态具有最高优先级。当信道状态处于良好模式时，基于一个链接的QoS要求，能够保证带宽预留。当信道状态处于边际模式上时，基于一个链接的QoS要求，能够尽可能保证带宽预留。当信道状态是在不良模式上时，链接服务可能被降低到最低，同时尽可能地进行补偿，而不损害具有良好模式状态的链接服务。

[0047]参照图9，描述DISCO方案主要控制过程的流程图。在初始化步骤1001之后(其将在以下详细描述)，可以形成一个链接信息消息(步骤1002)。然后，无线终端广播链接信息消息，如步骤1003所示。接着，无线终端旁听和取回所有链接的链接信息，并将此信息更新到数据库(步骤1004)。其后，基于新的链接信息，在步骤1005无线终端预测信道状态，并在步骤1006能够设置传输调度(其将在以下详细描述)。基于所有局部输出链接的新调度，无线终端进行传输，如步骤1007所示。另外，无线终端监控链接质量信息，并计算所有局部输入链接达到的QoS(步骤1008)，然后返回到步骤1002。此过程可以继续进行，直到无线终端断开所有局部链接或断电。

[0048]图10是图9 DISCO方案的初始化过程(步骤1001)的流程图。系统参数(如阈值)可以在步骤1102上被初始化。在此步骤之后，初始带宽能够被预留给每个局部链接，且预留信息可以由无线终端记录(步骤1104)。在一个TDMA方案里，通常定义一个帧用作带宽分配。该帧是被时隙化的，根据时隙数目和时隙位置分配带宽到每个无线终端。假设有一种带宽预留机制用于初始带宽分配。另外，无线终端连续监控链接及其预留信息，直到在一个时间周期内网络内没有变化(步骤1106)。最后，每个链接的信道状态被设置成良好模式，如步骤1108所示。

[0049]图11a显示图10 DISCO方案的调度过程(步骤1006)中的控制流程。调度器保留初始带宽分配给每个具有良好模式或边际模式信道状态的链接(步骤1220)。调度器也分配一个最小带宽给每个具有不良模式信道状态的链接，并将初始带宽分配的剩余带宽放入一个可用带宽池(available bandwidth pool)内(步骤1222)。接着，调度器检查在可用带宽池内是否有一个带宽(步骤1224)。如果在可用带宽池内有一个带宽，调度器分配更多带宽到具有边际模式信道状态的链接，并赋予优先级给具有最坏的达到QoS的链接(步骤1226)。调度器再检查在可用带宽池内是否有一个带宽(步骤1228)，如果在可用带宽池内有一个带宽，它分配更多带宽到具有良好模式信道状态的链接，并赋予优先级给具有最坏的达到QoS的链接(步骤1230)。在步骤1224和1228，如果在带宽池内没有可用带宽，调度器离开调度过程。

[0050]图11b显示图10 DISCO方案的调度过程(步骤1006)中更详细控制流程。最初，调度器可以检查是否有任何链接加入或离开信道(步骤1232)。如果有一个链接，调度器重设达到的QoS以进行公平计算，如步骤1234所示。接着，调度器检查至少一个链接(但不是所有)的信道状态是否具有不良模式(步骤1236)。如果条件不满足，调度器使用所有链接的初始带宽分配，如步骤1238所示。否则，调度器保留所有良好信道状态和边际信道状态(步骤1240)的链接的初始分配。对所有不良信道状态的链接，调度器仅能分配最小带宽到这些链接，并将初始分配的剩余带宽分配给可用带宽池(步骤1242)。其后，调度器检查在带宽池内是否有可用带宽，如步骤1244所示。如果有可用带宽，调度器将其分配给具有边际信道状态的链接，并赋予较高优先权给具有较差的达到QoS的链接(步骤1246)。如果在带宽池内还剩有带宽(步骤1248)，调度器分配剩余带宽到具有良好信道状态的链接，并赋予较高优先权给具有较差的达到QoS的链接(步骤1250)。在步骤1246和1250，可以设置系统参数来确定多少带宽应该被分配给每个链接。

[0051]当每个无线终端调用调度方案时，基于相同的初始参数和系统参数，所有无线终端都运行相同的调度方案。所以，对所有链接而言，所有无线终端能够获得相同的调度结果。接着，基于这些结果，每个无线终端传输信息包给其局部输出链接。

[0052]当方案被调用时，假设每个无线终端具有全局链接信息。但是，在一些调度时间点上，一些无线终端仅仅能够获得部分链接信息，所以对所有无线终端而言调度结果可能是不一致的。在此情况下，系统不是收敛的。但是，由于信息被周期性地广播且链接信息是重复的，最后，所有无线终端能够获得全局链接信息，系统是收敛的。

[0053]如上所述，调度器被周期性地调用。调度周期对方案很重要。如果调度周期太长，那么预测的信道状态对调度而言是过期的。如果调度周期太短，那么管理开销很高。通常，调度周期应该被选择，使得在此周期内信道状态和网络拓扑保持静止。在一个TDMA系统里，通常定义一个超级帧为一个带宽分配边界。所以，维持一个或几个超级帧的周期被定义为调度周期。

[0054]利用WiMedia MAC作为一个例子，以下讨论协议方法整合。参照图12，输出和输入处理单元被整合作为一个系统。在所述实施例里，系统可能包括一个调度器1301、一个消息聚合器1302、一个信道状态预测器1303、一个信道状态监控器1304、和数据库1305、1306和1307。一个信标模块1308是通过WiMedia MAC提供。在本实施例里，QoS要求是链接要求的时隙数目。链接信息消息在聚合器内聚合，并使用专用信息单元(ASIE)功能通过信标模块进行广播。信标消息总是在一个最低数据率和最大功率上被广播。无线终端监控信道状态，并通过旁听计算达到的吞吐量。DRP负责初始带宽预留。调度器可以改变DRP预留的分配时隙来调整带宽分配。调度方案是在每个超级帧上被调用。

[0055]尽管已经参考优选实施例描述了本发明，本领域技术人员将认识到，在不脱离本发明的精神和范围可以对其形成和细节进行修改。另外，实施例不是被用来限制所有的细节，在不脱离本发明的精神和范围，可以对其作出修正和改变。