Method and system for scheduling packets for transmission from a wireless communication platform

• US 6,888,806 B1
• Filed: 11/22/2000
• Issued: 05/03/2005
• Est. Priority Date: 11/22/2000
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Vandegriff, Aaron C., Doerr, Kenneth J., Miller, Karl E., Mendez, George A.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/721,238
• Time in Patent Office: 1,623 Days
• Field of Search: 370/315, 370/316, 370/338, 370/349, 370/389, 370/391, 370/392
• US Class Current: 370/316
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00

Abstract

A system (38) schedules candidate packets (46) for transmission from a communication platform (22), the communication platform (22) being allocated a plurality of transmission resources (24). The system (38) includes a processing element (40) for receiving the packets (46) and establishing a transmission priority (77) for each of the packets (46) according to a desired quality of service. The packets (46) are stored in a candidate packet buffer (42) as candidate packets (48) in accordance with the established transmission priority (77). The system (38) further includes an interference resolver (44) that executes an interference resolution process (84) to concurrently consider transmission resource availability, spatial separation, and temporal separation variables when scheduling the candidate packets (48) for transmission from the communication platform (22).

Claims

1. A method for scheduling transmission of a packet from a communication platform, said communication platform being allocated a plurality of transmission resources, said method comprising steps of

establishing a transmission priority for said packet;

selecting said packet in response to said transmission priority;

assigning said packet to a candidate transmission resource, said candidate transmission resource being one of said plurality of transmission resources;

comparing a target region for transmission of said packet to keep out regions represented in a cumulative keep out map established for a transmit time frame; and

when said target region differs from said keep out regions, scheduling said packet for transmission during said transmit time frame using said candidate transmission resource.

2. A method as claimed in claim 1 wherein:

said transmission priority establishes an allowable period of transmission time delay for said packet; and

said transmit time frame is one of a number of potential transmit time frames in said allowable period of transmission time delay such that said packet can be scheduled for transmission during any of said potential transmit time frames to prevent violation of said transmission priority.

3. A method as claimed in claim 1 wherein said establishing step comprises:

determining a data type of said packet; and

designating said transmission priority in response to a desired quality of service for said data type.

4. A method as claimed in claim 1 wherein:

said method further comprises storing said packet in a candidate packet buffer following said establishing step and

said selecting operation selects said packet from a plurality of packets stored in said candidate packet buffer.

5. A method as claimed in claim 1 wherein:

said packet is one of a plurality of packets;

said establishing step establishes transmission priorities for each of said packets of said plurality of packets; and

said selecting step includes determining said one packet has a higher one of said transmission priorities than said transmission priorities of remaining ones of said plurality of packets.

6. A method as claimed in claim 1 wherein said packet is one of a plurality of packets, and said method further comprises performing said assigning, comparing, and scheduling operations for each of said transmission resources during a scheduling duration using others of said plurality of packets.

7. A method as claimed in claim 6 wherein said scheduling duration is substantially equivalent to a duration of said transmit time frame.

8. A method as claimed in claim 1 further comprising:

storing said packet in a candidate packet buffer prior to said selecting step

determining, in response to said comparing step, that said target region overlaps one of said keep out regions represented in said cumulative keep out map; and

retaining said packet in said candidate packet buffer in response to said determining step.

9. A method as claimed in claim 8 wherein said method further comprises:

selecting, in response to said retaining step, a next one of said packets from said candidate buffer; and

performing said assigning and comparing operations to determine whether said next one of said packets is to be scheduled for transmission during said transmit time frame using said candidate transmission resource.

10. A method as claimed in claim 8 wherein following said retaining step said method further comprises repeating said selecting, assigning, and comparing step to schedule said packet for transmission during a next transmit time frame.

11. A method as claimed in claim 10 wherein said packet is a first packet and said method further comprises:

determining said candidate packet buffer includes a second packet; and

performing said repeating step for said first packet prior to performing said selecting, assigning, and comparing step for said second packet.

12. A method as claimed in claim 1 wherein:

said plurality of transmission resources are transmission beams exhibiting a first transmission discriminator and a second transmission discriminator;

said method further comprises;

establishing a first keep out map of said cumulative keep out map, said first keep out map being responsive to said first discriminator and having first discriminator keep out regions;

establishing a second keep out map of said cumulative keep out map, said second keep out map being responsive to said second discriminator and having second discriminator keep out regions;

determining a first portion of said target region responsive to said first discriminator; and

determining a second portion of said target region responsive to said second discriminator; and

said comparing operation comprises;

verifying that said first portion differs from said first discriminator keep out regions; and

verifying that said second portion differs from said second discriminator keep out regions.

13. A method as claimed in claim 12 wherein:

said first discriminator is a right polarization beam pattern; and

said second discriminator is a left polarization beam pattern.

14. A method as claimed in claim 12 wherein:

said first discriminator is a first transmission frequency; and

said second discriminator is a second transmission frequency.

15. A method as claimed in claim 1 wherein said comparing step comprises:

extracting a packet destination from said selected packet;

producing a translation vector in response to said packet destination;

obtaining a target region profile from a profile database in response to said packet destination; and

generating said target region in response to said translation vector and said target region profile.

16. A method as claimed in claim 15 wherein said target region profile exhibits one of a plurality of transmission patterns.

17. A method as claimed in claim 15 wherein said producing step comprises:

computing an azimuth and a beam angle relative to said communication platform for said packet destination; and

using said azimuth and said beam angle to obtain coordinates of said translation vector that describe a location of said target region profile for generating said target region relative to said cumulative keep out map.

18. A method as claimed in claim 15 wherein said obtaining operation comprises:

computing an azimuth for said packet destination relative to said communication platform; and

accessing said profile database using said azimuth to obtain said target region profile.

19. A method as claimed in claim 18 wherein:

said obtaining operation further comprises computing a beam angle for said packet destination relative to said communication platform; and

said accessing operation accesses said profile database using both of said azimuth and said beam angle to obtain said target region profile.

20. A method as claimed in claim 1 wherein said scheduling operation includes marking said candidate transmission resource as being occupied during said transmit time frame.

21. A method as claimed in claim 1 further comprising including said target region as an additional one of said keep out regions in said cumulative keep out map in response to said scheduling operation.

22. A system for scheduling packets for transmission from a communication platform, said communication platform being allocated a plurality of transmission resources, and said system comprising:

a processing element for receiving said packets, said processing element establishing a transmission priority for each of said packets according to a desired quality of service for said each packet;

a candidate packet buffer for receiving ones of said packets from said processing element in accordance with said transmission priority;

a profile database having a plurality of target region profiles describing transmission patterns of said transmission resources; and

an interference resolver configured to perform operations including;

establishing a cumulative keep out map of keep out regions for a transmit time frame;

selecting one of said packets from said candidate packet buffer in response to said transmission priority;

assigning said packet to a candidate transmission resource, said candidate transmission resource being one of said plurality of transmission resources;

extracting a packet destination from said one packet;

obtaining a target region profile from said profile database in response to said packet destination;

generating a target region in response to said target region profile;

when said target region differs from said keep out regions of said cumulative keep out map, scheduling said one packet for transmission during said transmit time frame using said candidate transmission resource; and

when said target region overlaps one of said keep out regions of said cumulative keep out map, retaining said packet in said candidate packet buffer.

23. A system as claimed in claim 22 wherein said profile database comprises a plurality of azimuth entries, said target region profiles being associated with particular ones of said azimuth entries.

24. A system as claimed in claim 23 wherein said profile database further comprises a plurality of beam angle entries characterizing a distance from a center of a field of view of said communication platform, said azimuth entries being associated with ones of said elevation angle entries, and one of said target region profiles is obtained in response to a particular pair of said azimuth and beam angle entries.

25. A system as claimed in claim 22 wherein:

said plurality of transmission resources are transmission beams exhibiting a left polarization beam pattern and a right polarization beam pattern;

said profile database includes a left polarization target region profile and a right polarization target region profile; and

said cumulative keep out map includes a left polarization keep out map of left keep out regions and a right polarization keep out map of right keep out regions; and

said interference resolver performs further operations including;

obtaining one of said left polarization target region profiles and one of said right polarization target region profiles in response to said packet destination;

generating a left polarization target region in response to said one of said left polarization target region profile and a right polarization target region in response to said one of said right polarization target region profile; and

verifying that said one left polarization target region profile differs from said left keep out regions and said one right polarization target region profile differs from said right keep out regions.

26. A system as claimed in claim 22 wherein:

each of said target region profiles is described by a target region bitmap;

said keep out regions of said cumulative keep out map are described by keep out region bitmaps; and

said interference resolver concurrently compares bits of said target region bitmap with bits of said keep out region bitmaps to determine whether said target region differs from said keep out regions.

27. A system as claimed in claim 22 wherein in response to said retaining operation, said interference resolver performs a further operation of attempting to schedule said one packet for transmission during a next time frame prior to scheduling others of said packets in said candidate packet buffer for transmission in said next time frame.

28. A system as claimed in claim 22 wherein said interference resolver performs a further operation of including said target region as an additional one of said keep out regions in said cumulative keep out map in response to said scheduling operation.

29. A method for scheduling transmission of packets from a communication platform, said communication platform being allocated a plurality of transmission beams, said method comprising:

establishing a transmission priority for one of said packets in response to a desired quality of service for a data type of said one packet;

selecting said one packet in response to said transmission priority;

establishing a cumulative keep out map of keep out regions for a transmit time frame, said keep out regions being described by keep out region bitmaps;

assigning said packet to a candidate transmission resource, said candidate transmission resource being one of said plurality of transmission resources;

extracting a packet destination from said one packet;

producing a translation vector in response to said packet destination;

obtaining a target region profile from a profile database in response to said packet destination;

generating a target region bitmap in response to said translation vector and said target region profile;

comparing said target region bitmap with said keep out region bitmaps;

when all bits of said target region bitmap differ from all bits of said keep out region bitmaps, scheduling said one packet for transmission during said transmit time frame using said candidate transmission resource; and

including said target region bitmap as an additional one of said keep out region bitmaps in said cumulative keep out map in response to said scheduling operation.

30. A method as claimed in claim 29 further comprising performing said method to schedule ones of said packets for transmission during said transmit time frame using others of said transmission beams.