US6788702B1 — Protocol for neighborhood-established transmissio…

Claim 1

Independent Claim 78 words

A method, comprising exchanging scheduling packets among neighboring nodes of a synchronized wireless network in which time is divided into slots and the slots are grouped into frames, the scheduling packets including descriptions of active scheduled links (ASLs) between a transmitting node and its neighboring nodes, the ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel; and, determining a transmission schedule from information received via said scheduling packets.

Claim 2

Independent Claim 78 words

A method, comprising exchanging scheduling packets among neighboring nodes of a synchronized wireless network in which time is divided into slots and the slots are grouped into frames, the scheduling packets including descriptions of active scheduled links (ASLs) between a transmitting node and its neighboring nodes, the ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel; and, determining a transmission schedule from information received via said scheduling packets.

Claim 3

Dependent Claim 23 words

The method of claim 1 wherein the descriptions further identify nodes within said transmitting node's 2-hop neighborhood by way of a node identifier.

Claim 4

Dependent Claim 22 words

The method of claim 2 wherein the exchange of scheduling packets occurs within a first number of the slots of each frame.

Claim 5

Dependent Claim 14 words

The method of claim 1 wherein transmitting nodes advertise availability using the scheduling packets.

Claim 6

Dependent Claim 15 words

The method of claim 1 wherein the scheduling packets are exchanged in a common channel.

Claim 7

Dependent Claim 20 words

The method of claim 5 wherein the scheduling packets are exchanged over initial portions of frame periods within the network.

Claim 8

Dependent Claim 16 words

The method of claim 1 wherein the descriptions further identify which of the ASLs are established.

Claim 9

Dependent Claim 15 words

The method of claim 7 wherein the descriptions identify which of the ASLs are requested.

Claim 10

Dependent Claim 13 words

The method of claim 8 wherein the descriptions identify idle slot ranges (ISRs).

Claim 11

Dependent Claim 20 words

The method of claim 1 wherein the descriptions further comprise a list of incoming ASLs relative to the transmitting node.

Claim 12

Dependent Claim 20 words

The method of claim 10 wherein the descriptions further comprise a list of outgoing ASLs relative to the transmitting node.

Claim 13

Independent Claim 65 words

A method, comprising scheduling transmission times and/or channels at a node of a computer network according to previously reserved and requested transmission schedules received in packets transmitted by neighboring nodes of the computer network, each of said neighboring nodes describing its 2-hop neighborhood through those of said packets it transmits, said describing including identifiers for nodes residing at a 2-hop periphery within said 2-hop neighborhood.

Claim 14

Independent Claim 65 words

A method, comprising scheduling transmission times and/or channels at a node of a computer network according to previously reserved and requested transmission schedules received in packets transmitted by neighboring nodes of the computer network, each of said neighboring nodes describing its 2-hop neighborhood through those of said packets it transmits, said describing including identifiers for nodes residing at a 2-hop periphery within said 2-hop neighborhood.

Claim 15

Dependent Claim 23 words

The method of claim 12 wherein the packets are transmitted at known periods of time within each frame period within the computer network.

Claim 16

Dependent Claim 25 words

The method of claim 12 wherein transmission times and/or channels are scheduled for periods indicated as being available according to information included in the packets.

Claim 17

Dependent Claim 18 words

The method of claim 12 wherein the previously reserved transmission schedules have precedence over the requested transmission schedules.

Claim 18

Dependent Claim 18 words

The method of claim 12 wherein conflicts between requested transmission schedules are resolved according to a priority scheme.

Claim 19

Dependent Claim 21 words

The method of claim 16 wherein under the priority scheme, requested broadcast transmissions have precedence over requested multicast or unicast transmissions.

Claim 20

Dependent Claim 19 words

The method of claim 17 wherein under the priority scheme, requested multicast transmissions have precedence over requested unicast transmissions.

Claim 21

Dependent Claim 32 words

The method of claim 17 wherein under the priority scheme, conflicts between requested transmissions of equal precedence based on transmission type are resolved according to schedule priority tickets included in the packets.

Claim 22

Dependent Claim 19 words

The method of claim 12 wherein accommodating requested transmission schedules takes precedence over reserving listening time at the node.

Claim 23

Independent Claim 88 words

A method, comprising determining a transmit/receive schedule at a node of a computer network by first monitoring a common communication channel within the computer network to determine from information included within packets transmitted within the common communication channel previously scheduled transmission times and/or channels and advertised listening times of neighboring nodes in the computer network, those of said packets transmitted by a neighboring node describing said neighboring node's 2-hop neighborhood to said node so as to include node identifiers for nodes two hops distant from said neighboring node.

Claim 24

Independent Claim 88 words

A method, comprising determining a transmit/receive schedule at a node of a computer network by first monitoring a common communication channel within the computer network to determine from information included within packets transmitted within the common communication channel previously scheduled transmission times and/or channels and advertised listening times of neighboring nodes in the computer network, those of said packets transmitted by a neighboring node describing said neighboring node's 2-hop neighborhood to said node so as to include node identifiers for nodes two hops distant from said neighboring node.

Claim 25

Dependent Claim 46 words

The method of claim 21 wherein the information included within packets transmitted within the common communication channel comprises a list of the neighboring nodes' scheduled outbound communications, a list of the neighboring nodes' scheduled inbound communications and a list of the neighboring nodes' idle communication periods.

Claim 26

Dependent Claim 46 words

The method of claim 22 wherein the list of the neighboring nodes' outbound communications comprises, for each outbound communication, an indication of the node to which the communication pertains, time parameters for the communication, channel parameters for the communication and a priority indication for the communication.

Claim 27

Dependent Claim 33 words

The method of claim 23 wherein the list of the neighboring nodes' outbound communications further comprises, for each outbound communication, an indication of whether the scheduled outbound communication has been established or requested.

Claim 28

Dependent Claim 46 words

The method of claim 22 wherein the list of the neighboring nodes' inbound communications comprises, for each inbound communication, an indication of the node to which the communication pertains, time parameters for the communication, channel parameters for the communication and a priority indication for the communication.

Claim 29

Dependent Claim 35 words

The method of claim 25 wherein the list of the neighboring nodes' inbound communications further comprises, for each of the inbound communications, an indication of whether the scheduled inbound communication has been established or requested.

Claim 30

Dependent Claim 16 words

The method of claim 21 wherein the node identifiers further comprise media access control (MAC) addresses.

Claim 31

Dependent Claim 14 words

The method of claim 21 wherein the node identifiers further comprise local link identifiers.

Claim 32

Dependent Claim 37 words

The method of claim 21 wherein the transmit/receive schedule is determined using a working schedule comprising a set of valid transmission times and/or channels and a feasible schedule comprising a set of valid listening times and/or channels.

Claim 33

Dependent Claim 20 words

The method of claim 29 wherein the working and feasible schedules are updated upon receipt of each of the packets.

Claim 34

Independent Claim 34 words

The method of claim wherein the working schedule is updated according to a protocol in which established communication times and/or channels between nodes of the network take precedence over requested communication times and/or channels.

Claim 35

Dependent Claim 31 words

The method of claim 31 wherein under the protocol communication schedules for broadcast transmissions take precedence over those for multicast transmissions which, in turn, take precedence over those for unicast transmissions.

Claim 36

Dependent Claim 30 words

The method of claim 32 wherein under the protocol nodes of the network may only schedule one communication session with other nodes of the network during a particular time/channel period.

Claim 37

Dependent Claim 23 words

The method of claim 33 wherein any communication session between nodes of the network must occupy contiguous time periods over a designated channel.

Claim 38

Dependent Claim 32 words

The method of claim 30 wherein the feasible schedule is updated according to a protocol in which established and/or requested communication sessions between nodes of the network take precedence over listening times.

Claim 39

Dependent Claim 28 words

The method of claim 30 wherein requested communication sessions are added to the working schedule after verifying that the requested sessions can be accommodated using the feasible schedule.

Claim 40

Independent Claim 72 words

A method, comprising: in a wireless network in which time is divided into slots and slots are grouped into frames: sending one or more schedule packets from a node within said network that identify: active scheduled links (ASLs) between said node and said node's neighbors, said neighbors being identified with node identifiers, said ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel.

Claim 41

Independent Claim 72 words

A method, comprising: in a wireless network in which time is divided into slots and slots are grouped into frames: sending one or more schedule packets from a node within said network that identify: active scheduled links (ASLs) between said node and said node's neighbors, said neighbors being identified with node identifiers, said ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel.

Claim 42

Dependent Claim 23 words

The method of claim 37 wherein multiple slots of each frame are reserved for sending schedule packets amongst nodes within said wireless network.

Claim 43

Dependent Claim 28 words

The method of claim 37 wherein at least one of said schedule packets further comprise a list of outgoing ASLs for said node to transmit to its neighbors.

Claim 44

Dependent Claim 28 words

The method of claim 39 wherein said list at least partially specifies an outgoing ASL by a node identifier assigned to the neighbor associated with said outgoing ASL.

Claim 45

Dependent Claim 29 words

The method of claim 40 wherein said list at least partially further specifies said outgoing ASL by an indication as to whether said outgoing ASL is established or requested.

Claim 46

Dependent Claim 25 words

The method of claim 41 wherein said list at least partially further specifies said outgoing ASL by the slot range occupied by said outgoing ASL.

Claim 47

Dependent Claim 30 words

The method of claim 39 wherein said at least one of said schedule packets further comprise a list of incoming ASLs for said node's neighbors to transmit to said node.

Claim 48

Dependent Claim 34 words

The method of claim 43 wherein said list of incoming ASLs at least partially specifies an incoming ASL by a node identifier assigned to said node by the neighbor associated with said incoming ASL.

Claim 49

Dependent Claim 32 words

The method of claim 44 wherein said list of incoming ASLs at least partially further specifies said incoming ASL by an indication as to whether said incoming ASL is established or requested.

Claim 50

Dependent Claim 28 words

The method of claim 45 wherein said list of incoming ASLs at least partially further specifies said incoming ASL by the slot range occupied by said incoming ASL.

Claim 51

Dependent Claim 18 words

The method of claim 37 wherein said elements further include: idle slot ranges (ISRs) within said 2-hop neighborhood.

Claim 52

Dependent Claim 31 words

The method of claim 47 wherein said list of ISRs at least partially specifies an ISR by an indication as to whether or not said node is listening on said ISR.

Claim 53

Dependent Claim 18 words

The method of claim 37 herein said one or more schedule packets are a plurality of schedule packets.

Claim 54

Dependent Claim 17 words

The method of claim 37 wherein said one or more schedule packets is a single schedule packet.

Claim 55

Dependent Claim 28 words

The method of claim 37 wherein said node's 2-hop neighborhood is described by said node at least in terms of all known nodes in said node's 2-hop neighborhood.

Claim 56

Independent Claim 101 words

A method, comprising: in a wireless network in which time is divided into slots and where slots are grouped into frames, and where multiple slots of individual frames are reserved for sending schedule packets amongst nodes within said wireless network: receiving schedule packets at a node within said network, said schedule packets including descriptions of active scheduled links (ASLs), said ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel; and, building, at said node, an understanding of said node's 2-hop neighborhood from information contained in said one or more schedule packets.

Claim 57

Independent Claim 101 words

A method, comprising: in a wireless network in which time is divided into slots and where slots are grouped into frames, and where multiple slots of individual frames are reserved for sending schedule packets amongst nodes within said wireless network: receiving schedule packets at a node within said network, said schedule packets including descriptions of active scheduled links (ASLs), said ASLs corresponding to a reserved group of contiguous slots having a specific start slot and an associated data channel; and, building, at said node, an understanding of said node's 2-hop neighborhood from information contained in said one or more schedule packets.

Claim 58

Dependent Claim 19 words

The method of claim 52 wherein said understanding further comprises node identifiers of all of said node's 1-hop neighbors.

Claim 59

Dependent Claim 20 words

The method of claim 52 wherein said understanding further comprises the ASLs advertised by all of said node's 1-hop neighbors.

Claim 60

Dependent Claim 23 words

The method of claim 54 wherein a first portion of said ASLs are established and a second portion of said ASLs are requested.

Claim 61

Dependent Claim 20 words

The method of claim 52 wherein said understanding further comprises the ISRs advertised by all of said node's 1-hop neighbors.

Claim 62

Dependent Claim 43 words

The method of claim 52 wherein said understanding further comprises: 1) node identifiers of all of said node's 1 hop neighbors; 2) the ASLs advertised by all of said node's 1-hop neighbors; 3) the ISRs advertised by all of said node's 1-hop neighbors.

Claim 63

Dependent Claim 23 words

The method of claim 57 wherein a first portion of said ASLs are established and a second portion of said ASLs are requested.

Claim 64

Dependent Claim 20 words

The method of claim 52 wherein said multiple slots further comprises a first few slots of each of said frames.

Claim 65

Dependent Claim 36 words

The method of claim 52 wherein each of said schedule packets further comprise, relative to its corresponding transmitting node, a list of outgoing active scheduled links (ASLs) for the transmitting node to transmit to its neighbors.

Claim 66

Dependent Claim 28 words

The method of claim 60 wherein said list at least partially specifies an outgoing ASL by a node identifier assigned to the neighbor associated with said outgoing ASL.

Claim 67

Dependent Claim 28 words

The method of claim 61 wherein said list at least partially further specifies said outgoing ASL by an indication as to whether said ASL is established or requested.

Claim 68

Dependent Claim 25 words

The method of claim 62 wherein said list at least partially further specifies said outgoing ASL by the slot range occupied by said outgoing ASL.

Claim 69

Dependent Claim 35 words

The method of claim 60 wherein each of said schedule packets further comprise, relative to its corresponding transmitting node, a list of incoming ASLs for said transmitting node's neighbors to transmit to said transmitting node.

Claim 70

Dependent Claim 35 words

The method of claim 64 wherein said list of incoming ASLs at least partially specifies an incoming ASL by a node identifier assigned to said transmitting node by the neighbor associated with said incoming ASL.

Claim 71

Dependent Claim 32 words

The method of claim 65 wherein said list of incoming ASLs at least partially further specifies said incoming ASL by an indication as to whether said incoming ASL is established or requested.

Claim 72

Dependent Claim 28 words

The method of claim 66 wherein said list of incoming ASLs at least partially further specifies said incoming ASL by the slot range occupied by said incoming ASL.

Claim 73

Dependent Claim 23 words

The method of claim 64 wherein said at least one of said schedule packets further comprise a list of idle slot ranges (ISRs).

Claim 74

Dependent Claim 31 words

The method of claim 68 wherein said list of ISRs at least partially specifies an ISR by an indication as to whether or not said node is listening on said ISR.

Claim 75

Independent Claim 138 words

A method, comprising: in a wireless network in which time is divided into slots and where slots are grouped into frames, and where schedule packets sent between nodes in said network identify established active scheduled links (ASLs) and requested ASLs, and where said ASLs correspond to a reserved group of contiguous slots having a specific start slot and an associated data channel: adhering to etiquette rules, at a plurality of nodes within said network, to implement a distributed listen-to-schedule before requesting channel reuse approach, said etiquette rules comprising: 1) a node can request an ASL after listening to slots containing schedule packet information for a number of frames in order to obtain the current state of its 2-hop neighborhood; and, 2) an already established ASL has precedence over any requested ASL that conflicts with the already established ASL.

Claim 76

Independent Claim 138 words

A method, comprising: in a wireless network in which time is divided into slots and where slots are grouped into frames, and where schedule packets sent between nodes in said network identify established active scheduled links (ASLs) and requested ASLs, and where said ASLs correspond to a reserved group of contiguous slots having a specific start slot and an associated data channel: adhering to etiquette rules, at a plurality of nodes within said network, to implement a distributed listen-to-schedule before requesting channel reuse approach, said etiquette rules comprising: 1) a node can request an ASL after listening to slots containing schedule packet information for a number of frames in order to obtain the current state of its 2-hop neighborhood; and, 2) an already established ASL has precedence over any requested ASL that conflicts with the already established ASL.

Claim 77

Dependent Claim 70 words

The method of claim 70 wherein said etiquette rules further comprise: For two requested ASLs that conflict with each other: 1) ASLs for broadcast transmission have precedence over ASLs for multicast or unicast transmission; 2) ASLs for multicast transmission have precedence over ASLs for unicast transmission; 3) Among the ASLs with the same precedence due to the type of transmission, the ASL with the smallest schedule priority ticket has precedence.

Claim 78

Dependent Claim 34 words

The method of claim 70 wherein said etiquette rules further comprise: No ASL to or from a given node may overlap on any time slot with another ASL to or from the same node.

Claim 79

Dependent Claim 31 words

The method of claim 70 herein said etiquette rules further comprise: The slots of an ASL must be contiguous and the same data channel must be used for the entire ASL.

Claim 80

Dependent Claim 50 words

The method of claim 70 wherein said schedule packets also identify ISRs and said etiquette rules further comprise: ASLs have precedence over ISRs, and between two ISRs that use the same channel and overlap in at least one time slot, the ISR with the smallest schedule priority ticket has precedence.

Claim 81

Dependent Claim 40 words

The method of claim 74 further comprising updating a feasible schedule of a node by applying said rule of claim 74 to any updated or new ISRs found in those of said packets reported by a neighbor of said node.

Claim 82

Dependent Claim 48 words

The method of claim 70 wherein said schedule packets also identify ISRs and said etiquette rules further comprise: During any given time slot assigned for data transmission, a node that is not transmitting or receiving on an established ASL must be listening in one of its advertised ISRs.

Claim 83

Dependent Claim 53 words

The method of claim 70 wherein said schedule packets also identify ISRs and said etiquette rules further comprise: When node i needs to establish a new ASL with a neighbor j, it must choose one of the advertised ISRs from j in a way that does not conflict with any other etiquette rules.

Claim 84

Dependent Claim 19 words

The method of claim 70 wherein said etiquette rules further comprise: A node can transmit only over established ASLs.

Claim 85

Dependent Claim 37 words

The method of claim 70 wherein said schedule packets also identify ISRs and said etiquette rules further comprise: Transmissions over an advertised ISR must be done using a listen-before-talk etiquette over the channel specified for the ISR.

Claim 86

Dependent Claim 163 words

The method of claim 70 further comprising, to update a node's working schedule, applying the following rules upon each new or updated ASL found in those of said packets reported by a neighbor of said node to determine if said each new or updated ASL is valid: 2) said rule where an already established ASL has precedence over any requested ASL that conflicts with the already established ASL; 3a) ASLs for broadcast transmission have precedence over ASLs for multicast or unicast transmission; 3b) ASLs for multicast transmission have precedence over ASLs for unicast transmission; 3c) Among the ASLs with the same precedence due to the type of transmission, the ASL with the smallest schedule priority ticket has precedence; 4) No ASL to or from a given node may overlap on any time slot with another ASL to or from the same node; 5) The slots of an ASL must be contiguous and the same data channel must be used for the entire ASL.

Claim 87

Dependent Claim 31 words

The method of claim 80 further comprising, for said each new or updated ASL, scanning conflict classes of each slot within a slot rage attributed to a new or updated ASL.

Claim 88

Dependent Claim 32 words

The method of claim 81 further comprising regarding as invalid any said new or updated ASL deemed to violate any of said rules in any of said new or updated ASL's slots.

Claim 89

Dependent Claim 56 words

The method of claim 80 further comprising, for a new or updated ASL, scanning a conflict class defined for a channel used in the system, where, said conflict class is associated with a slot and a channel and includes all valid and proposed ASLs that use said conflict class's channel and include said conflict class's slot.

Claim 90

Dependent Claim 36 words

The method of claim 83 further comprising picking said channel and regarding as invalid any said new or updated ASL deemed to violate any of said rules in any of said new or updated ASL's slots.

Claim 91

Dependent Claim 59 words

The method of claim 70 wherein said schedule packets also identify ISRs, said method further comprising requesting, by a node, a new ASL with a neighbor of said node by selecting an ISR maintained by said node for said neighbor, such that, said slot range is larger than or equal to the slot range needed for said new ASL.

Claim 92

Dependent Claim 29 words

The method of claim 85 further comprising: adding said requested ASL to said node's working schedule; and, requesting said ASL in a following schedule packet launched by said node.

Claim 93

Dependent Claim 242 words

The method of claim 70 wherein said schedule packets also identify ISRs and said rules of etiquette further comprise: 3a) ASLs for broadcast transmission have precedence over ASLs for multicast or unicast transmission; 3b) ASLs for multicast transmission have precedence over ASLs for unicast transmission; 3c) Among the ASLs with the same precedence due to the type of transmission, the ASL with the smallest schedule priority ticket has precedence; 4) No ASL to or from a given node may overlap on any time slot with another ASL to or from the same node; 5) The slots of an ASL must be contiguous and the same data channel must be used for the entire ASL; 6) ASLs have precedence over ISRs, and between two ISRs that use the same channel and overlap in at least one time slot, the ISR with the smallest schedule priority ticket has precedence; 7) During any given time slot assigned for data transmission, a node that is not transmitting or receiving on an established ASL must be listening in one of its advertised ISRs; 8) When node i needs to establish a new ASL with a neighbor j, it must choose one of the advertised ISRs from j in a way that does not conflict with any other etiquette rules; 9) A node can transmit only over established ASLs; 10)Transmissions over an advertised ISR must be done using a listen-before-talk etiquette over the channel specified for the ISR.

Claim 94

Dependent Claim 59 words

The method of claim 87 further comprising, at a node, selecting which of said ISRs to report in a schedule packet to be launched by said node by: monitoring utilization of available channels; selecting those of said channels that are least utilized; determining those of said ISRs that can exist over said least utilized channels according to said rules.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2007-09-07	2008-03-08	2008-09-07	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2011-09-07	2012-03-08	2012-09-07	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2015-09-07	2016-03-08	2016-09-07	$7700.00	Window Closed / Lapsed

Protocol for neighborhood-established transmission scheduling

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag