CN1338187A

CN1338187A - 信道分配的设备和方法

Info

Publication number: CN1338187A
Application number: CN99815468A
Authority: CN
Inventors: 兹维·斯洛温
Original assignee: Marconi Communications Israel Ltd
Current assignee: Marconi Communications Israel Ltd
Priority date: 1998-12-07
Filing date: 1999-12-07
Publication date: 2002-02-27
Also published as: ZA200104568B; JP2002532984A; AU1582800A; EP1138168A1; HK1044443A1; NO20012781L; RU2001115687A; IL127436A0; IL127436A; WO2000035222A1; NO20012781D0

Abstract

本发明公开了一种由第二组发射机利用第一组信道的方法,该方法包括下面步骤:规定第三组发射机子集使得第二组发射机中至少一个包括在每个发射机子集中;将来自第一组信道的至少一个信道分配到每个发射机子集,在该发射机子集的发射机之间共享,使得小于所有第一组信道被分配给第三组发射机子集,因此规定了还没有分配给任何发射机子集的信道的储存器,并且共享所有第二组发射机中信道储存器的信道。还公开了一个由第二组发射机利用第一组信道的系统。

Description

信道分配的设备和方法

发明领域

本发明涉及信道分配的设备和方法。

发明背景

现代的信道分配方法在下面的文件中描述：

“无线网络的资源分配”，Scott Jordan，JHSN，10，January1995。

Duque-Anton等人的“使用仿真热处理(simulated annealing)的静态和动态信道分配”，在电信的神经网络的第10章，Ben Yuhas和Nirwan Ansari(Ed.)，Kluwer Academic Publishers，Buston，1994。

“借用而不锁定的优先信道(Prioritized channel borrowingwithout locking)：一种用于蜂窝式通讯的信道共享策略”，H.Jiang和S.S.Rappaport，IEEE/ACM Transactions on Networking，Vol.4，No.2，April 1996。

在说明书中提到的所有公开的出版物和这里引用的出版物在此作为参考。

发明概述

本发明试图提供用于信道分配的改进的设备和方法。

因此，根据本发明优选实施例，提供一种通过第二组发射机利用第一组信道的方法，该方法包括定义第三组发射机子集使得第二组发射机中至少一个包括在每个发射机子集中，并且将第一组信道中至少一个信道分配到每个发射机子集，在该发射机子集的发射机之间共享，使得小于所有第一组信道分配给第三组发射机子集，因此定义了没有分配给任何发射机子集的信道的储存器(reservoir)，并且共享所有第二组发射机中信道储存器中的信道。

另外根据本发明的优选实施例，如果没有包括第一和第二发射机的邻近小集团(neighbor-clique)，即使储存器中的信道被第二发射机使用，第一发射机也有资格使用该信道，其中单独的发射机子集的邻近小集团包括与单独的发射机子集共享至少一个公共发射机的所有发射机子集。

另外根据本发明的另一个优选实施例提供了一种方法，利用该方法，在第一组信道服务于包括单独的发射机的第二组发射机的情况下，该单独的发射机发射，如果该发射机属于第一信道服务的发射机子集并且如果第一信道是可利用的，该方法包括在第一组信道中第一信道上的发射，否则，如果信道的储存器包括可利用的第二信道，则经过第二信道发射，其中储存器包括不服务于任何发射机子集的第一组信道中所有的信道。

另外，根据本发明的优选实施例，信道通过它们的传输频率分开。

另外，根据本发明的优选实施例，信道通过它们的传输编码分开。

另外，根据本发明的优选实施例，这些信道包括CDMA(码分多址)信道。

另外，根据本发明的优选实施例，至少一些信道包括无线信道。

根据本发明的优选实施例，子集定义步骤还包括对于每个子集从子集的发射机中选择一个子集主机，经过控制信道子集主机寻址信道分配请求。

另外，根据本发明的优选实施例，选择子集主机以便最大程度地利用控制信道，用于该子集中的发射机与子集主机属于的其它子集的发射机通讯。

根据本发明的优选实施例，属于最大数量的其它子集的子集中的发射机被选择作为子集主机。

另外，根据本发明的优选实施例，该方法还包括通过将丢失(dropout)的发射机从它属于的子集断开来放弃丢失的发射机，包括仅通知每个子集的主机该丢失的发射机已经断开。

根据本发明的另一个优选实施例，同样提供一个通过第二组发射机利用第一组信道的系统，该系统包括信道分配器，操作时将第一组信道中至少一个信道分配到第三组发射机子集中的每一个，每个子集包括第二组发射机中至少一个，该信道在该发射机子集的发射机中共享，使得小于第一组信道的所有信道分配到第三组发射机子集，因此规定一个还没有分配到任何发射机子集的信道的储存器，信道共享器操作时共享所有第二组发射机中信道储存器的信道。

本发明方法的特别优点是该方法是典型的NP完整的(NP-complete)。

附图简要描述

结合附图，由下面详细的描述可以更好地理解本发明。

图1是根据本发明优选实施例构造和工作的信道分配系统的简化功能方框图，它将信道分配给空间分布的若干个发射机；

图2示出在如墙的障碍之间的欧几里德空间分布，同时也在空间分布的若干个发射机；

图3示出在非欧几里德空间分布的相同数量的若干个发射机；

图4是一些发射机子集的描述；

图5是图3的子集I和子集VI之间图形表示的关系；

图6说明子集图形上色处理的结果；

图7A-7F说明子集I-VI中每一个的邻近小集团；

图8是一个总结了图2-7F的例子中子集和邻近小集团之间关系的表格；

图9是一个表示在分配信道给子集之前哪个信道属于每个本地储存器的表格；

图10是一个表示在信道A和B已经分配给子集I-IV之后哪个信道属于每个本地储存器的表格；

图11A是一个表示图11B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图11B说明借用处理，其中发射机#1从它的本地储存器借用信道C；

图12A是一个表示图12B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图12B说明借用处理，其中发射机#21从它的本地储存器借用信道D；

图13A是一个表示图13B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图13B说明借用处理，其中发射机#15从它的本地储存器借用信道C；

图14A是一个表示图14B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图14B说明借用处理，其中发射机#17从它的本地储存器借用信道D；

图15A是一个表示图15B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图15B说明借用处理，其中发射机#1、#15、#17和#21的每一个已经返回它们使用的信道并且发射机#4从它的本地储存器借用信道C；

图16A是一个表示图16B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图16B说明借用处理，其中发射机#8从它的本地储存器借用一个信道(发射机#4还没有返回它的信道)；

图17A是一个表示图17B中示出的借用处理已经发生之后哪个信道属于每个本地储存器的表格；

图17B说明借用处理，其中发射机#7和#9的每一个从它们各自的本地储存器借用一个信道；

图18A描述了在500毫秒相对高的信道请求密度时间周期上发射机#1-#10的时间序列。如所示，每个发射机可以是“高(up)”状态或在“低(down)”状态。“高”状态表示空闲(即没有请求的信道)，反之“低”状态表示有请求的信道；

图18B是图18A的时间周期内“放大”的100毫秒时间周期；

图19A描述在500毫秒相对低的信道请求密度时间周期上发射机#1-#10的时间序列。如所示，每个发射机可以是“高”状态或在“低”状态。“高”状态表示空闲(即没有请求的信道)，反之“低”状态表示有请求的信道；

图19B是图19A的时间周期内“放大”的100毫秒时间周期；

图20是用于图1连通矩阵发生器的优选操作方法的简化流程图说明；

图21是用于图1发射机子集发生器的优选操作方法的简化流程图说明；

图22是用于图1子集图形结构单元的优选操作方法的简化流程图说明；

图23是用于图1子集图形上色单元的优选操作方法的简化流程图说明；

图24是一个示出适用于附件A或附件B的输入格式的表格；

图25是用于图1本地储存器管理单元的优选操作方法的简化流程图说明；

图26是用于完成图25步骤870的最小成本信道计算的优选方法的简化流程图说明；

图27A-27B是两个发射机的频谱密度图，该图形成术语“中心信道”、“相邻信道”和“相间信道”的图示定义；

图28是发射机采用三种不同的方法与其它网络组成部分通讯的示意说明；

图29是相同子集中两个发射机同时通讯的示意说明；

图30是子集产生的逐步处理的示意图；

图31是在子集图形上实现彩色上色的说明。

图32是具有给定边缘长度的无向子集图形的说明。

图33是基本小区结构内数据流的说明。

这里附加的附件可以帮助理解本发明的优选实施例，附件如下面示出和描述：

附件A和B是用软件实现的本发明另一个实施例，它接收发射机连通矩阵作为输入，并且完成下面的功能：发射机子集产生、子集图形构造、以及邻近小集团计算；

附件C是用于提供附件A或附件B方法的管理最佳化循环的优选技术的软件列表；

附件D是用于附件A或B的初始化文件；

附件E是通过运行附件A或B的包含图24数据的ASCII文件产生的输出文件的例子；以及

附件F是完成图1的单元60和70功能的Matlab过程的软件列表。

优选实施例详细描述

图1是根据本发明优选实施例构造和工作的信道分配系统的简化功能方框图，它将信道分配给空间分布的第一组发射机。典型地，发射机用作较大一组工作站(未示出)的接入点。

术语“信道”用于包括可以发送信号或数据或信息的任何器件或工具或路径或接入线路，包括但不限于有线频道如TV有线电视和长途地下电缆；无线频道如无线电频道、光纤和卫星；以及上面的任何组合。

术语“连通”定义为两个或多个发射机之间的相互灵敏度。图1的系统包括操作时产生矩阵的连通矩阵发生器10，它的元素表示第一组发射机内每对发射机之间连通的级别。

发射机子集产生器20操作时产生第二组子集，每个子集包括一些发射机。每个子集的发射机典型地共享至少一个信道，没有任何子集以外的发射机有资格使用该信道，除了能够再用信道而又实质上不会干扰子集中发射机的子集以外的发射机。

子集内的发射机能够相互通讯，例如当“普通的”发射机通过任何适当的有线或无线装置向子集的主发射机要求信道时。典型地，子集信道中的一个可以用于在子集内通讯。这个信道称为子集的“控制信道”。

应该理解每个子集中的发射机可以适当地使用它们共享的信道。信道可以单独地或部分地(例如，通过分时方案)用于下面的一些或所有的功能，功能(a)和(b)是控制功能而功能(c)是正常使用功能：

a.如下面详细描述的，允许子集中特定的发射机为自身向主储存器请求信道。例如，发射机可以使用信道B以便为它自身请求信道并且根据响应可以接收来自主储存器的信道C。

另一方面，应该理解发射机让主储存器分配信道给该发射机的请求可以经过特定的信道传送，该信道不用于其它目的即不是主储存器信道中一个。特定的信道甚至可以经过不同于主储存器中信道的介质。

b.允许子集服务的工作站请求接入发射机。例如，工作站可以使用信道B以便通知它的“希望”以发送数据或由互联网服务。根据响应，发射机中的一个(例如，发射机No.3)可以使用特定的信道来为它自身请求主储存器的一个信道。根据响应，主储存器可以分配信道C到发射机No.3并且工作站可以随后经过信道C发送数据到发射机No.3。另一方面，如果适当的分时方案用于信道B，从发射机No.3到主储存器的请求可以经过信道B发射。

c.典型地允许特定的发射机传送数据，以便服务于特定的工作站。

可以使用任何适当的协议来管理工作站和发射机之间的通讯，例如TDMA(时分多址)、环路协议如令牌环；ALOHA、PPMA(抢先查询多址联接)、GRAP(分组随机存取查询)、CSMA(载波检测多址联接)如CSMA-CD(CSMA-冲突检测方式)、以及CDMA(码分多址)。可以使用任何适当的协议例如任何上面的协议或它们的任何适当的组合来管理子集内发射机之间的通讯、以及子集之间发射机之间的通讯。

在附件A中实现的处理最好在操作阶段激活之前完成。

返回参照图1，子集图形构造单元30操作时构造一个图形以表示子集的连通，这里如果它们各自的最近成员(member)发射机相互间相当靠近则子集被认为是连通的。

邻近小集团计算单元34操作时计算由单元30构造的子集图形中所有邻近小集团的集合。包括一个适当源码例子的用于单元34操作的优选方法在TAB Professional and Reference Books，BlueRidge Summit，PA，USA，1989的Lau，H.T.的图形算法第59-69页中描述。

图形上色单元40操作时通过将单元30产生的子集图形上色使得分配信道给该子集，每个子集(节点)的颜色表示分配到那里的信道。通过图形上色的信道分配允许使用最小数量的信道，同时确保每个子集对信道的使用实质上不会干扰任何其它子集中的发射机。在图23中说明了图形上色单元40的优选实施例的功能方框图。包括适当的源码例子的图形上色单元的优选实施例在TAB Professional and Reference Books，Blue RidgeSummit，PA，USA，1989的Lau，H.T.的图形算法第4章中描述。图形算法还提供完成子集图形上色的代码。

储存管理器50操作时管理包括所有还没有分配到特定子集的信道的主储存器。储存管理器50是一个功能单元，实际上，它典型地通过各个发射机完成。完成储存器管理功能的各个发射机可以是预定的，但最好它们是选择的。在说明的实施例中，子集主机分配子单元60操作时分配或选择发射机来完成储存器管理功能，典型地每个子集一个主发射机。最好所有的主发射机是相同的状态并且没有“主-主(master-master)发射机”。然而，在某些应用中，可能最好分配或预定一个“主-主发射机”，它可以包括或者不包括主发射机中的一个。

典型地，每个子集的主发射机被选择作为属于最大数量其它子集的子集中的发射机，即发射机具有最大的邻近小集团。应该理解如果子集A的主发射机也是子集B中的成员，则最好子集A内的发射机能够利用子集A的控制信道以便经过子集A的控制信道、主发射机、以及子集B的控制信道传送消息到子集B的成员。这是典型的情况，即使子集A的主机不是子集B的主机。最好，这种利用仅在控制信道是空闲时被允许，即从主子集请求的信道经过主子集优先与其它的子集进行一般的通讯。

一般地，选择作为子集主机的具有最大邻近小集团的发射机的特别的优点是这种选择通过随后有效地使用分配给该子集的未控制信道来最大地利用控制信道，使得子集之间的连通达到最大。

服务于特定子集的每个管理器发射机包括本地储存器管理单元70，该单元是一个功能单元，操作时从该子集的观点管理主储存器。如下面详细描述的，由代表特定子集的特定子集管理器管理的主储存器在这里也称为该子集的“本地储存器”。应该理解子集管理器本身典型地有时要求信道并且在这种情况下，典型地，该子集管理器向自身要求信道，类似于子集中其它发射机向管理器要求信道。

术语“分配(assign)”用于表示向子集提供信道的处理，这个信道“属于”该子集并且不仅被子集“借用”。术语“分派(allocate)”用于表示由主储存器“借出”一个信道给单独的发射机的处理。

图2示出在如墙的障碍120之间的欧几里德空间分布，同时也在空间分布的若干个发射机110。

图3示出在非欧几里德空间分布的相同数量的若干个发射机。应该理解用于规定发射机之间距离的度量典型地是一种非欧几里德度量。例如，如果使用非欧几里德空间如Labochevsky或Minkowski度量，发射机之间的距离与这些发射机之间存在的信号强度传播(典型地采用电磁dB进行测量)成比例。Minkowski度量在Moyseyev，R.，Chapter 2，Dover Books，1942的时空运动中进行描述。Minkowski度量的使用在Dover，Prentice-Hall，1942的P.G.Bergmann的相对论入门中进行描述。用于本发明说明实施例的适当的Minkowski度量在下面的弗吉尼亚州立大学物理系的网址中描述：http：//astsun.astro.virginia，edu/～eww6n/math/MinkowskiSpace.html。

若干个发射机是典型的，使得实质上没有串音，即在每个发射机和它自身之间的距离是无穷的，它在Labochevsky度量下等效于零距离。

应该理解图3的发射机可以被认为是一个完整的图形，其中每个发射机是一个节点并且连接每两个节点的边缘的加权是它们之间的距离。该距离例如可以是Labochevsky度量距离，以dB表达。如果两个发射机的定位使得它们不能相互间接收，则它们之间的距离典型地被认为是无穷大。

现在定义发射机子集使得21个发射机(在当前的例子中)中至少一个包括在每个发射机子集中，最好每个发射机包括在至少一个子集中。

图4示出6个子集，每个包括5或6个发射机，不过应该更一般地理解，任何数量的发射机，包括仅有一个发射机可以被包含在一个特定的子集中。

为了产生图4的子集，可以使用下面的准则：

a.每个子集具有预定的最大数量的发射机以及每个子集具有预定的最小数量的发射机。例如，如图4所示，该规则可以是每个子集必须包括5个或6个发射机。

b.对于每个发射机，存在该发射机有资格属于的最大数量的子集。在说明的例子中，每个发射机有资格属于仅仅多到2个子集。然而，更一般地说，一些发射机可以有资格属于仅仅3个子集，而另一个发射机可以有资格属于例如仅仅一个子集。

为了使发射机属于n个子集，典型地，发射机有能力在n个不同的信道中同时工作，例如典型地包括n个分开的和独立的发射机单元，例如n个不同的无线电设备。例如，为了使一个无线电发射机属于2个子集，该无线电发射机典型地包括两个分开的和独立的无线电单元。这是建立每个发射机有资格属于的最大数量子集的一个原因。然而，在某些应用中，最好用于特定发射机的最大数量的子集小于该发射机能够发射的信道数量。

c.仅属于一单个子集的发射机的数量应该是最少的。

d.连接的子集数量应该是最少的。如果两个子集之间的距离小于预定的连通门限值如说明例子中的-91dB，则它们被“连接”。

不具有公共成员的两个子集之间的“距离”被定义为第一子集中任何发射机和第二子集中任何发射机之间的最小距离。具有公共成员的子集之间的距离是零，因此具有公共成员的子集总是被认为连接的。

e.每个子集属于的邻近小集团的数量应该是最小的。每个子集S具有一个“邻近小集团”，该小集团包括连接到S的所有子集。因此，每个子集S属于的邻近小集团的数量等于连接到S的子集的数量。

可以使用任何适当的技术来产生满足上面准则(a)到(e)的子集，如基于组合代数或神经网络或人工使用期限(artificiallife)方法或蒙特卡罗(Monte Carlo)法的技术。描述人工使用期限方法的出版物包括：

在L.D.Whitley(Ed.)，Morgan Kaufmann，San Mateo，CA，USA的原生(genetic)算法基础＿2中D.Whitley的“简单原生算法的可执行模型”。

在L.D.Whitley(Ed.)，Morgan Kaufmann，San Mateo，CA，USA的原生算法基础＿2中M.D.Vose的“简单原生算法建模”。

接着，产生表示子集之间关系的图形。典型地，如果相应的子集被连接，则图形中每个节点表示一个子集和一对节点是相邻的(即在它们之间有一个边缘)。图5示出表示图3的子集I到VI之间关系的图形。

使用最少数量的颜色，将可利用信道颜色编码并且现在对图形中的节点(子集)上色。换句话说，由节点的颜色识别出属于相应于该节点的子集的信道。应该理解如果多个信道分配给一个特定的子集，该子集的节点将具有多种颜色(即该节点的颜色向量长度是多个)。可以使用任何适当的方法对信道上色，如在TABProfessional and Reference Books，Blue Ridge Summit，PA，USA的H.T.Lau图形算法的第四章中描述的彩色上色。

没有分配给任何子集的信道被认为属于一个主储存器，该储存器通常由所有子集中所有的发射机使用。如下面更详细描述的，主储存器中的信道有时能够同时由多个发射机使用。这种情况在这里称为“信道再用”。

典型地，通过从主储存器获得本地储存器便于信道再用。对于每个发射机子集典型地获得一个本地储存器。在给定时间t本地储存器内的信道总是在时间t包括在主储存器中的信道子集。当且仅当一个信道可以由相应于储存器I的发射机子集I中任何发射机和相应于储存器II的发射机子集II中任何发射机同时使用时，该信道同时包括在两个本地储存器I和II中。更一般地说，当且仅当一个信道可以分别由n个储存器的每n个发射机子集的一个成员同时使用而实际上无干扰时，该信道同时包括在n个本地储存器中。

典型地，如果两个发射机之间传输质量的预定成本函数值低于门限值，则两个发射机被认为是“实际上无干扰”地工作。例如，成本函数可以包括两个发射机之间信道的BER(误码率)。

一开始，每个本地储存器包括主储存器中所有的发射机。然而，应该理解随后根据每个子集与其它子集的关系并且根据每个子集需要信道的程度，每个本地储存器不同程度地缩小并且再扩展回去。

根据图2-6的例子，现在描述从服务于6个发射机子集的主储存器发展到6个本地储存器的例子。

图7A-7F说明分别用于子集I-VI中每一个的邻近小集团200、210、220、230、240和250。这些小集团由图1的邻近小集团计算单元34来定义。每个小集团由环绕所有它的成员的虚线识别。

图8是一个总结图2-7F的例子中子集和邻近小集团之间关系的表格。“X”表示两个子集之间的连通。

图9是一个表示如图6所示在分配信道给子集之前哪个信道属于每个本地储存器的表格。如说明的，每个本地储存器包括所有的信道A-G，因此，当然主储存器也包括所有的信道A-G。

图10是一个表示如图6所示在信道A和信道B已经分配给子集I-VI之后哪个信道属于每个本地储存器的表格。如说明的，每个本地储存器现在仅包括信道C-G，因此，当然主储存器也仅包括信道C-G。应该理解在这个阶段，所有6个本地储存器是相同的。

图11A是一个表示如图11B所示在发射机#1已经从它的本地储存器借用信道C之后哪个信道属于每个本地储存器的表格。如图11B所示，因为发射机#1(交叉影线)属于子集II，并且因为子集II仅连接到另一个子集(子集I)，信道C仅仅从子集I和II的本地储存器去除而仍然保留在所有其它的本地储存器中，即子集III-VI的本地储存器中。

图12A是一个表示(如图12B所示)在发射机#21已经从它的本地储存器借用信道D之后并且在信道C已经被发射机#1返回之前哪个信道属于每个本地储存器的表格。因为如图12B所示发射机#21也属于子集II，并且因为子集II仅连接到另一个子集(子集I)，信道D如信道C一样也仅仅从子集I和II的本地储存器去除而仍然保留在所有其它的本地储存器中，即子集III-VI的本地储存器中。

图13A是一个表示(如图13B所示)在发射机#15已经从它的本地储存器借用信道C之后，在即使信道C还没有被发射机#1返回的情况下，哪个信道属于每个本地储存器的表格。因为发射机#1和#15分别属于没有连接的子集II和VI，所以这是可能的。因为如图13B所示发射机#15属于子集VI并且因为子集VI仅连接到另一个子集(子集IV)，信道C从子集VI和IV的本地储存器中去除而仍然保留在子集III和V的本地储存器中。

图14A是一个表示(如图14B所示)在发射机#17已经从它的本地储存器借用信道D后哪个信道属于每个本地储存器的表格。即使因为发射机#17和#21属于的子集VI和II没有连接，信道D被发射机#21使用，这也是可能的。因为如图14B所示发射机#17属于子集VI并且因为子集VI仅连接到另一个子集(子集IV)，信道D从子集IV和VI的本地储存器中去除而仍然保留在子集III和V的本地储存器中。

图15A是一个表示(如图15B所示)在发射机#1、#15、#17和#21每个返回它们使用的信道并且发射机#4已经从它的本地储存器借用信道C之后哪个信道属于每个本地储存器的表格。如图15B所示，发射机#4属于子集I和III。因为子集I连接到子集II、III和IV并且子集III连接到子集I和V，信道C从子集I-V的本地储存器中去除而仍然保留在子集VI的本地储存器中。

图16A是一个表示(如图16B所示)在发射机#8已经从它的本地储存器借用一个信道(发射机#4还没有返回它的信道)之后哪个信道属于每个本地储存器的表格。

图17A是一个表示(如图17B所示)在发射机#7和#9每个已经从它们各自的本地储存器借用信道(发射机#4和#8还没有返回它的信道)之后哪个信道属于每个本地储存器的表格。

图18A描述了在500毫秒的相对高信道请求密度时间周期上发射机#1-#10的时间序列。如所示，每个发射机可以是“高”状态或在“低”状态。“高”状态表示空闲(即没有请求的信道)，反之“低”状态表示有请求信道；

图18B是图18A的时间周期内“放大”的100毫秒时间周期。

图19A描述在500毫秒的相对低信道请求密度时间周期上发射机#1-#10的时间序列。如所示，每个发射机可以是“高”状态或在“低”状态。“高”状态表示空闲(即没有请求的信道)，反之“低”状态表示有请求信道。

图19B是图19A的时间周期内“放大”的100毫秒时间周期。

图20是用于图1连通矩阵发生器的优选操作方法的简化流程图说明。图20方法的输入是例如使用常规的欧几里德度量系统的空间中发射机位置的表示。根据FCC(联邦通信委员会)第15部分的规则，对于ISM频带的典型8级FSK(移频键控)调制系统，在规定的时间周期如近似于2秒钟，每个发射机完成对于所有其它发射机的载波测量。

最好除了载波测量以外，通过对于载波内存在的时钟给出一个FOM(品质因数)来测量发射机的相关检测率(CDR)。单元330连接了成对的信息，该信息即从单元310和320到达的有关相同发射机的信息。单元330的输出馈给包括循环块340、350和360的连通矩阵计算过程334。

连通矩阵发生器10操作时产生一个矩阵，该矩阵的元素表示系统中每对发射机之间的连通级别。在具有21个发射机的说明例子中，连通矩阵是一个21×21对称的矩阵，它的对角线是零。

图21是图1的发射机子集发生器20的优选工作方法的简单明了的流程图说明。在步骤410，准则(a)是参照上面图4描述的准则(a)。

在步骤430，对于每个未分配发射机，典型地通过计算它和不同分配的发射机中任何分配的发射机之间的最短距离，并且选择具有最小“最短距离”作为“最近的”未分配发射机来确定“最近的”。在这个步骤使用的度量不是欧几里德的，而是连通矩阵例如Minkowski的度量。

在步骤440，准则(a)-(e)是参照上面图4描述的准则(a)-(e)。

选择地完成步骤460。在这个步骤，使用常规的方法如在这里参照的Vose的出版物中描述的展开的原生算法的方法，优化在步骤400-450完成的发射机的分配。

图21方法的输出是典型的发射机子集向量，如附件E中示出的。

图22是用于图1的子集图形构造单元30优选工作方法的简化流程图说明。图22的方法接收如图21的方法产生的发射机子集向量，并且将每个子集作为图形中一个节点来处理。该方法加上边缘以连接具有公共发射机的每对子集，因此产生如图5图形的发射机子集图形。

图23是用于图1的子集图形上色单元40的优选工作方法的简化流程图说明。图23方法的输入是通过图22的方法产生的子集图形。在步骤610，“可利用的”颜色是还没有分配给任何节点的颜色。图23的输出是上色的子集图形。图6中说明了上色子集图形的例子。

图25是图1的本地储存器管理单元70的简化的状态机说明。每个发射机具有两种状态：空闲和“需要信道”。

在步骤830，术语“子集主机”指的是发射机属于的子集的主机，或者如果该发射机属于多个子集，指的是发射机属于的任何子集的任何主机。

图26是完成图25的最低成本信道计算步骤870的优选方法。

图27A-27B形成了术语“中心信道”、“相邻信道”和“相间信道”的说明的定义。图27A和27B分别是第一和第二发射机的频谱密度图。如所示，第一发射机的频谱(图27A)包括主瓣1010、第一旁瓣1020和1030、第二旁瓣1040和1050。第二发射机的频谱(图27B)包括主瓣1060、第一旁瓣1070和1080、第二旁瓣1090和1100。每个发射机的主瓣占用了称为该发射机‘中心信道’的信道。当说明书谈到发射机“借用信道”时，这意味着借用的信道变为该发射机的中心信道。

每个发射机的两个第一旁瓣占用两个各自的信道，它们称为发射机的两个“相邻信道”。每个发射机的两个第二旁瓣占用两个各自的信道，它们称为发射机的两个“相间信道”。因此，如果发射机A的中心信道是相邻信道或甚至是另一个发射机B的相间信道，则发射机A个B之间的干扰如图27A-B所示。

从发射机A相对于发射机B的观点来看，“零成本(zerocost)”借用指的是B借用了一个信道，而该信道的相邻信道或相间信道中没有一个与A的中心信道、相邻信道或相间信道重叠的情况。

从发射机A相对于发射机B的观点来看，“非零成本(non-zerocost)”借用指的是B借用了一个信道，而该信道的相邻信道或相间信道中至少一个与A的中心信道、相邻信道或相间信道中至少一个重叠的情况。

典型地，如果对于所有其他的发射机T，实际上由于借用处理引起的干扰不大于T的中心信道和任何一个T的相邻信道的幅度的比值，才允许发射机A借用该信道。

如果A的中心信道的幅度和B的中心信道的幅度的比值等于A的中心信道和相邻信道幅度的比值，由发射机B引起的对于发射机A的干扰电平称为“相邻信道干扰电平”。

类似地，如果A的中心信道的幅度和B的中心信道的幅度的比值等于A的中心信道和相间信道的幅度的比值，由发射机B引起的对于发射机A的干扰电平称为“相间信道干扰电平”。

典型地，如果两个信道在相同的储存器中，则它们之间没有干扰。

图28是发射机1500的示意说明，如输出通讯信道A、B和C(虚线)以及输入通讯信道D、E和F(实线)表示的，它以三种不同的方式与其他网络组成部分通讯。

如所示，发射机1500经过信道A将信息传送到围绕发射机1500的无线通讯包络内若干个网络部分1510中单独的网络组成部分1510’，发射机1500能够与规定的这些网络组成部分通讯。发射机1500经过信道B传送信息到另一个网络组成部分1520，该组成部分描述为与发射机1500在相同的子集1530中，不过也不必是这种情况。信道B是根据本发明优选实施例分派给发射机1500的信道。发射机1500经过信道C并且经过对于子集1530和1550公共的子集主机1540另外传送信息到子集1550中的发射机1560。

发射机1500经过信道D从围绕发射机1500的无线通讯包络内若干个网络组成部分1510中单独的网络组成部分1510”接收信息。发射机1500经过信道E从另一个网络组成部分1520接收信息，该组成部分描述为与发射机1500在相同的子集1530中，不过也不必是这种情况。信道B是根据本发明优选实施例分派给发射机1500的信道。发射机1500经过信道F并且经过对于子集1530和1550公共的子集主机1540另外接收来自子集1550中的发射机如子集1550中的发射机1560或任何其他发射机的信息。

图29是相同子集1530中两个发射机1500和1540同时通讯(分别与发射机1540和1520)的示意说明。这种情况是可能的，因为发射机1500中的一个正在使用分派给子集1530的信道，而其他发射机(子集主机1540)正在使用子集1530的控制信道。

现在描述用于产生子集的优选处理。

假定在一个限定范围内随机分布若干个发射机(接入点)，它们中的一些可以连接到有线网络，发射机可能相互干扰，并且引起网络中干扰。

下面的描述规定了在提供最大网络效率和性能的分段拓扑结构同时又保留最大的频率再用和健壮性中涉及的智能网络分段和接入引擎，即建立具有最大网络数据流的发射机之间强大连通的网络。

下面的方法将发射机分组到逻辑的子集中，它的实际特性是一个完整的图形(这里发射机是图形的顶点)。在多个发射机子集分段之后，子集图形产生。为了增强性能，产生的图形将满足一些要求(下面讨论)。

假设可利用有限的和不足数量的频率，图形上色用于分配最小需求的频率状态到子集图形。这个处理称为FCA(固定的信道分配)。在操作期间，本地频率组被定义(频率储存器组)，并且子集将根据信道要求从这个子集借用频率。

在多个子集的结构中，通过许多固有的拓扑结构特性，移动台对于子集覆盖表现出非动态并且每个移动台最好相关于该组中至少一个子集。通过后面跟随R-TDMA数据排序的信道请求捕获的时隙式-aloha(slotted-aloha)装置完成接入。由子集中特定的发射机接受的每个发射的数据实体将对于它解决的目标进行分析。随后的判定将经过子集(它这时假设被连接)转送这个数据实体到它的目的发射机(负责对于目的地最后接入步骤的发射机)。

初始和边界条件包括：

发射机组{AP}；

当dB是变换矩阵，且dB_ij是发射机(I)和发射机(J)的干扰比值的绝对值时的发射机内干扰变换；

对于以绝对值dB给出的相对干扰比值的规定的门限值；

子集上最小数量的发射机α_min；

子集上最大数量的发射机α_max；

每个发射机上最大数量的无线电接口p；

一组有限的离散频率{f}；以及

用于一个子集的固定数量的信道κ。

拓扑结构产生

下面描述的模型将发射机组映射到子集组{R}，同时保留：

1)边界条件：d、e和f

2)使属于单个子集的发射机最少，这可以通过

(Σ_{i}^{{R_{j}}} \frac{α_{{Rm}_{i}} - α_{{Rs}_{i}}}{α_{{Rm}_{i}} + α_{{Rs}_{i}}}, \frac{1}{R} Σ_{i = 1}^{1} α_{{Rs}_{i}} \cdot {(α_{{Rm}_{i}} - \overset{&OverBar;}{α_{Rm}})}^{2})

的最小化表达。

3)最大数量的不干扰的子集，这样频率再用可以实现。无干扰定义为

φ = {AP} | AP &NotElement; R_{i} \cap R_{j}

，i＝1…R，j＝1…R，i≠j

4)当邻近小集团定义为

{C_{i}} = {AP} | AP &NotElement; R_{i} \cap R_{j}

，j＝1…R，i≠j时，子集属于的小集团最小化。

当Cost_i定义为Cost_i＝Cost_c+ ωCost_φ，

{Cost}_{c} = \min (Σ_{i = 1}^{{| | c}_{R} | |} α_{Ri}),

Cost_φ＝minφ，d是不同构象的数量(可能的组合)，以及 ω是加权因子时，给定的子集拓扑结构的排列定义为min(Cost₁，…，Cost_d)。

假设子集的产生跟随着每个发射机的产生(可能的能量传输)，同时发射机的去除不引起子集变化直到一些预定成本函数被破坏为止(这个成本函数可以是吞吐量准则，连通丢失、特别的外部干扰等)。

运行在系统上的信道分配引擎经过子集拓扑结构完成分配(图形上色)，这样因为图形小集团包含较少的子集，所以需用于上色图形的固定频率的数量(顶点颜色)变得较少。

图30和下面的描述是在初始条件下用于子集产生、且满足上面列出的要求的逐步进行的模型。

一开始选择的AP_k位于发射机群的“质心”，即满足下面的条件，

当NN＝‖{AP}‖时，

Σ_{j} d B_{kj} \min {Σ_{j} d B_{ij}}_{i = 1}^{N}

通过使用下面的方式将发射机集成到第一次分配来构造第一子集，

R_{1} = {A P_{k}} + {{AP}_{s}}_{s = 2}^{α_{\max}} | {dB}_{ks} \leq {dB}_{kl} &ForAll; l = s + 1 . . N, {dB}_{ks} \leq {dB}^{(th)}

剩余的子集用两个迭代的步骤建立，步骤1选择的发射机是对于所有准备好的现有子集最近的发射机，步骤2集成的发射机将是先前的子集和当前的子集之间的连接发射机。在步骤3，选择另外的自由发射机直到定义的边界为止。步骤1：选择的AP_k位于发射机群的“质心”，即满足下面的条件，

当j运行在现有子集的发射机上，并且AP_k从自由的发射机中选择时，∑_jdB_kj＝min{∑_jdB_ij}。

步骤2：选择{AP}_i ^min使得每个AP_j属于现有的子集，并且AP_j保留条件f，在任何现有的子集中没有其它的发射机，它对于APk的dB小于APj对于APk的dB。

经过步骤1和2从自由的发射机组完成子集到α_max。

HCA

假设没有扩展，要求该系统解决信道分配问题。一般地，信道分配速率通过它的频谱间隔(它最好是所需最小的)和阻塞概率(阻塞被定义为当需要信道但不能利用时的情况)加权。

信道分配处理可以分为两个不同的操作状态(因此这是一个混合处理)：

固定信道分配(FCA)-它分配给定数量的信道到每个子集κ，并且通过这样做来确保子集业务量连通。

动态信道分配(DAC)-它用作子集信道要求的信道储存器。由于子集信道要求速率是时空的(时间和范围即子集的函数)，不同的储存器将在工作状态期间逐渐形成。

FCA

通过将κ种颜色分配给每个子集并且通过将这些颜色映射到信道组中，在子集图形上完成彩色上色，参见图31上色的说明。在这样做之后，新的信道组被定义(没有分配的信道组)并且命名它作为信道储存器组。

不定向图形G的上色是分配颜色给G的节点，使得没有任何G相邻的节点具有相同的颜色。G的彩色数量是需用于覆盖G的最小数量的颜色。

当C_n(G_R)是G_R的彩色数量时‖{f}_res‖＝‖{f}₀‖-κ·C_n(G_R)。

通过简单的隐式计数树搜索方法来完成上色。一开始，节点1被分配颜色1，其余的节点被顺序地上色使得节点I采用最低编号的颜色上色，该颜色还没有用于对相邻于节点i的任何节点上色。假定p是通过这种合理的上色要求的颜色数量。尝试使用q＜p种颜色产生合理的上色。为了实现这一点，所有采用p上色的节点必须被重新上色。这样，追溯步骤可能继续到节点u，这里节点u+1是分配颜色p的最小下标。试图对于彩色节点u采用比当前颜色大的最小合理的另一种颜色。如果没有这样的小于p的另一种颜色，则追溯到节点u-1。否则，采用最小合理的颜色对节点u重新上色并且继续向前，顺序地重新上色所有的节点u+1、u+2，…，直到节点n被上色或一些节点v达到颜色p的要求。在前一种情况下，已经找到使用q种颜色的改进的上色；在这种情况下追溯并且尝试使用小于q种颜色找到更好的上色。在后一种情况下，如前面由节点v追溯并且继续向前。当追溯到达节点1时算法终止。

DCA

如上面定义的，在FCA过程之后在储存器中存在‖{f}_res‖可利用信道。{f}_res分配到G_R中每个子集。每个子集根据内部请求从这个组中借用信道。从储存器借用信道的准则如下定义：

对于给定的子集请求的最近邻近的图形G_nn被这样定义：当V＝{R₁，…R_R}并且E＝{R_i，R_j}使得R_i∩R_j≠0|i≠j时G_nn＝{V，E}。当{f}_{小集团R}＝{f}_self-{f}_nnR时，对于给定子集来自{f}_res的可利用信道被定义为{f}_R＝{f}_res-{f}_小集团R。

现在规定基于DCA建议的信道借用的阻塞概率，并且这样证明子集拓扑结构产生模型条件。

当是在小集团或子集R中使用的所有信道的统一组并且{f}_冲突R是冲突的信道(以后讨论)组时

_团R-{f}_冲突R。换句话说，

表示邻近请求，以及

。从这些符号，很清楚{f}_小集团R取决于邻近小集团的业务量。应该理解最好是需用于构造‖{f}_res‖的信道数量，以这种方式使得在系统中不会出现阻塞。

在FCA之后R子集需要如峰值要求的α_R-1信道，这样以便消除阻塞概率

并且。由这一点，最小的α_R或‖c_R‖将导致‖{f}_res‖_min的最小化，记得‖{f}_res‖_min是R上的向量。

假设‖{f}_冲突R‖是给定的常数，则系统级别最佳化通过

Σ_{i = 1}^{R &Element; G_{m}} {| | {f}_{{res}_{i}} | |}_{\min}

的最小化给出。这样，阻塞概率P_B()_R能够通过

P_{B} {()}_{R} = \min (1, \frac{{| | {f}_{resR} | |}_{\min}}{| | {f}_{resR} | |})

给出。注意：概率衰减的陡峭性是业务量要求和接入装置的函数。

接入

如子集产生描述的，发射机被作为有线图形的顶点寻址，并且被分组到高连接的子集中。逻辑上每个子集用作网络分段，这样同网络一样，每个子集变为无线小区。在特定子集的覆盖区域下漫游的移动台(移动用户)经过子集“网关”-发射机接收和传送信息(基于信息包的方式)。发射机搜集它的信息和这个信息如何在网络上传递对于移动台是不重要的。

现在描述两个分层协议：子集内协议也称为无线电MAC协议，它负责无线电处理上的协调和消息输出；以及

子集协议负责子集发射机控制、频率分配和子集内的连接性。

下面是协议的一般性描述以及相关的数学模型。

描述的接入方法完成两个主要的任务：协调和空中高容量数据处理。每个任务被限制于一些边界条件：MAC的协调函数被限制于完成传输请求捕获和子集上发射机的定时同步。MAC的处理部分称为LLC(链路层控制)并且它的目的是处理信道请求(从频率分配的角度)，并且处理无线电信道上的数据业务量。

子集上每个发射机单独地完成基于时隙式-Aloha的接入请求捕获并且随后处理R-TDM状态下的传输。为了完成协议的R-TDM部分，DCA算法通过请求的发射机激活(这些请求经过子集介质发送到子集主机-它是发射机中的一个)。

发射机周期地接受许可以产生时隙式-aloha争用窗口。使用专用的信道，它经过无线电发送CCLR广播信息包(争用开始通知)。在响应中，通过发送基于随机接入的RTS(请求发送)控制帧，所有没有与某些发射机接合的激活的移动台在这个处理中进行争用。发射机存储所有的接入请求在请求缓存器中(RTS队列)。使用规定的队列作为FIFO，它查询等待的移动台用于数据传输。在从子集一侧寻址移动台的情况下，使用反向查询。

因为时隙式aloha装置对于随机化种子(seed)的正确性非常敏感，通过和相同子集的其余的发射机商量，该发射机应该计算在下一个aloha争用窗口的子集中激活的移动台的估计数量，并且随后将这种了解包括在CCLR控制帧上可能的争用者中。

第二层协议完成三种主要的任务：

用于发射机子集群的时隙式-aloha争用定时的令牌控制传递，

用作信道分配协调的主干：请求和释放频率基本频带；以及

控制和传送子集邻近小集团中发射机之间的数据业务量。

这是一个基于令牌的协议，并且在同一个子集上可以存在两种类型的令牌。子集协调令牌的目的是协调时隙式-aloha争用定时。一旦接收到这样一个令牌，在需要经过无线电传输的情况下(RTS队列不是空的，或者存在可利用数据用于无线电台)发射机在子集信道转送回来自子集主机的请求(不同的或相同的发射机)。主机最好通过允许或拒绝该信道立刻响应(这时通知所有邻近的子集群)。注意这个令牌仅在它所属的子集(home Subset)内滚动，并且它对于邻近小集团中的邻近子集是透明的。第二个令牌类型在邻近小集团中滚动，即在所有的邻近子集上循环。它用作如令牌子集接入允许，一旦接收它，就允许不空闲的发射机传送它的数据信息包(达到在时间单位给出的一些预定的短脉冲串长度)。

以下面的方式完成目的地址分析。一旦接收到数据信息包(对于它的源位置是不变的)，发射机将它与子集当前群相比较，即假设每个发射机具有关于在相同子集上所有发射机的当前地址队列状态的完整信息。如果目的地址位于子集(邻近子集上没有信息)，发射机将这个信息包转送到所属发射机(home-transmitter)，否则这个信息包被寻址为没有解决的，并且被传送到邻近子集，以这种方式这个信息包将在整个邻近小集团中循环。

每个发射机从子集拓扑结构观点完成IP路由。经过子集拓扑结构传送的每个数据信息包采用它的初始无线电发射机(所属发射机)IP地址来封装。目的发射机子集(目的移动台位于后面的发射机子集可以是有线LAN或移动台)剥去这个封装，并且将源发射机IP映射到MAC信息包地址。

为了避免信息包循环和广播风暴扰动(storm)，实现最小生成树自配置。

由于系统条件作为时间相关干扰和改变的业务量状态的函数变化，生成树图形被周期地重新计算。目标被定义如下：采用给定的边缘长度(在我们的情况下的业务量和它典型的BER)考虑无向图G。目标是找出G中的生成树使得树中的边缘长度总和最小，参见图32。

下面的处理在G(子集图形)上获得这个目标。一开始，设置T是空的。考虑边缘以它们长度(成本)的非降低次序包括在T中。如果一个边缘不和已经在T中的边缘形成一个环则它包括在T中。当n-1个边缘包括在T中时形成最小的生成树。在实现中，边缘在堆结构的底部采用它们最小的边缘部分地分类(一个二进制树，其中每个节点的加权不大于它儿子(son)的加权)。上面处理的运行时间是0(mlogm)，这里m是图形中边缘的数量。

基本的小区结构如下面所描述并且在图33中说明。箭头表示数据流。它假设调查的发射机的队列性能由6个随机过程管理：

A.经过子集中空中协议的队列相加(不考虑目的地位置)；

B.经过子集协议来自位于相同子集中另一个发射机的队列相加，即目的地址是在调查的发射机队列中；

C.经过子集协议来自不位于相同子集的另一个发射机的队列相加，即目的地址在调查的发射机队列中；

D.经过子集中协议的队列相减，即目的地位于调查的发射机之后，并且在发射机队列中反映出来；

E.经过子集协议的队列相减，即目的地位于相同子集的发射机之后；以及

F.经过子集协议的队列相减，即目的地位于相同子集的发射机之后，但是它的目的发射机不是子集成员。

假设一个队列动态特性的隐藏马尔可夫模型。从这些队列的集成中构造一个系统级模型。队列动态特性经过随机方程式确定，在事件阶越跳转时间(event-step-jump time)计算。这些方程式以及它们相互联系的推导如下所示。

{Q}₀{P}{dQ}{Q}_Δt

{dQ}{Uy}_Δt

{Q}_Δt{DL}_Δt

当{Q}_Δt＝{Q}_-Δt+{dQ}时

1)A过程的构造

单个移动台对于单个时隙式-aloha的基本进入概率通过

\frac{1}{n_{E}} {(1 - \frac{1}{n_{E}})}^{n_{n} - 1}

给出。n_E是争用移动台的估计数量，n_a是实际的争用移动台数量。假定概率分布Γ(n)规定子集中任何两个移动台具有某一dB门限值差值即在相同时隙上有部分干扰的概率，对于相同时隙上u个移动台冲突的时隙成功得到的概率可以估计为

\frac{1}{{n_{E}}^{u}} {(1 - \frac{1}{n_{E}})}^{n_{n} - u} \cdot Γ^{k} (n), k = \frac{u (u - 1)}{2}

；这样，有BER的整个时隙接入概率通过

P_{A} = S \cdot Σ_{u = 1}^{n_{u}} \frac{1}{n_{E}^{u}} {(1 - fer)}^{u} {(1 - \frac{1}{n_{E}} (1 - fer))}^{n_{u} - u} \cdot Γ^{k} (n)

给出；S是时隙-aloha窗口中时隙的数量。

激活的移动台的数量通过是子集中发射机的RTS队列中移动台的数量。

经过一些算法形式最好地表示激活移动台的估计数量。随着估计误差增加，经过aloha装置的接入等待时间非线性的增加。

假定一个移动台进入传输请求队列的概率，它最好转换为实际的信息包数量：ΔQ_RTS＝min(1，P_A)·n_a；因为用于概率估计的时间阶越是传递持续时间的aloha令牌的Δt_CCLR，并且它非常短，ΔQ_RTS不能立刻转换到信息包队列。这样，计算和分配实际的到达时间。假设定义到达时间向量

Q_{arr} = {t_{0} + \frac{P_{L_{t}}}{{Rate}_{Air}}, \dots, t_{0} + \frac{P_{L_{ΔQRTS}}}{{Rate}_{Air}}},

t_{0} = t_{prev} + \frac{{Δ t}_{CCLR}}{P_{f}}

；P_f是经过DCA处理的允许频率的概率，t_prev是先前信息包到达的时间(初始时间是浮动时间t)。

2)B和C过程的构造

定义P_DR是在给定子集中产生的信息包发送到相同子集中的移动台的概率。目的地址位于调查的发射机队列的概率由t_prev给出；当n^(Ri)是子集中总的移动台数量时(激活的和空闲的)，这个表达式假设信息包的目的地址在地址范围上均匀地分布。这样，调查的发射机最好能够控制的信息包的数量通过

R_{Q_{B}} = (\frac{Q_{RTS}^{j}}{n^{(R_{i})}}) \cdot Σ_{\overset{k = 1}{k &NotEqual; j}}^{α_{R_{1}}} (P_{DR} {\cdot Q}_{RTS}^{k})

给出；这时j是调查的发射机。C过程-队列相加是由于信息包来自相同邻近小集团的远端子集。对于调查的发射机控制这样一个信息包的概率通过

P_{Qc} = \frac{Q_{RTS}^{j}}{Σ_{i = 1}^{| | c | | - 1} R^{(i)}}

给出；这时

Σ_{i = 1}^{| | C | | - 1} R^{(i)}

是邻近小集团中子集的数量，不包括调查的发射机的子集。这里假设所有的子集工作在相同的工作状态。

结合两个过程(B和C)，提供在Δt_CCLR间隔通过调查的发射机控制的整个邻近小集团内产生的信息包的数量。假定子集令牌给发射机，它可以在

{Δt}_{TR} = \frac{Br}{{Rate}_{R}}

给定的规定时间周期经过子集传送；这时Br是最小信息包中短脉冲串长度。这样，通过调查的发射机控制的信息包的数量由

{ΔQ}_{B + C} = (\frac{P_{Q_{B}} + P_{Q_{C}}}{Σ_{k = 1, k &NotEqual; j}^{| | C | |} R^{(k)}}) \cdot [\frac{{Δt}_{CCLR}}{{Δt}_{TR}} {\cdot Rate}_{R}]

给出；这时

[\frac{{Δt}_{CCLR}}{{Δt}_{TR}} \cdot {Rate}_{R}]

是在Δt_CCLR持续时间期间传送的信息包数量(这可以是信息包百分率)。

3)E和F过程的构造

调查的发射机需要传送给邻近小集团(不是它自己的空中)的概率通过

P_{E + F} = 1 - P_{DR} \cdot \frac{Q_{RTS}^{j}}{n^{(R_{i})}} - (1 - R_{DR}) \cdot Q_{RTS}^{j}

给出并且在简化这个表达式

P_{E + F} = 1 - Q_{RTS}^{j} (P_{DR} \cdot (\frac{1}{n^{(R_{i})}} + 1) - 1)

之后；将这个概率表达式变换为由

q_{RTS}^{j} \cdot [1 - Q_{RTS}^{j} (P_{DR} \cdot (\frac{1}{n^{(R_{i})}} + 1) - 1)]

给出的信息包数量；这样，由调查的发射机传送到邻近小集团(表示它自己的子集上)的信息包的数量由

Δ Q_{E + F} = \frac{Q_{RTS}^{j} \cdot [1 - Q_{RTS}^{j} (P_{DR} \cdot (\frac{1}{n^{(R_{i})}} + 1) - 1)]}{N \cdot Σ_{k = 1}^{| | C | |} Q_{RTS}^{k}} \cdot [\frac{Δ t_{CCLR}}{Δ t_{TR}} \cdot {Rate}_{R}]

给出；这时N是在整个邻近小集团上发射机的数量并且由

N = Σ_{k = 1}^{| | c | |} α_{R_{k}}

给出。

这里包括的上面描述假设用于子集内发射机之间通讯的环路协议和用于子集中发射机之间通讯的循环时隙式ALOHA。

本发明优选实施例的一个特别优点是该设备的适用性不限于在具有干扰空间特定的发射机分布的通讯系统。典型地，常规的系统适用于特定的、对称的发射机拓扑结构。根据本发明优选实施例，该设备适用于实际上任何发射机拓扑结构，并且特别适用于发射机是移动的并且因此发射机拓扑结构随着时间改变的应用中。

本发明优选实施例的另一个特别的优点是属于多个子集的发射机特别适用于作为转发，即转发发射机属于的子集之间的信息。

每个子集的最大数量的发射机典型地由子集传输速率确定。例如，如果子集介质的速度是100mbps并且每个发射机能够传送最多10mbps，则典型地不能有多于10个发射机被允许属于每个子集以便防止信道浪费。

本发明的优选软件实现在附件A-C中说明，它包含本发明软件实施例的计算机列表。

附件A和B是在本发明软件中实现的另外的实施例，它们接收如图1单元10产生的发射机连通矩阵作为输入，并且实现图1的单元20、30、34和40的功能。

附件C是用于提供附件A或附件B方法的管理最佳化循环的优选技术的软件列表。

用于提供管理最佳化循环的优选方法在上面参考的Vose出版物中描述。

附件D是用于附件A或B的初始化文件。

附件E是通过运行包含图24数据的附件A或附件B的ASCII文件产生的输出文件的例子。

附件F是完成图1的单元60和70功能的Matlab过程的软件列表。该过程运行在Matlab(矩阵实验室)for Windows，Version5.0以上并且可以从MathWorks Inc.，Cochituate Place，24 PrimePark Way，Natick，MA 01760，USA市场上获得。该过程接收附件A或B的输出作为输入，如附件E的示范输出。

图24是一个适用于附件A或附件B的输入格式的表格。图24的表格内容是适合表示当前说明书中图2-图19B例子的输入例子。

利用附件A-附件C的计算机列表的优选方法如下：

a.使用备有Delphi Pascal的PC 486，在如附件A-C所示的适当的标题(单元，接口，使用，常数等)下，产生附件A和B或C的内容的单元和键控。

b.使用Delphi Pascal的“主”程序编辑和运行软件。

应该理解如果需要，本发明的软件部分可以用ROM(只读存储器)形式实现。一般地，如果需要，软件部分可以使用常规的技术采用硬件实现。

应该理解附件中描述的特定实施例只是提供本发明公开的细节并不打算用于限制。

应该理解为了清楚起见，从分开的实施例角度描述的本发明的各种特性也可以在单个实施例中组合地提供。相反地，为了简洁起见，从单个实施例角度描述的本发明各种特性也可以单独地或在任何适当的局部组合中提供。

本领域的技术人员应该理解本发明不限于上面特别示出和描述的内容。本发明的范围仅仅通过下面的权利要求书来规定。

附件A

   unit Ring_generation_routine；
   interface
   uses

      Windows，Messages，SysUtils，Classes，Graphics，Controls，Forms，
   Dialogs，

      StdCtrls，ExtCtrls；
  const

           MaxNumofAP＝500；

           MaxNumOfRings＝50；
  type

      TForml＝class(TForm)

         Button1：TButton；

         Button2：TButton；

         Panell：TPanel；

         Edit1：TEdit；

         Button3：TButton；

         procedure Button1Click(Sender：TObject)；

         procedure Button2Click(Sender：TObject)；

         procedure Button3Click(Sender：TObject)；

     private

         (Private declarations)

     public

         (Public declarations)

     end；
 var

     Forml：TForml；

     (I/O related variables)
    K_File          ： string；

    Mass_File       ： string；

    R_File          ： string；

    V_File          ： string；

    A_File          ： string；

    inifile         ： string；

    WriteOut        ： string；

    Ini_file        ： TextFile；

    Out_File        ： TextFile；

    (Common variables)

    NumofAP         ： Word；
   MaxP_onRing      ： Word；
   MaxRing_forAP    ： Word；
   Sensitivity      ： Integer；
   Rings            ： Word；
   Ring             ： array [1..MaxNumOfRings，1..MaxNumofAP] of Integer；
   procedure Initiation；
   procedure Main_Loop；
   procedure Generate_Rings；
   procedure Output；
implementation
				
				<dp n="d35"/>
(SR  *.DFM)
 Procedure main_loop
 begin

　　　　    initiate；

　　      Generate_Rings；

　　      Output；
 end；
 procedure Initiation；
 var

　　  i，j；Word；
 begin

　　     Randomize；

　　     inifile：＝′d：\sim\MAC-Sim\5GHz\ring.ini′；

　　     AssignFile(Ini_File，inifile)；

　　     Reset(Ini_File)；

　　          Readln(Ini_File，NumofAP)；

　　          Readln(Ini_File，Sensitivity)；

　　          Readln(Ini_File，MaxAP_onRing)；

　　          Readln(Ini_File，MaxRing_forAP)；

　　          Readln(Ini_File)；

　　          Readln(Ini_File，K_File)；

　　          Readln(Ini_File，WriteOut)；

　　     CloseFile(Ini_File)；

　　     (read the K Map)

　　     AssignFile(Ini_File，K_File)；

　　     Reset(Ini_File)；

　　          for i：＝1 to NumofAP do

　　              begin

　　                for j：＝i to NumofAP do read(Ini_File，K_Map[i，j])；

　　                readln(Ini_File)；

　　              end；

　　     CloseFile(Ini_File)；
end；
procedure Generate_rings；
var
Temp，i：Word；
Distance：array[1..MaxAP，1..MaxAP]of Word；
Temp_Distance，Pointr：array[1..MaxAP]of Word；
NumOfRings：Word；
begin

　　 NumOfRings：＝0；
(CALCULATE THE DISTANCE MATRIX FROM AP LOCATION MATRIX-THE EUCLIDEAN
CASE)

　　 for AP_a：＝1 to NumofAP do

　　   for Ap_b：＝1 to NumOfAP do

　　     Distance[AP_a，AP_b]：＝Sqrt(Sqr(Field[AP_a，1]-Field[AP_b，1])
				
				<dp n="d36"/>
　　                                                 +     Sqr(Field[AP_a，2]-Field[AP_b，2]))；

　　       for i：＝1 to NumofAP do

　　          for AP_a：＝1 to NumofAP-1 do

　　              for AP_b：＝AP_a+1 to NumOfAP dp

　　                 if Distance[i，AP_a]＞Distance[i，AP_b] then

　　                    begin

　　                      Temp：＝Distance[i，AP_b]；

　　                      Distance[i，AP_b]：＝Distance[i，AP_a]；

　　                      Distance[i，AP_a]：＝Temp；

　　                    end；

　　      for AP_a：＝1 to NumofAP do

　　          for AP_b：＝1 to NumOfAP dp
  (FIND THE AP THAT IS THE MASS CENTER OF THE CLOUD)

　　   for AP_a：＝1 to NumOfAP do Temp_Distance[AP_a]：＝0；

　　   for AP_a：＝1 to NumOfAP do

　　     for AP_b：＝1 to NumOfAP do

　　       Temp_Distance[AP_a]：＝Temp_Distance[AP_a]+Distance(AP_a，AP_b]；

　　   Temp：＝1；

　　   for AP_a：＝2 to NumOfAP do

　　     if Tamp_Distance[AP_a)＜Temp_Distance[Temp)then Temp：＝AP_a；
 (GENERATE FIRDT RING)

　　  Pointr[1]：＝1；

　　  Ring[1，1]：＝Temp；

　　  Inc(RingsOnAP[Temp])；

　　  for AP_a：＝1 to MaxAP_onRing-1 do

　　    begin

　　      Inc(Pointr[1])；

　　      Ring(1，
procedure Output；
var
   i，j：Word；
begin

　　 AssignFile(Out_File，WriteOut)；

　　 Rewrite(Out_File)；

　　 for i：＝1 to Rings do

　　     begin

　　        write(Out_File，′Ring′，i：3，′：′)；

　　        for j：＝1 to NumofAP do

　　             write(Out_File，K_Map[NumofAP+1-i，j])；

　　        writeln(Out_File)；

　　     end；

　　 CloseFile(Out_File)；
end；
procedure TForml.ButtonlClick(Sender：TObject)；
begin

　　Panell.visible：＝true；

　　Main_Loop；
				
				<dp n="d37"/>
　　   Panell.Visible：＝false；
end；
procedure TForml.Button2Click(Sender：TObject)；
begin

　　Halt；
end；
procedure TForml.Button3Click(Sender：TObject)；
begin

　　  inifile：＝editl.text；

　　  Button1.Visible：＝true；

　　  Button2.Visible：＝true；

　　  Edit1.Visible：＝false；

　　  Button3.Visible：＝false；
end；
end.

附件B

 unit MAC_5GHz；
 interface
 uses

　　Windows，Messages，SysUtils，Classes，Graphics，Controls，Forms，
 Dialogs，
   StdCtrls，ExtCtrls；
 const

　　  MaxNumofAP      ＝    200；

　　  MaxNumofRings   ＝     80；

　　  MaxNumofRings3  ＝    210；

　　  H_MaxNumofAP    ＝     50；
type
  TForml＝class(TForm)

　　Button1：TButton；

　　Bunton2：TButton；

　　Panell：TPanel；

　　Edit1：TEdit；

　　Button3：TButton；

　　procedure Button1Click(Sender：TObject)；

　　procedure Button2Click(Sender：TObject)；

　　procedure Button3Click(Sender：TObject)；
  private

　　(Private declarations)
  public

　　(Public declarations)
  end；
var
  Form1：TForml；
  (I/O related variables)
  K_File             ： string；
  Mass_File          ： string；
  R_File             ： string；
  V_File             ： string；
  A_File             ： string；
  inifile            ： string；
  WriteOut           ： string；
  Ini_file           ： TextFile；
  Out_File           ： TextFile；
  (Common variables)
  NumofAP         ： Word；
  MaxAP onRing    ： Word；
  MaxRing_forAP   ： Word；
  Sensitivity     ： Word；
  Rings           ： array[1..MaxNumofRings，1..H_MaxNumofAP]of Word；
  MinAP_onRing    ： Word；
  R               ： Word；
  Termination     ： Boolean；
  R_Point         ： array[1..MaxNumofRings]of Word；
  First_In_Ring   ： array[1..MaxNumofRings]of Word；
  Free Pointr     ： Word；
  Treshold        ： Single；
  Option          ： Word；
				
				<dp n="d40"/>
   Distance_Parameter ： Word；
   Rings_OnAP       ： array [1..MaxNumofAP]of Byte；
   K_Map            ： array [1..MaxNumofAP，1..NaxNumofAP]of Word；
   Distance， d     ： array [1..MaxNumofAP，1..MaxNumofAP]of Single；
   Free_List        ： array [1..MaxNumofAP]of Word；
   Graph            ： array [1..MaxNumofRings，1..MaxNumofRings]of Word；
   procedure Generate_Locations；
   procedure Initiation；
   procedure Generate_rings；
   procedure Generate_Ring_Graph；
   procedure Output；
   procedure Main_Loop；
implemantation
(SR *，DFM)
(****************************)
procedure main_loop；
begin
　　 initiation；

　　 Generate_rings；

　　 Generate_Ring_Graph；

　　 Output；
end；
(****************************)
procedure Generate_Locations；
var
   i，j：Word；
begin

　　 Randomize；

　　 AssignFile(Ini_File，K_File)；

　　 Rewrite(Ini_File)；

　　 Case Option of

　　      1：for i：＝1 to NumofAP do

　　           writeln(Ini_File，Random(300)+1，′′，Random(300)+1)；

　　                                 ′
　　      2：for i：＝1 to Trunc(Sqrt(NumofAP)+1) do

　　           for j：＝1 to Trunc(Sqrt(NumofAP)+1) do

　　             writeln(Ini_File，10+i*10，′′，10+j*10)；

　　end；(of Case)

　　ClcseFile(Ini_File)；
end；
procedure Initiation；
				
				<dp n="d41"/>
  var

　　 i，j：Word；

　　 Location：array[1..MaxNumofAP，1..2]of Word；
  begin

　　   inifile：＝′d：\sim\MAC-Sim\5GHz\ring.ini′；

　　   AssignFile(Ini_File，inifile)；

　　   Reset(Ini_File)；

　　        Readln(Ini_File，NumofAP)；

　　        Readln(Ini_File，Sensitivity)；

　　        Readln(Ini_File，MinAP_onRing)；

　　        Readln(Ini_File，MaxAP_onRing)；

　　        Readln(Ini_File，MaxRing_forAP)；

　　        Readln(Ini_File)；

　　        Readln(Ini_File，Option)；

　　        Readln(Ini_File，K_File)；

　　        Readln(Ini_File，WriteOut)；

　　   CloseFile(Ini_File)；

　　   Generate_Locations；

　　   (read the the AP Location Map ＝＝＝＝  if the user choice is″Random″
 then

　　    skipp this reading loop)

　　   AssignFile(Ini_File，K_File)；

　　   Reset(Ini_File)；

　　        for i：＝1 to NumofAP do

　　            readln(Ini_File，Location(i，1)，Location[i，2])；

　　   CloseFile(Ini_File)；

　　   (Calculate the Distance Matrix)

　　   Distance_Parameter：＝1；(Euclidian)

　　   Case Distance Parameter of

　　     1：for i：＝1 to NumofAP do

　　                      for j：＝1 to NumofAP do

　　                        Distance[i，j]：＝SQRT(Sqr(Location[i，1]-
Location[j，1])+

　　                                               Sqr(Location[i，2]-
Location[j，2]))；

　　   2：        for i：＝1 to NumofAP do

　　                     for j：＝1 to NumofAP do

　　                       if i＜＞j then

　　                          Distance[i，j]：＝Location[i，1]-Location[j，1]
else

　　                          Distance[i，j]：＝0；

　　 end；(of case)

　　 (initiate working arrays and variables)

　　 for i：＝1 to MaxNumofRings do

　　   begin

　　     R_Point[i]：＝0；

　　     First_In_Ring[i]：＝0；

　　   end；
   R：＝0；
end；
procedure Generate_Rings；
				
				<dp n="d42"/>
  procedure WorkArea；(generate a working metrix for the distances]
  var

　　 i，j ：Word；
  begin

　   for i：＝1 to NumofAP do

　　       for j：＝1 to NumofAP do d[i，j]：＝Distance[i，j]；
  end；
  procedure FreeAP；(Find the free-APs)
  var

　　 i，j，k：word；

　　 K_Not_Free：Boolean；
 begin

　　         for k：＝1 to NumOfAP do

　　           begin

　　             K_Not_Free：＝False；

　　             for i：＝1 to R do

　　                 for j：＝1 to R_Point[i] do

　　                     if Rings[i，j]＝k then K_Not_Free：＝True；

　　             if not(K_Not_Free)then

　　                begin

　　                 Inc(Free_Pointr)；

　　                 Free_List[Free_Pointr]：＝k；

　　                end；

　　           end；
　　  (check if all APs are assigned)

　　  if Free Pointr＝0 then Termination：＝True

　　    else Termination：＝False；
 end；
 var (of ring-generation Procedure)
 i，j，Min_Indx，Min_Indx_to：Word；
 k，l，m：Word；
 Left：Word；
 Min：Single；
 Temp，Temp_indx：array[1..MaxNumofAP]of Word；
 begin

　　  Min_Indx：＝65000；

　　  WorkArea；

　　  (find Cluster center)

　　  for i：＝1 to NumofAP do Temp[i]：＝0；

　　  for i：＝1 to NumofAP do

　　      for j：＝1 to NumofAP do Temp[i]：＝Temp[i]+Trunc(1+d[i，j])；

　　Min：＝65000；

　　for i：＝1 to NumofAP do

　　    if Temp[i]＜Min then

　　      begin

　　           Min：＝Temp[i]；

　　           Min_Indx：＝i；

　　      end；

　　Inc(R)；

　　Inc(R_Point[R])；

　　Rings[R，R_Point[R]]：＝Min_Indx；
				
				<dp n="d43"/>
　　       First_In_Ring[Min_Indx]：＝1；

　　       (update number of rings per AP)

　　       Inc(Rings_OnAP[Min_Indx])；

　　       (add the rest of the APs to the ring)

　　       for j：＝1 to MaxAP_onRing-1 do

　　         begin

　　           Min：＝65000；

　　           for i：＝1 to NumofAP do

　　             if(d[Rings[R，1]，i]＜Min) and

　　               (d[Rings[R，1]，i]＞0) then

　　               begin

　　                    Min：＝d[Rings[R，1]，i]；
　　                    Min_Indx：＝i；

　　               end；

　　          Inc(R_Point[R])；

　　          Rings[R，R_Point[R]]：＝Min_Indx；

　　          d[Rings[R，1]，Min_Indx]：＝0；

　　          (update number of rings per AP)

　　          Inc(Rings_OnAP[Min_Indx])；

　　        end；

　　      (GENERATE ALL OTHER RINGS)

　　      (find the nearest Free-AP to one of the rings APs)

　　       Termination：＝False；

　　       While not(Ternination) do

　　         begin

　　           WorkArea；

　　           Free_Pointr：＝0；

　　           FreeAP；

　　           [For all Free APs find the AP that has the closest NOT-Free
AP)

　　           Min：＝65000；

　　           for i：＝1 to Free_Pointr do

　　               for j：＝1 to NumofAP do

　　                 if (d[Free_List[i]，j]＜Min) and (d[Free_List[i]，j]＜0) and

　　                    (First_In_Ring[i]＝0)and(Rings_OnAP[j]＞0) then

　　                   begin

　　                     Min：＝d[Free_List[i]，j]；

　　                     Min_Indx：＝i；

　　                   end；

　　          if Min＜65000 then

　　             begin

　　               Inc(R)；

　　               Inc(R_Point[R])；

　　               Rings[R，R_Point[R]]：＝Free_List[Min_Indx]；

　　               d[Rings[R，1]，Free_List[Min_Indx]]：＝0；

　　               First_In_Ring[Free_List[Min_Indx]]：＝1；

　　               (update number of rings per AP]

　　               Inc(Rings_OnAP[Free_List[Min_Indx]])；

　　             end；
				
				<dp n="d44"/>
　　            (perform the first stage of generation：co-locate all
   connected

　　             APs up to min treshold)

　　            for j：＝1 to MinAP_onRing do

　　                begin

　　                     Min：＝65000；

　　                     for i：＝1 to NumofAP do

　　                         if(d[Rings[R，1]，i]＜Min)and(Rings_0nAP[i]＞0)
  and

　　                           (Rings_OnAP[i]＜MaxRing_forAP) and

　　                           (d[Rings[R，1]，i]＞0)then

　　                           begin

　　                                Min：＝d[Rings[R，1]，i]；

　　                                Min_Indx：＝i；

　　                           end；

　　                   if Min＜65000 then

　　                     begin

　　                       Inc(R_Point[R])；

　　                       Rings[R，R_Point[R]]：＝Min_Indx；

　　                       d[Rings[R，1]，Min_Indx]：＝0；

　　                       (update number of rings per AP)

　　                       Inc(Rings_OnAP[Min_Indx])；

　　                     end；
　　             end；

　　         (perform the second stage of generation：co-locate all free

　　          APs up to max treshold)

　　         (calculate treshold：the maximal distance to a connected AP)

　　         (this parameter should be changed to a better criterion to
 sute the

　　          non-Euclidian spase.the best will be if the ap in a given
 ring

　　          will be at the most equal distance from one to the other.

　　          There is a possibility that a cetrain ap will not be able to

　　          connect，thus it should generate a seperate ring，and skipp
 the

　　          first stage of the connected ap acquisition)

　　         Treshold：＝0；

　　         for j：＝2 to R_Point[R]do

　　             if distance[Rings[R，l]，Rings[R，j]]＞Treshold then

　　                Treshold：＝distance[Rings[R，1]，Rings[R，j]]；

　　         j：＝1；

　　         While(j＜＝MaxAP_onRing-MinAP_onRing-1)or(Termination) do

　　             begin

　　                  Min：＝65000；

　　                  for i：＝1 to NumofAP do

　　                      if(d[Rings[R，1]，i]＜Min)and(Rings_OnAP[i]＝0)
and

　　                        (d[Rings[R，1]，i]＞0)and

　　                        (d[Rings[R，1]，i]＜Treshold)then

　　                        begin

　　                             Min：＝d[Rings[R，1]，i]；

　　                             Min_Indx：＝i；

　　                        end；

　　                if Min＜65000 then

　　                  begin

　　                    Inc(R_Point[R])；
				
				<dp n="d45"/>
　　                      Rings[R，R_Point[R]]：＝Min_Indx；

　　                      d[Rings[R，1]，Min_Indx]：＝0；

　　                      (update number of rings per AP)

　　                      Inc(Rings_OnAP[Min_Indx])；

　　                    end；

　　                  Inc(j)；

　　             end；

　　             if Not(Termination) then

　　               begin

　　                 Free_Pointr：＝0；

　　                 FreeAP；

　　               end；

　　      end；(of While)
 end；
 procedure Generate_Ring_Graph；
 var

　　i，j，k，Count：Word；

　　Graph_Temp：array[1..MaxNumofRings3]of Word；
 begin

　　  for i：＝1 to R do for j：＝1 to R do Graph[i，j]：＝0；

　　  for i：＝1 to MaxNumofRings3 do Graph_Temp[i]：＝0；

　　  Count：＝0；

　　  for k：＝1 to NumOfAP do

　　    (if Rings_OnAP[k]＞1 then)

　　      begin

　　        for i：＝1 to R do

　　          for j：＝1 to R_Point[i] do

　　            if Rings[i，j]＝k then

　　              begin

　　                Inc(Count)；

　　                Graph_Temp[Count]：＝i；

　　              end；

　　        if Count＞＝2 then

　　           for j：＝2 to Count do

　　             begin

　　               Graph[Graph_Temp[1]，Graph_Temp[j]]：＝1；

　　               Graph[Graph_Temp[j]，Graph_Temp[1]]：＝1；

　　             end；

　　        Count：＝0；

　　      end；
end；
procedure Output；
var
   i，j：Word；
begin

　　 AssignFile(Out_File，WriteOut)；

　　 Rewrite(Out_File)；

　　 Writeln(Out_File，′APs to Ring Mapping，and Ring connectivity
list′)；

　　 Writeln(Out_File)；

　　 for i：＝1 to R do

　　     begin
				
				<dp n="d46"/>
　　        write(Out File，′Ring′，i：3，′：′)；

　　        for j：＝1 to R_Point[i]do write(Out_File，Rings[i，j]：4]；

　　        (write out the ring connectivity information)

　　        for j：＝1 to (MaxAP_onRing-R_Point[i])do write(Out_File，′

　　        write(Out_File，′**′)；

　　        for j：＝1 to R do if Graph[i，j]＝1 then Write(Out_File，j：4)；

　　        writeln(Out_File)；

　　     end；

　　 (

　　 Writeln(Out_File)；Writeln(Out_File)；

　　 Writeln(Out_File，′Ring Graph Connectivity Matrix′)；

　　 Writeln(Out_File)；)

　　 (for i：＝1 to R do

　　   begin                                                            

　　     write(Out_File，′Ring′，i：3，′；′)；

　　     for j：＝1 to R do if Graph[i，j]＝1 then Write(Out_File，j：4)； 

　　     writeln(Out_File)；

　　   end；)
　　 CloseFile(Out_File)；
end；
procedure TForml.ButtonlClick(Sender：TObject)；
begin

　　Panell.visible：＝true；

　　Main_Loop；

　　Panell.Visible：＝false；
end；
procedure TForml.Button2Click(Sender：TObject)；
begin

　　Halt；
end；
procedure TForml.Button3Click(Sender：TObject)；
begin

　　   inifile：＝edit1.text；

　　   Button1.Visible：＝true；

　　   Button2.Visible：＝true；

　　   Edit1.Visible：＝false；

　　   Button3.Visible：＝false；
end；
end.

附件C

  program GA；
  uses    crt；
  const
  (      PopMaxSize          ： Maximal number of genes in the system

     GenaMaxSize         ： Maximal number of Allels in every gene

　　     MutationSeed        ： Mutation rate for gene level

　　     Threshold23read     ： Selection Strength

　　     NumOfGenerations    ： Maximal number of generations in a search

　　     AllelDimension      ： Numerical diversity of each
　
　　                            Allel[0，AllelDimension]

　　     MutationSchemaBin   ： Time bin for mutation schema calculations
　　                            in terms of number of generations.

　　     WriteFrequency      ： The frequency of output schedule.

　　     Generation          ： Generation countr.

　　     PopSize             ： A matrix containing the genes and their
 allel

　　                            information.

　　     GeneSize            ： Number of allels.

　　     PopCountr           ： General purpose countr for population
 scanning.

　　     AllelCountr         ： Counter for the Gene level scanning.

　　     CrossoverPointr     ： The location of the gene breaking point for
 the

　　                            purpose of crossover.

　　     NextPopCountr       ： The number of surviving individuals after
 the

　　                            selection stage.

　　     TotFitness          ： Mean population fitness.

　　     PopFitness          ： An array containing the fitnesses of each
 gene

　　                            in the population.

　　    OffspringList        ： An array containing the offsprings
information.

　　    ModelGene            ： A golden gene.

　　    MutationSchema       ： Low path filter over mutation to fitness
crossing

　　                            on an allel basis scale.

　　    GenerationOutFile    ： Global log file.

　　    f                    ： Output file.

　　    PopMaxSize                    ＝  400；

　　  GeneMaxSize                     ＝   30；

　　  MutationSeed                    ＝   10；

　　    AllelMutationSeed             ＝    8；

　　    Threshold23reed               ＝    5；

　　    AllelDimension                ＝   20；

　　    NumOfGenerations              ＝ 2000；

　　    MutationSchemaBin             ＝    1；

　　    WriteFrequency                ＝  100；
type

　　  field      ＝  array[1..PopMaxSize]of single；

　　  GenePop    ＝  array[1..PopMaxSize，1..GeneMaxSize]of integer；

　　    TargetGene ＝  array[1..GeneMaxSize]of word；
var
				
				<dp n="d49"/>
　　    Generation          ：word       ；

　　  PopSize             ：word       ；

　　    GeneSize            ：word       ；

　　  PopCountr           ：word       ；

　　  AllelCountr         ：word       ；

　　  CrossOverPointr     ：word       ；

　　     NextPopCountr      ：word       ；
　　     TotFitness         ：single     ；

　　  PopFitness          ：Field      ；

　　  PopList             ：GenePop    ；

　　  OffspringList         ：GenePop    ；

　　    MocelGene           ：TargetGene ；

　　    MutationSchema      ：TargetGene ；

　　    GenerationOutFile   ：text       ；

　　    f                   ：text      ；
(---------------------------------------------------)
Procedure NullArrays；
begin

　　 for PopCountr：＝1 to PopSize do

　　     begin

　　          PopFitness[PopCountr]：＝0；

　　          for AllelCountr：＝1 to GeneSize do

　　              OffspringList[PopCountr，AllelCountr]：＝0；

　　     end；

　　 For AllelCountr：＝1 to GeneSize do

　　     MutationSchema[AllelCountr]：＝0；
end；
(---------------------------------------------------------)
Procedure GenerateModelGene；
begin

　　 for AllelCountr：＝1 to GeneSize do

　　     ModelGene[AllelCountr]：＝Random(AllelDimension+1)；
end；
(--------------------------------------------------------------------)
Procedure InitiateIO；
begin

　　 Assign(GenerationOutFile，′c：\algrthms\ga\ga.out′)；

　　 Rewrite(GenerationOutFile)；

　　 ClrScr；
end；
(-----------------------------------------------------------------------)
Procedure WriteOut；
begin

　　 writeln(GenerationOutFile)；

　　 writeln(GenerationOutFile，′Generation：′，Generation，

　　         ′； Mean Fitness：′，TotFitness：7∶5)；

　　 writeln(GenerationOutFile)；

　　 writeln(GenerationOutFile)；

　　 for PopCountr：＝1 to Popsize do

　　     begin

　　          for AllelCountr：＝1 to GeneSize do

　　              write(GenerationOutFile，PopList[Popcountr，
				
				<dp n="d50"/>
AllelCountr]：3)；

               writeln(GenerationOutFile，′
′，PopFitness[PopCountr]：7∶5)；

                writeln(GenerationOutFile)；

          end；

      writeln(GenerationOutFile)；

      writeln(GenerationOutFile)；
end；
(-------------------------------------------------------------)
Procedure GeneratePop；
begin

      for PopCountr：＝1 to PopSize do

　　      for AllelCountr：＝1 to GeneSize do

　　            PopList[PopCountr，AllelCountr]：＝Random(AllelDimension
+1)；
end；
(---------------------------------------------------------------------------------------)
Function MutationRate：word；
begin

　　     MutationRate：＝Round(100*Sqrt(1-PopFitness[PopCountr]))；
end；
(-----------------------------------------------------------------------------------)
Procedure AllocatePopFitness；
var

　　  Temp_Fitness：array[1..PopMaxSize] of single；
begin

　　 for PopCountr：＝1 to PopSize do Temp_Fitness[PopCountr]：＝0；

　　     for PopCountr：＝1 to PopSize do

　　         for AllelCountr：＝1 to GeneSize do

　　             Temp_Fitness[PopCountr]：＝Temp_Fitness[PopCountr]+

　　                ABS(PopList[PopCountr，AllelCountr]-
ModelGene[AllelCountr])；

　　 for PopCountr：＝1 to PopSize do

　　     if Temp_Fitness[PopCountr]＝0 then Temp_Fitness[PopCountr]；＝
1

　　        else Temp_fitness[PopCountr]：＝0.9/Temp_Fitness[PopCountr]；

　　   for PopCountr：＝i to PopSize do

　　         PopFitness[PopCountr]：＝Temp_Fitness[PooCountr]；
end；
(---------------------------------------------------------------------------------------)
Function OneGeneFitness：Boolean；
var

　　 TempOneGeneFitness：single；
begin
　　 TempOneGeneFitness：＝0；

　　 for AllelCountr：＝1 to GeneSize do

　　     TempOneGeneFitness：＝TempOneGeneFitness+

　　        ABS(PopList[PopCountr，AllelCountr]-
				
				<dp n="d51"/>
ModelGene[AllelCountr])；

　　 if PopFitness[PopCountr]＞＝TempOneGeneFitness then OneGeneFitness
：＝False

　　    else OneGeneFitness：＝True；
end；
(-------------------------------------------------------------------------------)
Function AllelMutationRate：word；
begin

　　 if MutationSchema[AllelCountr]＜＝0 then AllelMutationRate：＝
AllelMutationSeed

　　    else AllelMutationRate：＝

　　         AllelMutationSeed*(1+
Trunc(Sqrt(MutationSchema[AllelCountr])))；
end；
(----------------------------------------------)
Procedure PcpMutation；
var

　　  AllelMutationDirection：integer；
begin

　　  for PopCountr：＝1 to PopSize do

　　        if Random(100)＜MutationRate then

　　             for AllelCountr：＝1 to GeneSize do

　　               if Random(100)＜AllelMutationRate then

　　                  Begin  

　　                     PopList[PopCountr，AllelCountr]：＝
Random(AllelDimension+1)；

　　                           if OneGeneFitness then
Inc(MutationSchema[AllelCountr])

　　                              else Dec(MutationSchema[AllelCountr])；

　　                end；
end；
(---------------------------------------------------------------------------------------------------)
Procedure CrossOver；
var

　　    PopChildren         ：word；

　　    CrossOverLocation ：word；

　　      GeneOne，GeneTwo  ：word；

　　      POpLack           ：word；
begin

　　      If NextPopCountr * 3  ＞ 2 * PopSize then

　　         NextPopCountr：＝(2*PopSize)div 3；

　　      PopChildren：＝NextPopCountr+1；

　　    PopCountr   ：＝1；

　　    While PopCountr＜＝(NextPopCountr-1)do

　　          begin

　　                CrossOverLocation：＝Random(GeneSize-1)+1；

　　                for AllelCountr：＝1 to CrossOverLocation do

　　                    PopList[PopChildren，AllelCountt]：＝

　　                          PopList[PopCountr，AllelCountr]；

　　                      Inc(PopCountr)；

　　                For AllelCountr：＝(CrossOverLocation+1)to GeneSize
do

　　                    PopList[PopChildren，AllelCountr]：＝

　　                          PopList[PopCountr，AllelCountr]；
				
				<dp n="d52"/>
　　                           Inc(PopCountr)；

　　                                 Inc(PopChildren)；

　　                 end；

　　                for PopCountr：＝PopChildren to PopSize do

　　                    begin

　　                         GeneOne：＝Random(NextPopCountr)+1；

　　                         GeneTwo：＝GeneOne；

　　                         While GeneTwo＝GeneOne do

　　                             GeneTwo：＝Random(NextPopCountr)+1；

　　                         CrossOverLocation：＝Random(GeneSize-1)+1；

　　                       for AllelCountr：＝1 to CrossOverLocation do

　　                           PopList[PopCountr，AllelCountr]：＝

　　                                 PopList[GeneOne，AllelCountr]；

　　                       For AllelCountr：＝(CrossOverLocation+1)to GeneSize
do

　　                           OffspringList[PopCountr，AllelCountr]：＝

　　                                     PopList[GeneTwo，AllelCountr]；

　　               end；
end；
(---------------------------------------------------------------------------------------)
Procedure Selection；
var

　　  AddGene               ： word；

　　  MaxGeneFitness        ： single；

　　    MinGeneFitness      ： single；

　　  ReproducingSpicies    ： array[1..PopMaxSize]of word；

　　    TempPop             ： array[1..PopMaxSize，1..GeneMaxSize]of
word；
begin

　　    TotFitness      ：＝   0；

　　  NextPopCountr  ：＝   0；

　　  MaxGeneFitness ：＝   PopFitness[1]；

　　  MinGeneFitness ：＝   PopFitness[1]；

　　  for PopCountr  ：＝ 1to Popsize do

　　      begin

　　          TotFitness：＝Tot Fitness+PopFitness[PopCountr]；

　　          if PopFitness[PopCountr]＞MaxGeneFitness then

　　           MaxGeneFitness：＝PopFitness[PopCountr]

　　               else if PopFitness[PopCountr]＜MinGeneFitness then

　　                     MinGeneFitness：＝PopFitness[PopCountr]；

　　       end；

　　   TotFitness：＝TotFitness/PopSize；

　　   writeln(f，Generation，′，′，MaxGeneFitness，′，′，MinGeneFitness，′，′，T
otFitness)；

　　    if (MaxGeneFitness＝1)and(TotFitness＞＝0.9)then

　　    begin

　　         WriteOut；

　　         Close(GenerationOutFile)；

　　         Close(f)；

　　         Halt；
				
				<dp n="d53"/>
　　         end；

　　       for PopCountr：＝1 to PopSize do

　　           if (MaxGeneFitness-PopFitness[PopCountr])＜＝

　　              (MaxGeneFitness-MinGeneFitness)/Threshold2Breed then

　　                 begin

　　                      Inc(NextPopCountr)；

　　                  ReproducingSpicies[NextPopCountr]：＝PopCountr；

　　                 end；

　　         if NextPopCountr＝0 then

　　            begin     

　　                 writeln(′Population died out. Search not completed′)；

　　                 Close(f)；

　　                 Close(GenerationOutFile)；

　　                 HALT；

　　            end；

　　         for PopCountr：＝1 to NextPopCountr do

　　             for AllelCountr：＝1 to GeneSize do

　　                 TempPop[PopCountr，AllelCountr]：＝

　　                    PopList[ReproducingSpicies[PopCountr]，AllelCountr]；

　　         for PopCountr：＝1 to NextPopCountr do

　　             for AllelCountr：＝1 to geneSize do

　　                 PopList[PopCountr，AllelCountr]：＝

　                    TempPop[PopCountr，AllelCountr]；

　　         if  NextPopCountr＜＞Trunc(NextPopCountr/2)*2 then

　　             begin

　　                  Inc(NextPopCountr)；
　　                  AddGene：＝Random(NextPopCountr-1)+1；

　　                  for AllelCountr：＝1 to GeneSize do

　　                      PopList[NextPopCountr，AllelCountr]：＝

　　                         PopList[AddGene，AllelCountr]；

　　            end；
end；
(--------------------------------------------------------------------------------------)
(                          MAIN       ROUTINE    )
begin

　　 Randomize；

　　 Assign(f，′c：\algrthms\ga\fitness.out′)；

　　 Rewrite(f)；

　　 PopSize  ：＝  300；

　　 GeneSize ：＝   10；

　　 InitiateIO；

　　 GenerateModelGene；

　　    write(GenerationOutFile，′Model Gene：′)；
				
				<dp n="d54"/>
　　    for AllelCountr：＝1 to GeneSize do

　　        write(GenerationOutFile，ModelGene[AllelCountr]：3)；

　　        writeln(GenerationOutFile)；

　　        writeln(GenerationOutFile)；

　　 Generation：＝1；

　　 GeneratePop；

　　 While Generation＜NumOfGenerations do
　　       begin

　　            NullArrays；

　　            AllocatePopFitness；

　　            if Generation＝

　　               Trunc(Generation/WriteFrequency)*WriteFrequency

　　                 then WriteOut；

　　            Selection；

　　            CrossOver；

　　            PopMutation；

　　            writeln(′Generation：′，Generation)；

 　　           if Generation＝

　　               Trunc(Generation/MutationSchemaBin)*
MutationSchemaBin then

　　                 for AllelCountr：＝1 to GeneSize do

　　                     MutationSchema[AllelCountr]：＝0；

　　            inc(generation)；

　　       end；

　　 WriteOut；

　　 Close(GenerationOutFile)；

　　 Close(f)；
end.

附件D

　　                              ring.ini
Apendix  A  and  B  Initialization  file
----------------------------------------

　　  20                   Number of APs

　　  90                   Lowest sensitivity for Rx in dBm

　　   2                   Mininmal number of AP on ring

　　   4                   Maximal Number of APs on the Ring

　　   2                   Upper bound of rings on AP

　　   2                   1-random position，2-grid position
d：\sim\mac-sim\5GHz\Ring_dBm.TBL
d：\sim\mac-sim\5GHz\Ring.out
i：\users\common\zvika\aviw\Ring_dBm.TBL
i：\users\common\zvika\aviw\Ring.out

附件E

　　　　                         Ring.out
Transmitter to Subset Mapping       Subset connectivity list
----------------------------      ----------------------
Ring  1：  8    3    7    9         **    2  3  4
Ring  2：  2    3    7              **    1  3
Ring  3：  1    2    8    6         **    1    2    4    5
Ring  4：  10   9    6    5         **    1    3    5    6
Ring  5：  12   1   10   11         **    3    4    6    7
Ring  6：  14   12   5   13   20    **    4    5    7    8
Ring  7：  16   11  13   17         **    5    6    8
Ring  8：  18   17  14   19   21    **    6    7

附件F

   runction cbwl＝CBWL()
   ％This function computes and manages a channel reservoirs of six
   ％cliques.The cliques are defined by the example in Fiqure 7.
   ％
   ％Function′s input：
   ％1)Mapping vector between transmitters and Subsets
   ％2)Subset graph，defined as a connectivity matrix
   ％3)A Carrier-sense matrix that defines levels of
   ％  interference between the transmitters
   ％4)transmitter load vector-a matrix that defines the
   ％  communication intencity of each transmitter in terms
   ％  of frames per second
   ％
   ％Function′s output：
   ％1)Complete time/event map of the system，as presented in the
  ％   following example：
  ％
  ％   Time   Tx-1  Tx-2   ...  Tx-21
  ％     #      i     i           i
  ％     #      i     6           1
  ％     ..     ..    ..          ..
  ％     ..     ..    s           s
  ％2)Each local reservoir behavior，as presented in the
  ％  following example：
  ％
  ％            Time -##
  ％   Res-1  Res-2  ...  Res-6
  ％    A       A         A
  ％    B                 B
  ％    C       C
  ％    D       D
  ％    ..      ..        ..
subnets＝zeros(6，21)；
％Filling the subnet matrix with he relevant data
n(1，1)＝2；
n(1，2)＝2；
n(1，3)＝2；n(2，3)＝1；
n(1，4)＝1；n(2，4)＝3；
n(1，5)＝3；
n(1，6)＝3；n(2，6)＝5；
n(1，7)＝5；
n(1，8)＝5；
n(1，9)＝5；
n(1，10)＝3；n(2，10)＝5；
n(1，11)＝1；n(2，11)＝3；
n(1，12)＝1；n(2，11)＝4；
n(1，13)＝4；
n(1，14)＝4；n(2，14)＝6；
n(1，15)＝6；
n(1，16)＝6；
n(1，17)＝6；
n(1，18)＝4；n(2，18)＝6；
n(1，19)＝1；n(2，19)＝4；
n(1，20)＝1；n(2，20)＝2；
n(1，21)＝2；
％Neiqbor Clique connectivity graph
clique＝zeros(6)；
z＝1：6；
clique(z，z)＝1；
clique(1，2)＝1；clique(1，3)＝1；clique(1，4)＝1；
clique(2，1)＝1；
clique(3，1)＝1；clique(3，5)＝1；
clique(4，1)＝1；clique(4，6)＝1；
clique(5，3)＝1；
clique(6，4)＝1；
				
				<dp n="d61"/>
％Inicial reservoir of all cliques
num_cliques＝；％For the specific exampla
％It is important to assign less channels than transmitters，
％i.e，otherwise no reservoir nulling will occur
num_channels＝10；
reservoir＝ones(num_cliques)；
％Assign initial reservoirs
reservoir(：)＝num_channels；
％Channel request vector
channel_need＝teros(1，21)；％For the specific example case
％Channel request intencity expressed threshold
channel_Need_threshold＝.S；
％Associate output files
f1＝″C：\data\simout\rsservoirs.out″；
f1＝″C：\data\simout\channel_need.out″
％Initial time anf the total simulation duration in event units
time＝1；
fin＝5000；
％Main loop.Perform execution for time＝0 to time＝fin
％At each point calculate the reservoirs of every clique
％and print it out
for time＝1：fin
   ％Initiate the reservoir vectors-it is assumed that each borrowing
   ％duration is equal to one time step
   reservcir(：)＝num_channels；
   ％first，generate the channel request vector
   channel_need(：)＝in(random)，channel_Need_threshold)；
   ％For all nodes(transmitters in the network，chack whether they
   ％need a channel and then borrow one-iff available and update all
   ％reservcirs accordingly
　  for node＝1∶21

　　  if channel need(node)＞0

　　     ％Check to what cliques this node(transmitter) is associated

　　     ％and if possible borrow a channel

　　     if reservoir(n(1，node))＞0

　　        reservoir(n(1，node)＝reservoir(n(1，node)-1

　　        else if n(2，node)＞0 &amp;&amp; reservoir(n(1，node))＞0

　　                reservoir(n(1，node)＝reservoir(n(1，node)-1；

　　              end；

　　     end；％reservoir not emply

　　     printf(f1，reservoir)；

　　     printf(f2，channel_need)；

　　  end；％channel_need
   end；％for loop
end；％main for loop
close(f1)；
close(f2)。
return；

Claims

1.一种通过第二组发射机利用第一组信道的方法，该方法包括：

规定第三组发射机子集使得第二组发射机中至少一个包括在每个发射机子集中；

分配第一组信道中至少一个信道到每个发射机子集，在该发射机子集的发射机中共享，使得小于所有第一组信道被分配到第三组发射机子集，因此规定还没有分配给任何发射机子集的信道的储存器；以及

共享所有第二组发射机之间信道储存器中的信道。

2.如权利要求1所述的方法，其中如果没有包括第一和第二发射机的邻近小集团，第一发射机有资格使用储存器中的信道，即使该信道被第二发射机使用，其中单独的发射机子集的邻近小集团包括与单独的发射机子集共享至少一个公共发射机的所有发射机子集。

3.一种在第一组信道服务于包括单独的发射机的第二组发射机的情况下单独的发射机发射的方法，该方法包括：

如果该发射机属于第一组信道中第一信道服务的发射机子集，并且如果第一信道是可利用的，则经过第一信道发射；

否则，如果信道的储存器包括可利用的第二信道，则经过第二信道发射，其中储存器包括不服务于任何发射机子集的第一组信道中所有的信道。

4.如权利要求1所述的方法，其中所述信道通过它们的传输频率分开。

5.如权利要求1所述的方法，其中所述信道通过它们的传输编码分开。

6.如权利要求5所述的方法，其中所述信道包括CDMA(码分多址)信道。

7.如权利要求1所述的方法，其中所述信道中至少一些包括无线信道。

8.如权利要求1所述的方法，其中子集规定的步骤还包括对于每个子集从子集的发射机中选择子集主机，信道分配请求经过控制信道寻址到该子集主机。

9.如权利要求8所述的方法，其中子集主机被选择以便最大地利用所述控制信道用于子集中发射机与子集主机属于的其他子集中的发射机通讯。

10.如权利要求8所述的方法，其中属于最大数量其他子集的子集中的发射机被选择作为子集主机。

11.如权利要求1所述的方法还包括通过将丢失的发射机与丢失发射机属于的子集断开来放弃丢失的发射机，包括仅通知每个子集的主机该丢失的发射机已经断开。

12.一种通过第二组发射机利用第一组信道的系统，该系统包括：

信道分配器，操作时分配第一组信道中至少一个信道到第三组发射机子集的每一个，每个包括第二组发射机中至少一个，该信道在该发射机子集的发射机中共享，使得小于所有第一组信道被分配到第三组发射机子集，因此规定还没有分配给任何发射机子集的信道的储存器；以及

信道共享器，操作时共享所有第二组发射机中信道储存器中的信道。