JP2002532984A - Channel assignment apparatus and method - Google Patents

Abstract

  (57) [Summary] A method of utilizing a first plurality of channels by a second plurality of transmitters, wherein at least one of the second plurality of transmitters is included in a respective receiver subset. Defining a transmitter subset and assigning at least one channel to each transmitter subset among the first plurality of channels, sharing among the transmitters in the transmitter subset, wherein fewer than all of the plurality of channels are the channels. 3 of the plurality of transmitter subsets, thereby defining a reservoir of a channel not assigned to any of the transmitter subsets, and a channel in a reservoir of the channel between all of said second plurality of transmitters. Sharing method comprising Le.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

TECHNICAL FIELD OF THE INVENTION

 The present invention relates to an apparatus and a method for allocating channels.

[0002]

2. Description of the Related Art

 The prior art on channel assignment is described in the following publications:

[0003] Scott Jordan's "Resource Allocation in Wireless Networks" (JHSH
Jan. 10, 1995) Dunk Anton et al., "Assignment of Static and Dynamic Channels Using Simulated Annealing," Neural Networks in Communication, Chapter 10, Ed. Ben Jujas and Nirwan Anisari, Kluwer Academic. H. Jiang and S. S. Rapperport, "Preferred Channel Borrowing Without Locking: Strategies for Channel Distribution for Cellular Communications," (IEEE / ACM Transactions on Networking, Vol. 2,19
April 1996

[0004] The disclosures of all publications mentioned herein, as well as those cited herein, are incorporated by reference.

[0005]

[Means for Solving the Problems]

It is an object of the present invention to provide an improved channel allocation device and method.

According to a preferred aspect of the present invention, there is provided a method of utilizing a first plurality of channels by a second plurality of transmitters, wherein at least one of the second plurality of transmitters has a respective receiver. Defining a third plurality of transmitter subsets to be included in the subset;
Assigning at least one channel to each transmitter subset because of the first plurality of channels, sharing among the transmitters in the transmitter subset, wherein fewer than all of the plurality of channels are transmitted by the third plurality of transmitter subsets; , Thereby defining a reservoir of channels not assigned to any transmitter subset, and sharing a channel in a reservoir of channels among all of said second plurality of transmitters. .

[0007]

BEST MODE FOR CARRYING OUT THE INVENTION

FIG. 1 is a simplified functional block diagram of a channel allocation system constructed and operative in accordance with a preferred embodiment of the present invention, wherein the channels are distributed to a first plurality of spatially distributed transmitters. Allocate. Typically, these transmitters serve as access points for a larger number of workstations.

The term “channel” is intended to include, but is not limited to, any means of access, mediator, path or line through which signals, data or information is sent, including, but not limited to, TV cables and lengths. Includes wired channels, such as distance land value cables, wireless channels, such as radio channels, fiber optics and satellites, and any combination thereof.

The term “connectivity” is defined as the mutual sensitivity between two or more transmitters. The system of FIG. 1 includes a connectivity matrix generator 10 that operates to generate a matrix. Each component of the matrix represents a level of connectivity between each transmitter in the first plurality of transmitter groups.

The transmitter subset generator 20 operates to generate a second plurality of subsets, each subset including some of the transmitters. Normal,
The transmitters in each subset share at least one channel, and no one outside the subset is allowed to use this channel. However, this does not apply to the case where a transmitter outside the subset can reuse a channel that does not substantially interfere with a transmitter within the subset.

[0011] The transmitters in the subset may be, for example, ordinary transmitters using a suitable wired or wireless means to transmit the master transmitter of the subset.
nsmitter) can communicate with each other, such as when requesting a channel. Usually, one of the channels of the subset is used for communication within the subset.

The transmitters in each subset utilize one or more channels shared by them. The one or more channels may be used alone or partially (for example, by a time division scheme) to perform the following functions (a) and (b).
) And (c) for some or all. Functions (a), (
b) is a control function, and function (c) is a normally used function.

A. As described in more detail below, it allows certain transmitters in the subset to request channels from a main reservoir for the transmitter. For example, a transmitter may use channel B to request a channel for itself, and receive channel C from the main reservoir in response.

The request to allocate a channel from the transmitter to the main reservoir may be signaled using a special channel that is not used for other purposes, ie, is not one of the channels of the main reservoir. This special channel may be on a different medium than the main reservoir channel.

B. Allow workstations served by the subset to request access to the transmitter.

[Brief description of the drawings]

FIG. 1 is a schematic functional block diagram illustrating a channel assignment system according to an embodiment of the present invention. The system assigns channels to a plurality of oscillators distributed in space.

FIG. 2 is a diagram showing a plurality of transmitters distributed in a geometric space and between obstacles also distributed in the space.

FIG. 3 shows a plurality of similar transmitters distributed in a non-Euclidean space.

FIG. 4 shows a subset of several transmitters.

FIG. 5 is a diagram showing a relationship between subsets I to VI in FIG. 3;

FIG. 6 is a diagram showing a result of a subset graph coloring step.

FIG. 7A to 7F show adjacent clicks from subsets I to VI.

FIG. 8 is a schematic functional block diagram showing a channel assignment system according to an embodiment of the present invention, which assigns channels to a plurality of oscillators distributed in space.

FIG. 9 is a diagram showing a plurality of transmitters distributed in geometric space and between obstacles also distributed in space.

FIG. 10 illustrates a plurality of similar transmitters distributed in non-Euclidean space.

FIG. 11 shows a subset of some transmitters.

12 is a diagram showing a relationship between subsets I to VI in FIG. 3;

FIG. 13 is a diagram showing a result of a coloring process of a subset graph.

FIG. 14A to 14F show adjacent clicks from subsets I to VI.

FIG. 15 is a schematic functional block diagram showing a channel assignment system according to an embodiment of the present invention, which assigns channels to a plurality of oscillators distributed in space.

FIG. 16 is a diagram showing a plurality of transmitters distributed in a geometric space and between obstacles also distributed in the space.

FIG. 17 illustrates a plurality of similar transmitters distributed in non-Euclidean space.

FIG. 18 shows a subset of some transmitters.

FIG. 19 is a diagram showing a relationship between subsets I to VI in FIG. 3;

FIG. 20 is a diagram illustrating a result of a coloring process of a subset graph.

21A to 21F show adjacent clicks from subsets I to VI. FIG.

FIG. 22 is a schematic functional block diagram showing a channel assignment system according to an embodiment of the present invention, which assigns channels to a plurality of oscillators distributed in space.

FIG. 23 is a diagram showing a plurality of transmitters distributed in a geometric space and between obstacles also distributed in the space.

FIG. 24 shows a similar plurality of transmitters distributed in non-Euclidean space.

FIG. 25 shows a subset of some transmitters.

26 is a diagram showing a relationship between subsets I to VI in FIG. 3;

FIG. 27 is a diagram illustrating a result of a coloring process of a subset graph.

FIG. 28 illustrates adjacent clicks from 7A to 7F to subsets I to VI.

FIG. 29 is a schematic functional block diagram showing a channel assignment system according to an embodiment of the present invention, which assigns channels to a plurality of oscillators distributed in space.

FIG. 30 shows a plurality of transmitters distributed in geometric space and between obstacles also distributed in space.

FIG. 31 illustrates a plurality of similar transmitters distributed in non-Euclidean space.

FIG. 32 shows a subset of some transmitters.

FIG. 33 is a diagram showing a relationship between subsets I to VI in FIG. 3;

[Procedure amendment]

[Submission date] July 5, 2001 (2001.7.5)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] Full text

[Correction method] Change

[Contents of correction]

Patent application title: Channel Assignment Apparatus and Method

[Claims]

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to an apparatus and a method for allocating a channel.

[0002]

2. Description of the Related Art The prior art relating to channel assignment is described in the following publications.

[0003] Scott Jordan's "Resource Allocation in Wireless Networks" (JHSH
Jan. 10, 1995) Dunk Anton et al., "Assignment of Static and Dynamic Channels Using Simulated Annealing," Neural Networks in Communication, Chapter 10, Ed. Ben Jujas and Nirwan Anisari, Kluwer Academic. H. Jiang and S. S. Rapperport, "Preferred Channel Borrowing Without Locking: Strategies for Channel Distribution for Cellular Communications," (IEEE / ACM Transactions on Networking, Vol. 2,19
April 1996

[0004] The disclosures of all publications mentioned herein, as well as those cited herein, are incorporated by reference.

[0005]

SUMMARY OF THE INVENTION The present invention seeks to provide improved apparatus and methods for channel distribution.

In accordance with a preferred embodiment of the present invention, there is provided a method of utilizing a first plurality of channels by a second plurality of transmitters, the method comprising: at least one of the second plurality of transmitters. Defining a third plurality of transmitter subsets to be included in each transmitter subset, and at least one channel among the first plurality of channels shared among the transmitters in the transmitter subsets, for each transmitter subset , So that less than the first plurality of channels are allocated to the third plurality of transmitter subsets, thereby defining a reservoir of channels not allocated to any transmitter subsets; and Transmission Sharing the channel in the channel reservoir among all of the

Further, in accordance with a preferred embodiment of the present invention, the first transmitter defines a channel in the reservoir and an adjacent channel including both the first transmitter and the second transmitter, even if the channel is used by a second transmitter. Entitled to use in the absence of clicks, where adjacent clicks of individual transmitter subsets include all transmitter subsets that share at least one common transmitter with the individual transmitter subset.

According to another preferred embodiment of the present invention, there is provided a method in which individual transmitters transmit in a situation where the first plurality of channels service the second plurality of transmitters including the individual transmitters, The method includes transmitting on a first channel from a first plurality of channels if the transmitter belongs to a subset of transmitters served by the first channel, and if the first channel is available, Otherwise, if the reservoir of the channel includes a second available channel, the reservoir includes all channels from among the first plurality of channels that do not service any subset of the transmitters, and When the reservoir includes the second available channel, the second
Transmitting on a channel is provided.

[0009] Further according to a preferred embodiment of the present invention, the channels are separated by their transmission frequency.

[0010] Still further according to a preferred embodiment of the present invention, the channels are separated by their transmission code.

Further, according to a preferred embodiment of the present invention, the channels include CDMA (Code Division Multiple Access) channels.

Further, according to a preferred embodiment of the present invention, at least some of the channels include wireless channels.

[0013] Still further in accordance with a preferred embodiment of the present invention, the step of defining the subset also includes selecting, from the transmitters in the subset, for each subset, a subset master whose channel distribution request is addressed on the control channel. Including.

Further in accordance with a preferred embodiment of the present invention, the subset master maximizes the use of the control channel for communication between the transmitter in the subset to which the subset master belongs and the transmitter in another subset to which the subset master does not belong. Selected to limit

Further according to a preferred embodiment of the present invention, the transmitters in the subset that belong to the maximum number of other subsets are selected as subset masters.

Further, in accordance with a preferred embodiment of the present invention, the dropout transmitter is released by disconnecting the dropout transmitter from the subset to which the dropout transmitter belongs, and the dropout is disconnected only to each master of the subset. Including that

According to another preferred embodiment of the present invention, there is also provided a system for utilizing a first plurality of channels by a second plurality of transmitters, the system comprising:
Channel allocating means operative to allocate at least one channel from the first plurality of channels to each of a third plurality of transmitter subsets, each including at least one of the second plurality of transmitters; , Channels that are shared among the transmitters in the transmitter subset, such that fewer channels than the first plurality of channels are allocated to the third plurality of transmitter subsets, and thereby to any transmitter subset. Defining the reservoir for the missing channel;
Channel sharing means operable to share a channel in the reservoir of the channel among all of the second plurality of transmitters.

A particular advantage of the method of the present invention is that it is typically NP-complete.

[0019]

BRIEF DESCRIPTION OF THE DRAWINGS The invention will be understood and appreciated from the following detailed description, taken in conjunction with the drawings.

Attached hereto is the following appendix, which helps to understand and appreciate one preferred embodiment of the invention shown and described herein.

Appendices A and B provide a software-implemented alternative to the present invention that takes a transmitter connectivity matrix as input and performs the following functions: transmitter subset generator, subset graph creation, and adjacent click calculation. It is an embodiment.

Appendix C is a software listing of a preferred technique for providing a supervised optimization cycle of the method of Appendix A or Appendix B.

Appendix D is the initialization file of Appendix A or B.

Appendix E is an example of an output file generated by running Appendix A or Appendix B on an ASCII file that stores the data of FIG.

Appendix F is a software listing of a Matlab procedure that performs the functions of devices 60 and 70 of FIG.

FIG. 1 is a simplified functional block diagram of a channel allocation system constructed and operative according to a preferred embodiment of the present invention, wherein a first plurality of transmitters are distributed by space. Allocate a channel to Typically, these transmitters serve as access points for a larger number of workstations.

The term “channel” is intended to include, but is not limited to, any means of access, mediator, path or line through which signals, data or information is sent, including, but not limited to, TV cables and lengths. Includes wired channels, such as distance land value cables, wireless channels, such as radio channels, fiber optics and satellites, and any combination thereof.

The term “connectivity” is defined as the mutual sensitivity between two or more transmitters. The system of FIG. 1 includes a connectivity matrix generator 10 that operates to generate a matrix. Each component of the matrix represents a level of connectivity between each transmitter in the first plurality of transmitter groups.

The transmitter subset generator 20 operates to generate a second plurality of subsets, each subset including some of the transmitters. Normal,
The transmitters in each subset share at least one channel, and no one outside the subset is allowed to use this channel. However, this does not apply to the case where a transmitter outside the subset can reuse a channel that does not substantially interfere with a transmitter within the subset.

The transmitters in the subset may be, for example, ordinary transmitters using a suitable wired or wireless means to transmit the master transmitter of the subset.
nsmitter) can communicate with each other, such as when requesting a channel. Usually, one of the channels of the subset is used for communication within the subset.

The transmitters in each subset utilize one or more channels shared by them. The one or more channels may be used alone or partially (for example, by a time division scheme) to perform the following functions (a) and (b).
) And (c) for some or all. Functions (a), (
b) is a control function, and function (c) is a normally used function. a. As will be explained in more detail below, for a particular transmitter in the subset, to be able to request a channel from the main reservoir for that transmitter. For example, if the transmitter has its own May use channel B to request a channel to receive channel C from the main reservoir in response.

The request to allocate a channel from the transmitter to the main reservoir may be signaled using a special channel that is not used for other purposes, ie, is not one of the channels of the main reservoir. This special channel may be on a different medium than the main reservoir channel.

B. To allow workstations served by the subset to request access to the transmitter.For example, a workstation may notify a "request" to send data or receive Internet service. This can be done using channel B. In response, one of the transmitters (eg, transmitter number 3) may use a special channel to request a channel for itself from the main reservoir. In response, the main reservoir
Assigning channel C to transmitter number 3 allows a workstation to send data to transmitter number 3 via channel C. Further, the request from the transmitter No. 3 to the main reservoir may be transmitted on channel B if an appropriate time sharing scheme is used for channel B.

C. Typically, allowing a particular transmitter to transmit data to provide service to a particular workstation. To govern communication between the workstation and the transmitter, for example, TDMA (time division Multiple access), ring protocols such as token ring, ALO
CSMA (HA, PPMA (interrupt polling multiple access), GRAP (group random access polling), CSMA-CD (CSMA-collision detection), etc.
Any suitable protocol such as carrier sense multiple access) and CDMA (code division multiple access) can be utilized. Any suitable protocol may be utilized to govern communication between transmitters within the subset, and communication between transmitters during the subset, eg, the protocol or any suitable combination thereof.

It is desirable that the process whose configuration is shown in Appendix A be executed before the operating state is activated.

Referring back to FIG. 1, the subset graph creating device 30 creates a graph,
Serving to represent the connectivity of the subset, a subset is considered connected if its respective closest component (member) transmitter is relatively close to one another.

The neighbor click calculator 34 works to calculate the set of all neighbor clicks in the subset graph created by the device 30. A preferred method of operation for device 34, including examples of suitable source code, is described in TAB Professional and Reference Books at the Blue Ridge Conference in Pennsylvania, PA, USA, 1989. )
, Lau HT, "Algorithms on Graphs," pages 59-69.

The graph coloring device 40 serves to assign channels to subsets by coloring the subset graph generated by the device 30;
The color of each subset (node) represents the channel assigned to it. Channel assignment by graph coloring allows each subset to use the minimum number of channels, while not substantially disturbing transmitters in other subsets. A functional block diagram of a preferred embodiment of the graph coloring device 40 is shown in FIG. A preferred embodiment of a graph coloring device, including examples of suitable source code, is described in TAB Professional and Reference B at the Blue Ridge Conference in Pennsylvania, PA, USA, 1989.
ooks), described in Chapter 4 of Lau HT's "Algorithms on Graphs". "
Algorithms on Graphs also provides code for performing subset graph coloring.

The reservoir manager 50 serves to manage the main reservoir including all channels that have not been assigned to a particular subset. The reservoir manager 50 is actually a functional device that is typically performed by an individual transmitter. The individual transmitters that perform the reservoir management function may be pre-defined, but preferably they are selected. In the embodiment shown, the subset master assignment subunit 60 serves to assign or select a transmitter to perform a reservoir management function, typically one master transmitter per subset. Preferably, all of the master transmitters are of equal status and there is no "master-master transmitter". However, in certain applications, the "master-
It may be desirable to assign or pre-determine a "master transmitter". And it may or may not include one of the master transmitters.

Typically, the master transmitter for each subset is selected as the transmitter in the subset that belongs to the largest number of other subsets, ie, the transmitter with the largest adjacent click. If the master transmitter of subset A is also a member (member) of subset B, preferably the transmitters in subset A use the control channel of subset A to send messages to the components of subset B. And subset A
, The master transmitter and the control channel of subset B. This is typically true even if the subset A master is not the subset B master. Preferably,
This exploitation is only allowed if the control channel is free. That is, the case where the requesting channel from the master subset has priority over general communication with other subsets via the master subset.

A particular advantage of selecting a transmitter with the largest neighbor click as the subset master is that, in general, this choice maximizes the utilization of the control channel, so that it is assigned to that subset. This is to maximize the connectivity between subsets by efficiently using the existing non-control channels.

Each manager transmitter servicing a particular subset includes a local reservoir manager 70, a functional device that serves to manage the main reservoir from that subset's perspective. The main reservoir managed by a particular subset manager instead of a particular subset is also referred to herein as the "local reservoir" for that subset, as described in more detail below. The subset manager itself typically requests a channel from time to time,
In this case, it is typically recognized that the subset manager requests a channel from itself, in the same way that other transmitters in the subset request a channel from the manager.

The term “assign” is used to refer to the process of providing a subset with channels that “belong” to the subset, and is not merely “borrowed” by the subset. The term "distribute" is used to refer to the process of "lending" channels from the main reservoir to individual transmitters.

FIG. 2 shows a plurality of transmitters 110 dispersed in Euclidean space, between obstacles 120 such as walls also dispersed in space.

FIG. 3 shows the same transmitters distributed in non-Euclidean space. It is recognized that the metric used to determine the distance between transmitters is typically a non-Euclidean distance. For example, if a non-Euclidean distance is used, such as the Labochevsky distance or the Minkowski distance, the distance between the transmitters is proportional to the signal strength propagation (typically measured in electromagnetic dB) that exists between the transmitters. The Minkowski metric is described in Dover Books, Chapter 2, Moyseyev, R, Spatiotemporal Motion, 1942. The use of Minkowski metrics is described in Dover, Prentice Hall (Dov
er, Prentice Hall) in PBGergmann's introduction to relativity. Suitable Minkowski metrics for the illustrated embodiment of the present invention are described at the following website of the Department of Physics at Virginia State University: http: //astsun.astro.virginia,edu/~ewwon/math/MinkowskiSpace.html

Multiple transmitters are typically substantially free of crosstalk, ie, the distance between each transmitter and itself is infinite, where the Labochevsky distance equals zero.

The transmitter of FIG. 3 may be viewed as a complete graph, where it is recognized that each transmitter is a node and the weight of the edge connecting each two nodes is the distance between them. . The distance may be, for example, the distance of the Labochevsky metric expressed in dB. If two transmitters are positioned such that they cannot receive from each other, the distance between them is typically considered infinite.

The transmitter subset is defined here such that (in the present example) at least one of the 21 transmitters is included in each transmitter subset, and preferably each transmitter is included in at least one subset. Is done.

FIG. 4 shows six subsets, each containing five or six transmitters, but more generally, any number of transmitters, including only one transmitter, are included in a particular subset It is recognized that it may be.

To generate the subset of FIG. 4, the following criteria may be employed. a. There is a predetermined maximum number of transmitters per subset and a predetermined minimum number of transmitters per subset. For example, the rule states that each subset is
As shown in FIG. 4, it may be necessary to include between five transmitters and six transmitters.

B. For each transmitter, there is a maximum number of subsets to which the transmitter is entitled to belong. In the example shown, each transmitter
You are entitled to belong to at most two subsets. However, more generally, some transmitters are entitled to belong to, for example, up to three subsets, while other transmitters are entitled to belong to only one subset, for example.

In order for a transmitter to belong to the n subsets, the transmitter typically has the ability to operate on n different channels simultaneously, eg, typically n separate independent Transmitter device, for example, including n different radio stations. For example, for a wireless transmitter to belong to two subsets, the wireless transmitter typically includes two separate and independent wireless devices. This is one reason for establishing the maximum number of subsets each transmitter is entitled to belong to. However, in some applications it is desirable for the maximum number of subsets for a particular transmitter to be less than the number of channels that that transmitter can transmit.

C. The number of transmitters belonging to only one single subset needs to be minimized.

D. The number of connected subsets needs to be minimized. Two subsets are "connected" if the distance between them is below a predetermined connectivity threshold, such as -91 dB in the illustrated example.

The “distance” between two subsets that have no common components is defined as the minimum distance between any transmitter in the first subset and any transmitter in the second subset. Since the distance between subsets with one common component is zero, subsets with one common component are always considered connected.

E. The number of adjacent clicks to which each subset belongs needs to be minimized. Each subset S has an "adjacent click" that includes all subsets connected to S. Therefore, the number of adjacent clicks to which each subset S belongs is S
Equal to the number of subsets connected to.

Any suitable technique, such as a combinatorial algebra or a neural network or a technique based on a simulated life activity method or a Monte Carlo method, may be derived from said criterion (a) (
It may be used to generate a subset that answers e). Publications describing the simulated life activity method include:

Maugan Ka, San Mateo, CA, USA
ufmann, Basics of LDWhitley (ed.) Genetic Algorithm-2. D. Whitley, "Executable Model of Simplified Genetic Algorithm".

Maugan Ka, San Mateo, CA, USA
ufmann, LDWhitley (eds.) Genetic Algorithm Basics-2M. D. Vos
e "Modeling simple genetic algorithm
s) ".

Next, a graph is generated to represent the relationships between the subsets. Typically,
Each node in the graph represents a subset, and a set of nodes is adjacent (ie, there is an edge between them) if the corresponding subset is connected
. FIG. 5 shows a graph illustrating the relationship between subsets I to VI of FIG.

The available channels are color coded, and the nodes (subsets) in the graph are now colored using the minimum number of colors. In other words, the color of a node identifies a channel belonging to the subset corresponding to that node. If multiple channels are assigned to a particular subset, it is recognized that nodes in that subset have multiple colors (ie, the length of the color vector for that node is greater than one). Any suitable method is available from Pennsylvania, USA (PA, U.S.A.).
SA) at the Blue Ridge conference, TAB Professional and Reference Books, and Lau HT, Chapter 4 of "Algorithms on Graphs", to color channels. It may be used for coloring.

[0062] Channels that are not assigned to any subset are considered to belong to the main reservoir commonly used by all transmitters in all subsets. As will be described in more detail, a channel in the main reservoir may be used by multiple transmitters simultaneously. This situation is referred to herein as "channel reuse."

Channel reuse is typically facilitated by withdrawing a local reservoir from a main reservoir. Certain local reservoirs are typically drawn for each transmitter subset. The channels in the local reservoir at a specified time t are always a subset of the channels included in the main reservoir at time t. If a channel can be used simultaneously by any transmitter in transmitter subset I corresponding to reservoir I and by any of the transmitters in transmitter subset II corresponding to reservoir II, two local reservoirs I and II Is included at the same time. More generally, a channel is simultaneously included in n local reservoirs if it can be used simultaneously by each component of the n transmitter subsets of the n reservoirs without substantial interference.

Typically, two transmitters are operating “without substantial interference” if the value of a predetermined cost function of the transmission quality between the two transmitters is below a threshold. It is regarded. For example, the cost function may comprise the BER (Bit Error Rate) of the channel between the two transmitters.

Initially, each of the local reservoirs contains all of the transmitters in the main reservoir. However, since then, each of the local reservoirs has contracted and expanded in various ways, depending on the relationship of each subset to other subsets, and depending on how much each subset requires a channel. Or to be recognized.

An example of the deployment of six local reservoirs from a main reservoir servicing six subsets of transmitters will now be described based on the examples of FIGS.

FIGS. 7A to 7F show adjacent clicks 200 on each of subsets I to IV.
, 210, 220, 230, 240 and 250. These clicks
It is defined by the adjacent click calculator 34 of FIG. Each click is identified by a dashed line surrounding all of its components.

FIG. 8 is a table summarizing the relationships between the subsets of the examples of FIGS. 2 to 7F and adjacent clicks. “X” indicates connectivity between the two subsets.

FIG. 9 shows that before assignment to a subset of channels, as shown in FIG.
6 is a table showing which channels belong to each local reservoir. As shown, each of the local reservoirs includes all of channels A through G, so of course the main reservoir also includes all of channels A through G.

FIG. 10 shows that channels A and B have subsets I through VI as shown in FIG.
Is a table showing which channels belong to each local reservoir after they are assigned to. As shown, each of the local reservoirs is now channel C
Since the main reservoir includes only channels C to G, it is needless to say that the main reservoir also includes only channels C to G. At this stage, it is recognized that all six local reservoirs are identical.

FIG. 11A is a table showing which channels belong to each local reservoir after transmitter # 1 borrows channel C from its local reservoir, as shown in FIG. 11B. Transmitter (cross hatched)
Channel C is from the local reservoirs of subsets I and II because 1 belongs to subset II as shown in FIG. 11B and subset II is connected to only one other subset (subset I). Only deleted
It remains present in all other local reservoirs, ie, the local reservoirs of subsets III through VI.

FIG. 12A shows that after transmitter # 21 borrows channel D from its local reservoir and before channel C is returned by transmitter # 1 (as shown in FIG. 12B), It is a table | surface which shows whether it belongs to each local reservoir. Since transmitter # 21 also belongs to subset II as shown in FIG. 12B, and because subset II is connected to only one other subset (subset I), channel D also has
, And only remain in the local reservoirs of subsets II and II, and remain in all other local reservoirs, ie, the local reservoirs of subsets III through VI.

FIG. 13A shows that even though channel C has not been returned by transmitter # 1, after transmitter # 15 borrows channel C from its local reservoir (as shown in FIG. 13B), It is a table | surface which shows whether a channel belongs to each local reservoir. This is possible because transmitters # 1 and # 15 belong to unconnected subsets II and VI, respectively. Channel C is assigned to subsets VI and IV because transmitter # 15 belongs to subset VI, as shown in FIG. 13B, and because subsets and VIs are connected to only one other subset (subset IV). It is removed from the local reservoir and remains in the subset III and V local reservoirs.

FIG. 14A is a table showing which channels belong to each local reservoir after transmitter # 17 borrows channel D from its local reservoir (as shown in FIG. 14B). This is possible because even if channel D is used by transmitter # 21, subsets VI and II to which transmitters # 17 and # 21 belong are not connected. Transmitter # 17 belongs to subset VI, as shown in FIG. 14B, and because subset VI is connected to the only other subset (subset IV), channel D is the local reservoir of subsets IV and VI. It is only removed from the bar and remains in the local reservoirs of subsets III and V.

FIG. 15A illustrates transmitters # 1, # 1 (as shown in FIG. 15B).
5, # 17 and # 21 each return the channel they were using, and a table showing which channels belong to each local reservoir after transmitter # 4 borrowed channel C from its local reservoir. is there. Transmitter # 4 belongs to subsets I and III, as shown in FIG. 15B. Since subset I is connected to subsets II, III and IV and subset III is connected to subsets I and V, channel C is removed from the local reservoirs of subsets I to V and only in the local reservoir of subset VI. Will remain present.

FIG. 16A shows that after transmitter # 8 borrows a channel from its local reservoir (as shown in FIG. 16B) (transmitter # 4 has not yet returned that channel), It is a table | surface which shows whether it belongs to a local reservoir.

FIG. 17A shows transmitters # 7 and # 7 (as shown in FIG. 17B).
9 is a table showing which channels belong to each local reservoir after each has borrowed a channel from its respective local reservoir (transmitters # 4 and # 8 have not yet returned that channel).

FIG. 18A depicts a time series of transmitters # 1 to # 10 over a relatively high channel demand strength period over 500 msec. As shown, each transmitter may be in either an "up" state or a "down" state. An "up" state indicates free (that is, no channel requested),
The "down" state represents a request for a channel.

FIG. 18B is a “zoom” (partial enlargement) to a 100 msec time period within the time period of FIG. 18A.

FIG. 19A depicts a time series of transmitters # 1 to # 10 over a relatively low channel demand strength period over 500 msec. As shown, each transmitter is in either an "up" state or a "down" state. "
The "up" state represents empty (ie, not requesting a channel) while the "down" state represents a request for a channel.

FIG. 19B is a “zoom” to a 100 msec time period within the time period of FIG. 19A.

FIG. 20 is a simplified flowchart of a preferred operation method of the connectivity matrix generator 10 of FIG. The input to the method of FIG. 20 is, for example, an indication of the position of the transmitter in space using a conventional Euclidean metric system. Under the typical 8-level FSK (frequency shift keying) modulation system for the ISM band according to FCC (Federal Communications Commission) standard part 15, each transmitter has a specified duration, such as about 2 seconds. Perform carrier measurements on all other transmitters.

Preferably, in addition to the carrier measurement, the correlation detection rate (CDR) of the transmitter is measured, for example, by specifying a FOM (performance figure of merit) for the presence of a clock in the carrier. Device 330 combines the conjugate information coming from devices 310 and 320, that is, information about the same transmitter. Unit 3
The output of 0 (330) is the output of blocks 340, 350 and 3 forming a loop.
60 is sent to the connectivity matrix calculation procedure 334.

The connectivity matrix generator 10 serves to generate a matrix whose elements represent the level of connectivity between each pair of transmitters in the system.
In the example shown including 21 transmitters, the connectivity matrix is:
It is a 21 × 21 symmetric matrix whose diagonal elements are zero.

FIG. 21 is a simplified explanatory flowchart of the preferred method of operation of the transmitter subset generator 20 of FIG. In step 410, the reference (
a) is the criterion (a) described above with respect to FIG.

In step 430, “closest” typically determines the shortest distance between each unassigned transmitter and any assigned transmitters among the various assigned transmitters. Calculated from
Determined by selecting the unassigned transmitter with the smallest “shortest distance” as “closest” as “closest”. The distance criterion used in this step is not the Euclidean distance, but rather the distance criterion of the connectivity matrix, for example rather the Minkowski distance.

In step 440, the criteria (a) to (e) correspond to the criteria (a) described above with reference to FIG.
) To (e).

Optionally, step 460 is performed. In this step, the transmitter allocation achieved in steps 400 to 450 is determined by the Vose
Optimized using conventional methods, such as evolutionary genetic algorithm methods, such as those described in publications.

The output of the method of FIG. 21 is typically a transmitter subset vector as found in Appendix E.

FIG. 22 is a simplified flowchart diagram of a preferred operation method of the subset graph creating device 30 of FIG. The method of FIG. 22 receives the transmitter subset vectors generated by the method of FIG. 21 and processes each subset as a node in the graph. The method connects each set of subsets with one common transmitter and adds edges to generate a transmitter subset graph such as the graph of FIG.

FIG. 23 is a simplified flowchart diagram of a preferred method of operating the subset graph coloring device 40 of FIG. The input to the method of FIG.
9 is a subset graph generated by the method of FIG. In step 610, an "available" color is a color that has not yet been assigned to any node. The output of FIG. 23 is a colored subset graph. An example of a colored subset graph is shown in FIG.

FIG. 25 is a simplified state machine diagram of the local reservoir management device 70 of FIG. Each transmitter has the following two states. That is, empty and "needs a channel".

In step 830, the term “subset master” refers to the master of the subset to which the transmitter belongs, or, if the transmitter belongs to more than one subset, to any of the masters of any subset to which the transmitter belongs. .

FIG. 26 is a preferred method for performing the least cost channel calculation step 870 in FIG.

FIGS. 27A-27B illustrate the terms “central channel,” “adjacent channel,” and “
Forms an exemplary definition of "alternate channel". FIGS. 27A and 27B are spectral intensity diagrams of the first transmitter and the second transmitter, respectively. As shown, the spectrum of the first transmitter (FIG. 27A) includes a central lobe 1010, primary side lobes 1020 and 1030, and secondary side lobes 1040 and 1050. Spectrum of the second transmitter (FIG. 27B)
Includes a central lobe 1060, primary side lobes 1070 and 1080, and secondary side lobes 1090 and 1100. The center lobe of each transmitter occupies a channel called the "center channel" of that transmitter. When the specification talks about a "borrowed channel" transmitter, what is being said is that the borrowed channel becomes the central channel of that transmitter.

The two primary sidelobes of each transmitter occupy two respective channels, called the two “adjacent channels” of the transmitter. The two secondary side lobes of each transmitter occupy two respective channels, called the transmitter's two "alternate channels." Thus, if the center channel of one transmitter A is an adjacent channel of another transmitter B, or at least an alternate channel, the interference between transmitters A and B as shown in FIGS. There is.

Borrowing “zero cost” means that, from the perspective of transmitter A relative to transmitter B, B borrows a channel, but none of its adjacent or alternate channels are A's central channel, adjacent channel or Refers to situations that do not overlap with any of the alternate channels.

Non-zero cost borrowing means that from the point of view of transmitter A relative to transmitter B, B borrows a channel, but at least one of its adjacent or alternate channels is the central channel of A, the adjacent channel Or a situation that overlaps with at least one of the alternative channels.

Typically, transmitter A, with respect to all other transmitters T, sees that the interference introduced by the borrowing process exceeds the ratio between the amplitude of either the central channel of T and the adjacent channel of T. You are only allowed to borrow a channel if none is available.

The level of interference caused by transmitter B to transmitter A is such that the ratio between the amplitude of the central channel of A and the amplitude of the central channel of B is equal to the ratio of the amplitude between the central channel of A and the adjacent channel. Sometimes referred to as "adjacent channel interference level".

Similarly, the level of interference caused by transmitter B to transmitter A is such that the ratio between the amplitude of A's central channel and the amplitude of B's central channel is the amplitude of the amplitude between A's central channel and the alternate channel. When it is equal to the ratio, it is called “alternate channel interference level”.

Typically, when two channels are in the same reservoir, there is no interference between them.

FIG. 28 shows that the transmitter 1500 can operate in three different ways, as indicated by the outgoing communication paths A, B and C (dashed lines) and the receiving communication paths D, E and F (solid lines). FIG. 4 is a schematic diagram showing that it is communicating with an element.

As shown, transmitter 1500 includes transmitter 15
00 is communicable with each of the network elements 1510 in the wireless communication envelope around the transmitter 1500 from among the plurality of network elements 1510.
The information is transmitted via channel A to 510 '. This may not necessarily be the case, but the transmitter 1500 is another network element 152, shown as being in the same subset 1530 as the transmitter 1500.
Send the information to channel 0 via channel B. Channel B is a channel that is distributed to transmitter 1500 according to a preferred embodiment of the present invention. Transmitter 1500 further communicates via channel C and to subset 153
The information is transmitted to the transmitters 1560 in the subset 1550 via the subset master 1540 that is common to both 0 and 1550.

The transmitter 1500 receives information via channel D from individual network elements 1510 "from among a plurality of network elements 1510 within a wireless communication envelope around the transmitter 1500. This is not necessarily the case. Alternatively, transmitter 1500 may receive information from another network element 1520 via channel E. Channel B is a channel that is distributed to transmitter 1500 in accordance with a preferred embodiment of the present invention. 1500 is transmitted via channel F and via a subset master 1540 which is common to both subsets 1530 and 1550, to transmitter 1560 or any other transmitter in subset 1550. Information is received from a transmitter in a subset 1550, such as a transmitter.

FIG. 29 is a schematic diagram showing two transmitters 1500 and 1540 in the same subset 1530 communicating simultaneously (with respective transmitters 1540 and 1520). This is because one of the transmitters 1500 has a subset 15
While using the channel distributed to 30, the other transmitter (subset master 1540) is possible because it uses the control channel of the subset 1530.

A preferred process for generating a subset will now be described.

Considering a plurality of transmitters (access points) randomly distributed over confined areas, some of which may be connected to a wired network,
Transmitters will probably interfere with each other and cause interference in the network.

The following description provides maximum network efficiency and capacity while maintaining maximum frequency reuse and robustness, ie, constructing a network that exhibits strong connectivity between transmitters with the highest network data flows. , Define a smart network partitioning and access engine that contributes to implementing a segmented topology.

The following approach clusters transmitters into logical subsets whose physical properties are complete graphs (where the transmitter is the graph vertex). Subsequent to this subset partitioning of the transmitters, a subset graph appears. In order to improve performance, the resulting graph is (
Some requirements need to be met (described below).

Assuming a limited and not sufficient number of available frequencies, graph coloring is used to assign the subset graph to the minimum required frequency. This process is called FCA (Fixed Channel Assignment). In practical terms, a local frequency bank is defined (frequency reservoir set), and the subset shall borrow frequencies from this set upon channel demand.

In a multi-subset structure with many unique topological characteristics, mobile stations behave freely with respect to subset coverage, and each mobile station preferably associates with at least one subset from a cluster. Access is performed via a slotted Aloha mechanism of channel request acquisition followed by R-TDMA data ordering. Any transmitted data entities accepted by a particular transmitter in the subset shall be analyzed for its destination analysis. Subsequent decisions (assumed to be wired at this time) shall forward this data entity via its subset to its destination transmitter (the transmitter responsible for the final step of accessing the destination).

The initial condition and the boundary condition include the following. Transmitter set, {AP}; dB is a mapping matrix, and dB _ij is the absolute value of the interference rate between transmitter (I) and transmitter (j). Inter-transmitter interference map; Relative interference distribution specified by absolute value dB Defined thresholds; minimum number of transmitters in subset, α _min ; maximum number of transmitters in subset, α _max ; maximum number of radio interfaces in any transmitter: p; finite set of discrete frequencies, {f} And a fixed number of channels in the subset, K;

Topology Generation The model described below maps a transmitter set to a subset set {R}, while maintaining: 1) Boundary conditions, d, e and f 2) Minimization of transmitters belonging to a single subset, which is

[0115]

(Equation 1)

This can be expressed by minimizing 3) Maximization of non-interfering subsets, thus achieving frequency reuse. Non-interference is defined as follows.

[0117]

(Equation 2)

4) Minimizing the click to which the subset belongs. Here the adjacent click

[0119]

(Equation 3)

Is defined as The rank of the specified subset topology is such that Cost _i

[0121]

(Equation 4)

, Cost _φ = min _φ , and d is the number of different sequences (possible connectivity) and when ω is defined as a weighting factor, min (Cost ₁ ... Co
st _d ).

Although it is assumed that the generation of the subset follows each transmitter birth (potential energy transfer), the death of the transmitter causes the subset to change until some predefined cost function collapses. (This cost function may be a throughput criterion, loss of connectivity, extreme external interference, etc.).

The channel assignment engine running in the system performs the assignment (graph coloring) in a subset topology, and thus includes a subset with fewer graph clicks, so the fixed needed to color the graph frequency(
The number of vertex colors is further reduced.

FIG. 30, and the following discussion, is a step-by-step model for the generation of a subset that satisfies certain initial conditions and meets the requirements listed above.

An AP _k that is initially located at the “centroid” of the transmitter cluster, that is, satisfies the following conditions, is selected.

[0127]

(Equation 5)

The first subset is created by combining the transmitters with the first (transmitter set) assigned using the following method.

[0129]

(Equation 6)

The remaining subset is constructed in two iterative steps, where step 1 selects the transmitter that is the closest transmitter to all ready existing subsets, and step 2 selects the past subset and the latest transmitter. A transmitter that can be a coupling transmitter is coupled between them. And step 3 selects additional free transmitters up to the defined boundaries. Step 1: Select an AP _k located at the “center of gravity” of the transmitter cluster, that is, satisfying the following conditions. j is scanned on the transmitter in the existing subset, and Ap _k
Is selected from free transmitters,

[0131]

(Equation 7)

Step 2: Each AP_jBelongs to the existing subset and the AP_jSatisfies condition f and AP _k Its dB to AP_jFrom AP_kTransmitters smaller than the current
As in the busset

[0133]

(Equation 8)

Select.

The subset is completed from the free transmitter to α _max via steps 1 and 2.

Assuming that there is no HCA spreading, the system is required to solve the channel assignment problem. In a typical channel assignment, the rating is defined as its spectral span (preferably the required minimum), and the blocking probability (blocking is a condition where a channel is required but not available) ).

The channel assignment process can be divided into two different execution schemes (thus,
This is a hybrid process).

Fixed Channel Assignment (FCA) —Assigns a specified number of channels to each subset K, thereby ensuring the connectivity of subset traffic.

Dynamic Channel Assignment (DCA) —acts as a channel reservoir for subset channel requests. As the subset channel request rate is spatiotemporal (a function of time and domain, ie, a subset), different reservoirs will evolve during execution.

FCA color coloring is performed on subsets by assigning K colors to each subset, and by mapping those colors to channel sets. See FIG. 31 for a description of the coloring. After doing so, a new channel set is defined (the set of unassigned channels) and it is named the channel reservoir set.

The coloring of an unspecified graph G is to assign a color to a node of G such that adjacent nodes of G do not have the same color. The number of colors of G is the minimum number of colors required to cover G. When C _n (G _R) is a color number of G _R,

[0142]

(Equation 9)

The coloring is performed by a simple implicit enumeration tree search method. Initially, node 1 is assigned color 1 and the remaining nodes are
Are successively colored so as to be colored with the lowest numbered color that has never been used to color any node adjacent to node i. Let p be the number of colors required by this feasible coloring. Attempts to produce a viable coloring using q <p colors. To achieve this, all nodes colored with p must be recolored. In this way, node u + 1 has color p
Is the smallest exponent assigned, the backtracking step can be performed up to node u. Attempt to color node u with its least feasible alternative color greater than its current color. If there is no such alternative color smaller than p, the node u-
Backtrack to 1 Otherwise, recolor node u and proceed, until all nodes u + 1, u + 2, until node n is either colored or reaches some node v that needs color p. ,,, Are recolored with the minimum feasible color. In the former case, improved coloring using q colors was found. In this case, we backtrack and try to find better coloring using less than q colors. In the latter case, backtrack from node v and proceed as described above. The algorithm ends when the backtrack reaches node I.

DCA As defined above, after the FCA procedure, there are {f} _res } available channels in the reservoir. {F} _res is assigned to each subset of the G _R. Each subset borrows a channel from this set upon initial request. The criteria for lending a channel from a reservoir are defined as follows:

The graph of the nearest neighbor of the specified subset requirement-G _nm is thus defined. V = {R ₁ ... So that Ri∩Rj ≠ 0 | i ≠ j. . . R _r } and E = {Ri,
G _nn = {V, E} when Rj}.

Available channels from {f} _res to a specific subset are:

[0147]

(Equation 10)

Is defined as

The blocking probabilities of the proposed channel borrow-based DCA are now defined, thus presenting a subset topology generation model specification.

[0150]

[Equation 11]

Is the unified set of all channels used in the click or subset R,

[0152]

(Equation 12)

Is the set of colliding channels (discussed below). In other words,

[0154]

(Equation 13)

Represents an adjacent request,

[0156]

[Equation 14]

Is as follows. From these notations

[0158]

(Equation 15)

It is clear that is dependent on traffic in adjacent clicks. The number of channels needed to create {f} _res } is known so that no blocking appears in the system.

After FCA, the R subset is thus the blocking probability

[0161]

(Equation 16)

Requires α _R −1 channel as a peak channel requirement.
from now on

[0163]

[Equation 17]

Recall that is a vector for _R , minimizing α _R or { _{C R} }

[0165]

(Equation 18)

Is minimized.

[0167]

[Equation 19]

Assuming that is a specified constant, the system-level optimum is

[0169]

(Equation 20)

Is given by the minimization of Thus, the blocking probability P _B () _R is

[0171]

(Equation 21)

Is given by Note: The stiffness of the probability collapse is a function of traffic demand and access mechanisms.

As described for access subset generation, transmitters are treated as vertices in a connected graph and are clustered into highly connected subsets. Logically, each subset serves as a network segment, and thus, throughout networking, each subset becomes a wireless cell. Stations (mobile clients) roaming under a certain subset of coverage send and receive information (in a packet-based manner) via a subset “gateway” —a transmitter. It does not matter which transmitter collects that information, and how this information moves into the network.

[0174] Two layered protocols are now described.

That is, an in-subset protocol, also called a wireless MAC protocol, which is responsible for coordination and message delivery in a wireless transaction, and a subset protocol, which is responsible for subset transmitter control, frequency allocation, and inter-subset connectivity.

The following is a general description of the protocol and the accompanying mathematical model.

The described access method accomplishes two main tasks for coordination and for high volume data transactions over the air. Each of the tasks
It is bound by some boundary conditions. That is, the MAC coordination function is dedicated to performing transmission request acquisition and transmitter timing synchronization on the subset. The transaction part of the MAC is called LLC (Link Layer Control), and its purpose is to handle channel requests (from a frequency allocation perspective) and to handle data traffic to and from wireless channels.

Every transmitter in the subset separately performs acquisition of slotted Aloha-based access requests before processing the transmission under the R-TDM regime. To perform the R-TDM section of the protocol, the DCA algorithm is activated by the requesting transmitter (these requests are sent on the subset medium to one of the transmitters, the subset master).

Periodically, the transmitter is authorized to create a contention window on slotted Aloha. Using a dedicated channel, it sends CCLR broadcast transmission packets (contention-start indication) wirelessly. In response, all active stations not associated with the transmitter contend for this process by transmitting a random access based RTS (Request to Send) control frame. The transmitter sends a request buffer (RTS queue)
To store all access requests. Using a designated queue, such as a FIFO, it polls waiting stations for data transmission. If the station is addressed from the on-subset side, reverse polling is used.

Because the slotted Aloha mechanism is very sensitive to the accuracy of the randomized seed,
The transmitter calculates the approximate number of active stations in the subset at the next Aloha contention window by considering the rest of the transmitters in the same subset, and then uses this knowledge to potential competitors via CCLR control frames. Must be included.

The Layer 2 protocol performs three main tasks. That is, it functions as a token control pass for slotted Aloha contention timing for a set of transmitter subsets and as a backbone for channel assignment adjustment. It handles and forwards frequency baseband requests and releases, and data traffic between transmitters within subset adjacent clicks.

This is a token-based protocol, where two types of tokens may be on the same subset. A subnet coordination token whose purpose is to reconcile slotted Aloha contention timing. Upon receipt of such a token, the transmitter will indicate to the subset master (different transmitter or the same transmitter) if a radio transmission is required (RTS queue is not empty or the radio station has data available). Channel request from the transmitter) to the subset. The master preferably responds immediately by either granting or denying the channel (at this point, all neighboring subset members are notified). This token plays a role only in its home subset and is not visible from the neighboring subset in the proximity click. The second type of token operates within proximity clicks. That is, orbit over all adjacent subsets. It acts like a token subset access grant, upon receipt of which a non-empty transmitter can send its data packet (up to some predefined burst length specified in hours).

The analysis of the destination address is performed as follows. Upon receiving a data packet (invariant to its source location), the transmitter compares it to the current set of subsets. That is, it is assumed that every transmitter has complete information about the status of the current address queue of all transmitters in the same subset. If the destination address is located in the subset (no information about the neighboring subset), the transmitter forwards the packet to the home transmitter. Otherwise, the packet has been treated as unresolved and has been forwarded to the neighboring subset so that it turns a full proximity click.

Each transmitter performs IP routing in terms of a subset topology. Every data packet transmitted in the subset topology is sealed to the IP address of its initial wireless transmitter (home transmitter). Destination transmitter subset (the transmitter subset followed by the destination station will be a wired LAN or mobile station)
Opens this seal and maps the source transmitter IP to the MAC packet address.

To avoid packet looping and broadcast storms, a minimal spanning tree self-configuration is implemented.

As system conditions change as a function of time-dependent interference and traffic conditions, the spanning tree graph must be recalculated periodically. The purpose is defined as follows. Consider a graph G (in our case the traffic volume and its typical BER) without an indication of the specified edge length. The goal is to find a spanning tree in G such that the sum of the edge lengths of the tree is minimized. FIG. 32 is not referred to.

The following process achieves this goal with G (subset graph). Initially, set T is empty. Edges are considered for inclusion at T in non-decreasing order of their length (cost). If it does not form a cycle where the edge is already within T,
The edge is included in T. A minimal spanning tree is formed when n-1 edges are included in T. In an implementation, the edges are partially reordered, with the smallest edge being the root of the heap structure (a binary tree in which every node weighs less than its children). The execution time of the process is O (m log m
), Where m is the number of edges in the graph.

The basic cell structure is described as follows and is shown in FIG. Arrows indicate data flow. The queuing behavior of the investigated transmitters is governed by six stochastic processes. A. Add queue via wireless protocol in subset (regardless of destination location). B. Adding a queue via a subset protocol from another transmitter located on the same subset. That is, the destination address is in the interrogated transmitter queue. C. Adding a queue via a subset protocol from another transmitter that is not located on the same subset. That is, the destination address is in the interrogated transmitter queue. D. Dequeue queue via insubset protocol. That is, the destination located after the transmitter being examined, and reflected in the transmitter's queue. E. FIG. Dequeue queue via subset protocol. That is, destinations located behind transmitters located on the same subset. And F. Dequeue queue via subset protocol. That is, a destination located after a transmitter located on the same subset, but the destination transmitter is not a subset component.

A hidden Markov model of queue creation and extinction is assumed. A system level model is created from the assembly of those queues. The creation and extinction of the queue is determined via a probabilistic equation and is calculated on event-step-jump. The derivation of these equations and their mutual coupling is shown below.

[0190]

(Equation 22)

1) Creation of Process A The basic entry probability of a single slotted Aloha slot by a single station is

[0192]

(Equation 23)

Specified by When n _E is the approximate number of stations competing, n _a is the number of stations which actually conflicts. Given any dB threshold difference, the probability variance Γ ^k (n), which specifies the probability of being in partial interference in the same slot, u two stations in the subset have u The probability of successful slot extraction for a station collision is

[0194]

(Equation 24)

It can be evaluated as follows. Thus, the full slot access probability under BER is such that when S is the number of slots in the slotted Aloha window

[0196]

(Equation 25)

When is the number of stations in the transmitter's RTS queue in the subset, the number of active stations is specified by:

[0198]

(Equation 26)

The approximate number of active stations is preferably presented in some algorithmic form. As the estimation error increases, the access latency through the Aloha mechanism increases non-linearly.

Given the probability of a station entering the transmission request queue, it is preferably converted to the actual number of packets.

[0201]

[Equation 27]

The time step for probability estimation is the Aloha token transit period Δt _CCLR ,
Because it is so short, $ _ORTS cannot be immediately converted to a packet queue.
In this way, the actual arrival time is calculated and assigned. Arrival time vector

[0203]

[Equation 28]

Let us define

[0205]

(Equation 29)

Where P _f is the probability of granting the frequency through the DCA process and t _{prs v} is the arrival time of the previous packet (the initial time is the floating time t).

2) Creating B and C Processes P _DR is defined as the probability of a packet occurring within a subset and directed to a station within the same subset. The probability that the destination address is located in the queue of the examined transmitter is specified by t _prev . The assumption in this equation is
That is, the destination addresses of the packets are evenly distributed on the address domain when n ^(Ri) is the total number of stations on the subset (active and free). In this way, the number of packets that the surveyed transmitter can easily handle, when j is the surveyed transmitter,

[0208]

[Equation 30]

Is specified by C process: adding a queue for incoming packets from a remote subset within the same adjacent click.

The probability that the surveyed transmitter will handle such a packet is

[0211]

[Equation 31]

Is given by here,

[0213]

(Equation 32)

Is the number of subsets in adjacent clicks, not including the subset of transmitters surveyed. The assumption made here is that all subsets operate under the same performance criteria.

_Combining the two processes (B and C) provides the number of packets generated within a complete adjacent click that must be handled within the Δt _CCLR time interval by the surveyed transmitter. . Considering the subset token for the transmitter, it is, on the subset,

[0216]

[Equation 33]

Can be transmitted on the subset during the defined time period specified by. Here, Br is the burst length of the minimum packet. Thus, the number of packets handled by the surveyed transmitter is

[0218]

[Equation 34]

Is designated by here,

[0220]

(Equation 35)

Is the number of packets transmitted during the Δt _CCLR period (this will be part of the packet).

3) Creation of E and F processes The probability that the surveyed transmitter will need to transmit on adjacent clicks (not on dedicated radio channels) is

[0223]

[Equation 36]

By this equation,

[0225]

(37)

Are given after simplification. Mapping this probability expression to the number of packets

[0227]

(38)

Is given by In this way, the number of packets sent by a surveyed transmitter to adjacent clicks (not on its own subset)

[0229]

[Equation 39]

Is given by Where N is the number of transmitters across all adjacent clicks,

[0231]

(Equation 40)

Is given by

The description contained herein assumes a ring protocol for communication between transmitters within the subset and a recursive slotted Aloha for communication between transmitters between the subsets.

A particular advantage of the preferred embodiment of the present invention is that the suitability of the device is not limited to communication systems having a certain transmitter distribution in the interference space. Typically, conventional systems are suitable for a particular symmetric transmitter topology. According to a preferred embodiment of the present invention, the device is suitable for virtually any transmitter topology, and in particular for applications where the transmitter is movable and thus the transmitter topology changes over time.

Another particular advantage of the preferred embodiment of the present invention is that transmitters belonging to more than one subset are particularly suitable as relays, ie suitable for relaying information between the subsets to which they belong. is there.

The maximum number of transmitters per subset is typically determined by the subset transmission rate. For example, if the speed of the subset medium is 100 Mbps and each transmitter can transmit at most 10 Mbps, typically no more than 10 transmitters are allowed to belong to each subset to prevent channel waste. It is.

The preferred software embodiments of the present invention are described in Appendices A through C, which include a computer listing of the software implementation of the present invention.

Appendices A and B receive as input a transmitter connectivity matrix, such as the matrix generated by the device 10 of FIG.
, 30, 34, and 40 are alternative software implemented embodiments of the present invention.

Appendix C is a software list of leading preferred techniques for providing optimization cycles for the methods of Appendix A or Appendix B.

A guidance preferred method for providing an optimization cycle has been referenced above.
Described in the Vose publication.

Appendix D is an initialization file for Appendix A or B.

Appendix E is an example of an output file in an ASCII file containing the data of FIG. 24 generated by executing Appendix A or B.

Appendix F is a software listing of the Matlab procedure that performs the functions of the devices 60 and 70 of FIG. The procedure is located at 01760, Mass., USA
, Prime Parkway 24, Cochituate Place, 24
MathWorks I, Prime Park Way, Natick, MA01760, USA
nc.) can be run on Matlab (Matrix Laboratory) for Windows, version 5.0 or later. The procedure receives as input the output of Appendix A or B, such as the example output of Appendix E.

FIG. 24 is a table showing an input format suitable for either Appendix A or Appendix B. The contents of the table of FIG. 24 are examples of inputs that suitably represent the examples in FIGS.

A preferred method for utilizing the computer lists in Appendixes A to C is as follows. a. The device is generated using a PC 486 with Delphi Pascal, and the contents of either Appendix A and B or C are entered in the appropriate heading (Device, Interface, application, const, etc.)
Drive underneath. b. Compile and run the software using Delphi Pascal's "main" program.

It will be appreciated that the software components of the present invention may be implemented in ROM (read only memory) form, if desired. The software components may typically be implemented in hardware, if desired, using conventional techniques.

It will be appreciated that the specific embodiments described in the appendices are intended only to provide a very detailed disclosure of the invention, and not to limit the invention.

[0248] For clarity, it will be appreciated that various features of the invention, which are described in the context of separate embodiments, may be provided in combination in a single embodiment. Conversely, various features of the invention that are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable sub-combination.

It will be appreciated by those skilled in the art that the present invention is not limited to what has been particularly shown and described above. Rather, the scope of the present invention is defined solely by the following claims.

[Brief description of the drawings]

FIG. 1 is a simplified functional block diagram of a channel distribution system created and working in accordance with a preferred embodiment of the present invention that distributes channels to a plurality of transmitters distributed in space.

FIG. 2 is a diagram illustrating a plurality of transmitters dispersed in a Euclidean space between obstacles such as walls, which are also dispersed in the space.

FIG. 3 shows the same transmitters distributed in non-Euclidean space.

FIG. 4 is a diagram of multiple subsets of a transmitter.

FIG. 5 is a graph showing a relationship between subsets I to VI of FIG. 3;

FIG. 6 illustrates the result of the subset graph coloring process.

FIG. 7A is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 7B is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 7C is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 7D is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 7E is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 7F is a diagram showing adjacent clicks for each of subsets I to VI.

FIG. 8 is a table summarizing the relationship between the subsets and the close clicks in the examples of FIGS. 2 to 7F.

FIG. 9 is a table showing which channels belong to each local reservoir before assignment to a subset of channels.

FIG. 10 is a table showing which channels belong to each local reservoir after channels A and B have been assigned to subsets I to VI.

11A is a table showing which channels belong to each local reservoir after the borrowing process shown in FIG. 11B has occurred.

FIG. 11B illustrates a borrowing process whereby transmitter # 1 borrows channel C from its local reservoir.

12A is a table showing which channels belong to each local reservoir after the borrowing process illustrated in FIG. 12B has occurred.

FIG. 12B illustrates a borrowing process whereby transmitter # 21 borrows channel D from its local reservoir.

FIG. 13A is a table showing which channels belong to each local reservoir after the borrowing process illustrated in FIG. 13B has occurred.

FIG. 13B illustrates a borrowing process whereby transmitter # 15 borrows channel C from its local reservoir.

FIG. 14A is a table diagram showing which channels belong to each local reservoir after the borrowing process shown in FIG. 14B has occurred.

FIG. 14B illustrates a borrowing process whereby transmitter # 17 borrows channel D from its local reservoir.

15A is a table showing which channels belong to each local reservoir after the borrowing process shown in FIG. 15B has occurred.

FIG. 15B illustrates a borrowing process whereby transmitters # 1, # 15, # 17 and # 21 each return the channel they were using, and transmitter # 4 borrowed channel C from its local reservoir. is there.

FIG. 16A is a table showing which channels belong to each local reservoir after the borrowing process illustrated in FIG. 16B has occurred.

FIG. 16B illustrates a borrowing process whereby transmitter # 8 has borrowed a channel from its local reservoir (transmitter # 4 has not yet returned the channel).

17A is a table showing which channels belong to each local reservoir after the borrowing process shown in FIG. 17B has occurred.

FIG. 17B illustrates a borrowing process whereby transmitters # 7 and # 9 each borrow a channel from its respective local reservoir.

FIG. 18A is a diagram illustrating a time series of transmitters # 1 to # 10 in a relatively high channel request strength time period of 500 msec. As shown, each transmitter may be in either an "up" state or a "down" state. The "up" state represents empty (i.e., no channels are required) while the "down" state represents a request for a channel.

18B is a diagram that is a “zoom” to a 100 msec time period within the time period of FIG. 18A.

FIG. 19A depicts a time series of transmitters # 1 to # 10 during a relatively low channel demand strength time period of 500 msec. As shown, each transmitter may be in either an "up" state or a "down" state. The "up" state represents empty (i.e., no channels are required) while the "down" state represents a request for a channel.

19B is a diagram that is a “zoom” to a 100 msec time period within the time period of FIG. 19A.

20 is a simplified flowchart diagram of a preferred method of operation for the connectivity matrix generator of FIG.

FIG. 21 is a simplified flowchart of a preferred method of operation for the transmitter subset generator of FIG. 1;

FIG. 22 is a simplified flowchart of a preferred method of operation for the subset graph generator of FIG. 1;

FIG. 23 is a simplified flowchart diagram of a preferred method of operation for the subset graph coloring device of FIG. 1;

FIG. 24 is a table showing an input format suitable for either Appendix A or Appendix B.

FIG. 25 is a simplified flowchart of a preferred method of operating the local reservoir management device of FIG. 1;

FIG. 26 is a simplified flowchart diagram of a preferred method for performing the least cost channel calculation step 870 of FIG. 25.

FIG. 27A shows the spectral intensity diagram terms of the two transmitters, “center channel”,
FIG. 4 forms an exemplary definition of “adjacent channel” and “alternate channel”.

FIG. 27B shows the spectral intensity diagram terms of the two transmitters, “center channel”,
FIG. 4 forms an exemplary definition of “adjacent channel” and “alternate channel”.

FIG. 28 is a schematic diagram of a transmitter shown in communication with other network elements in three different ways.

FIG. 29 is a schematic diagram showing two transmitters within the same subset communicating simultaneously.

FIG. 30 is a diagram of a step-by-step process for a subset generator.

FIG. 31 is a diagram of color coloring performed on a subset graph.

FIG. 32 is a diagram of an indirect subset graph of a specified edge length.

FIG. 33 is a diagram of a data flow in the basic cell structure.

──────────────────────────────────────────────────続 き Continuation of front page (81) Designated country EP (AT, BE, CH, CY, DE, DK, ES, FI, FR, GB, GR, IE, IT, LU, MC, NL, PT, SE ), OA (BF, BJ, CF, CG, CI, CM, GA, GN, GW, ML, MR, NE, SN, TD, TG), AP (GH, GM, KE, LS, MW, SD, SL, SZ, TZ, UG, ZW), EA (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM), AE, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, CA, CH, CN, CR, CU, CZ, DE, DK, DM, EE, ES, FI, GB, GD, GE, GH, GM, HR, HU, ID , IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC, LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW, MX, NO, NZ, PL, PT, RO, RU, SD, SE, SG, SI, SK, SL, TJ, TM, TR, TT, TZ, UA, UG, US, UZ, VN, YU, ZA, ZW

Claims (12)

[Claims] 1. A method of utilizing a first plurality of channels by a second plurality of transmitters, wherein at least one of the second plurality of transmitters is included in a respective receiver subset. Defining a third plurality of transmitter subsets;
Assigning at least one channel to each transmitter subset because of the first plurality of channels, sharing among the transmitters in the transmitter subset, wherein fewer than all of the plurality of channels are transmitted by the third plurality of transmitter subsets; , Thereby defining a reservoir of channels not assigned to any transmitter subset, and sharing a channel in a reservoir of channels among all of said second plurality of transmitters. 2. The first transmitter uses a channel in a reservoir, even if the channel is used by a second transmitter, if there is no adjacent clique that includes the first and second transmitters. 2. The method of claim 1, wherein the clique has rights and the adjacent clique of the individual transmitter subset comprises all transmitter subsets, the transmitter subset sharing at least one common transmitter with the individual transmitter subset. 3. The method according to claim 1, wherein the first plurality of channels includes a second transmitter including an individual transmitter.
The plurality of transmitters, wherein the individual transmitters transmit, wherein the transmitter belongs to a subset of the transmitters functioning by the first channel between the first plurality of channels, and Transmit to the first channel if the first channel is available, otherwise, if the reservoir of the channel includes the second channel available,
The method of transmitting to a second channel, wherein the reservoir comprises all channels among a first plurality of channels that do not function as any subset of the transmitter. 4. The method of claim 1, wherein said channels are separated by their transmitter frequency. 5. The method of claim 1, wherein said channels are separated by their transmitter code. 6. The method of claim 5, wherein said channel comprises CDMA (Code Division Multiple Access). 7. The method of claim 1, wherein at least some of said channels comprise wireless channels. 8. The method of claim 1, wherein the step of defining the subset includes selecting a subset master for each subset among the transmitters in the subset, wherein a channel assignment request is made to the subset master on a control channel. The method of claim 1. 9. The method of claim 8, wherein said subset master is selected to maximize utilization of said control channel for communication of transmitters in a subset with respect to transmitters in other subsets. 10. The method according to claim 8, wherein a transmitter in a subset belonging to the largest number of other subsets is selected as a subset master. 11. The method of claim 11, further comprising the step of disconnecting the dropped transmitter by disconnecting the drop from the subset, wherein the drop belongs to the subset, and the drop indicates to each master of the dropped subset. The method of claim 8. 12. A system for utilizing a first plurality of channels by a second plurality of transmitters, wherein at least one channel from the first plurality of channels to each of a third plurality of transmitter subsets. A channel assigner that operates to assign
A channel sharer operable to share a channel in a channel reservoir among all of the second plurality of transmitters, wherein the third plurality of transmitter subsets comprises the third plurality of second transmitters. Wherein at least one of the transmitter subsets is shared such that less than all of the first plurality of channels are allocated to the third plurality of transmitter subsets, whereby any transmitter subset A system in which reservoirs for channels not assigned to are defined.