IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0767171
(2007-06-22)
|
등록번호 |
US-8320321
(2012-11-27)
|
발명자
/ 주소 |
- Joshi, Avinash
- Shukla, Manish
|
출원인 / 주소 |
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
7 인용 특허 :
3 |
초록
▼
A hybrid TDMA-CSMA MAC protocol is provided for allocating time slots within a frame having a structure in which transmission time is divided into a first number of actual TDMA time slots and a second number of “virtual” CSMA time slots. Each time a given node receives a Hello message, it can calcul
A hybrid TDMA-CSMA MAC protocol is provided for allocating time slots within a frame having a structure in which transmission time is divided into a first number of actual TDMA time slots and a second number of “virtual” CSMA time slots. Each time a given node receives a Hello message, it can calculate variables based on an HSN field. A ratio of the first number to the second number can be dynamically adjusted depending upon the traffic conditions. When TDMA time slots within the frame are freed (e.g., no longer being used), slot position optimization techniques are provided for moving these freed TDMA time slots back into the CSMA portion of the frame and reallocating or moving other TDMA time slots into the portion of the frame that was previously occupied by the freed TDMA time slots to thereby maximize resource utilization.
대표청구항
▼
1. A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the
1. A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the frame comprising at least one or more Hello time slots; and a Carrier Sense Multiple Access (CSMA) portion of the frame comprising a second number of virtual time slots, the method comprising: determining a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame based on one or more boundary variables, wherein the one or more boundary variables are computed based on information contained in a hello message received in a hello time slot of the one or more hello time slots, wherein the information contained in the hello message comprises:one or more time slots currently being used by a node and its neighbor nodes, anda Highest Slot Number (HSN) field which indicates a highest slot number being used by the node or its neighbor nodes;determining whether the TDMA portion of the frame comprises free time slots which are no longer being used by the nodes; andupdating the virtual boundary by decreasing the first number if the frame includes free time slots by relocating currently used time slots in the TDMA portion of the frame to the free time slots in the TDMA portion of the frame. 2. A method according to claim 1, wherein the step of decreasing the first number if the frame includes free time slots by relocating currently used time slots in the TDMA portion of the frame to the free time slots in the TDMA portion of the frame, comprises: decreasing the first number if the frame includes free lower-numbered time slots by relocating currently used higher-numbered time slots in the TDMA portion of the frame to the free lower-numbered time slots in the TDMA portion of the frame to reduce the neighborhood highest slot number (HSN) used in the TDMA portion of the frame thereby adding free TDMA slots to CSMA portion of the frame and increasing bandwidth utilization in the network. 3. A method according to claim 2, further comprising: increasing the second number of virtual time slots in the CSMA portion of the frame by reducing neighborhood HSN which moves the virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame, wherein the virtual boundary comprises a ratio of a first number of actual time slots in the TDMA portion of the frame to the second number of virtual time slots of the CSMA portion of the frame. 4. A method according to claim 3, wherein the step of increasing the second number of virtual time slots in the CSMA portion of the frame comprises: moving a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame by increasing the second number of virtual time slots in the CSMA portion of the frame to decrease a CSMA start (CSMAS) time comprising the sum of one and a neighborhood-highest slot number to maximize bandwidth utilization in the network, wherein the CSMAS time and the virtual boundary dynamically change as the first number of time slots are allocated for transmission in the TDMA portion of the frame. 5. A method according to claim 1, wherein the free time slots were previously being used by one of the nodes, are currently located within the TDMA portion of the frame and are no longer being used by the nodes. 6. A method according to claim 5, wherein the free time slots are located between the Hello time slot and the neighborhood highest slot number (HSN) in the TDMA portion of the frame. 7. A method according to claim 1, further comprising: determining, at the particular node, whether the particular node is eligible to initiate a time slot move. 8. A method according to claim 7, wherein the step of determining, at the particular node, whether the particular node is eligible to initiate a time slot move comprises: determining, at the particular node, whether there is at least one free time slot in the TDMA portion of the frame which has a lower slot number than at least one of the time slots in the TDMA portion of the frame that is currently being used by the particular node; andif there is at least one free time slot in the TDMA portion of the frame which has a lower slot number than one of the time slots in the TDMA portion of the frame that is currently being used by the particular node, determining, at the particular node, whether at least one time slot in TDMA portion of the frame that is currently being used by the particular node has a slot number equal to a neighborhood Highest Slot Number (HSN), andwherein the step of decreasing the first number if the frame includes free time slots by relocating currently used time slots in the TDMA portion of the frame to the free time slots in the TDMA portion of the frame comprises:decreasing the first number if at least one time slot in TDMA portion of the frame that is currently being used by the node has a slot number equal to a neighborhood Highest Slot Number (HSN) in the TDMA portion of the frame by relocating at least one of the time slot in TDMA portion of the frame that is currently being used by the node to the free time slots in the TDMA portion of the frame. 9. A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the frame comprising at least one or more Hello time slots; and a Carrier Sense Multiple Access (CSMA) portion of the frame comprising a second number of virtual time slots, the method comprising: determining a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame based on one or more boundary variables, wherein the one or more boundary variables are computed based on information contained in a hello message received in a hello time slot of the one or more hello time slots, wherein the information contained in the hello message comprises:one or more time slots currently being used by a node and its neighbor nodes, anda Highest Slot Number (HSN) field which indicates a highest slot number being used by the node or its neighbor nodes;determining whether to move at least one unused time slot in the TDMA portion of the frame into the CSMA portion of the frame; andupdating the virtual boundary by moving the unused time slot from the TDMA portion of the frame into the CSMA portion of the frame, if it is determined that the unused time slot in the TDMA portion of the frame is to be moved into the CSMA portion of the frame. 10. A method according to claim 9, wherein the step of determining whether to move at least one unused time slot in the TDMA portion of the frame into the CSMA portion of the frame, comprises: determining, based on a current arrangement of the time slots in the TDMA portion of the frame, whether to move at least one active time slot in the TDMA portion of the frame into at least one unused time slot in the TDMA portion of the frame and to move the at least one unused time slot in the TDMA portion of the frame into the CSMA portion of the frame. 11. A method according to claim 10, wherein the step of moving the unused time slot from the TDMA portion of the frame into the CSMA portion of the frame, if it is determined that the unused time slot in the TDMA portion of the frame is to be moved into the CSMA portion of the frame, comprises: moving at least one active time slot in the TDMA portion of the frame into at least one unused time slot in the TDMA portion of the frame and moving the at least one unused time slot in the TDMA portion of the frame into the CSMA portion of the frame, if it is determined that the unused time slot in the TDMA portion of the frame is to be moved into the CSMA portion of the frame. 12. A method according to claim 11, wherein the step of determining whether to move at least one unused time slot in the TDMA portion of the frame into the CSMA portion of the frame based on a current arrangement of the time slots in the TDMA portion of the frame, comprises: determining, based on a current arrangement of the time slots in the TDMA portion of the frame, whether to move at least one active time slot in the TDMA portion of the frame into the at least one unused time slot in the TDMA portion of the frame to increase the second number of virtual time slots in the CSMA portion of the frame and to decrease the number of unused time slots in the TDMA portion of the frame thereby improving frame utilization. 13. A method according to claim 12, wherein the step of moving the unused time slot from the TDMA portion of the frame into the CSMA portion of the frame, if it is determined that the unused time slot in the TDMA portion of the frame is to be moved into the CSMA portion of the frame, comprises: moving at least one active time slot in the TDMA portion of the frame into the at least one unused time slot in the TDMA portion of the frame to increase the second number of virtual time slots in the CSMA portion of the frame and to decrease the number of unused time slots in the TDMA portion of the frame thereby improving frame utilization, if it is determined that the unused time slot in the TDMA portion of the frame is to be moved into the CSMA portion of the frame. 14. A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the frame comprising at least one or more Hello time slots; and a Carrier Sense Multiple Access (CSMA) portion of the frame comprising a second number of virtual time slots, the method comprising: determining a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame based on one or more boundary variables, wherein the one or more boundary variables are computed based on information contained in a hello message received in a hello time slot of the one or more hello time slots, wherein the information contained in the hello message comprises:one or more time slots currently being used by a node and its neighbor nodes, anda Highest Slot Number (HSN) field which indicates a highest slot number being used by the node or its neighbor nodes;determining, at a particular node, whether the particular node is eligible to initiate a time slot move; andupdating the virtual boundary by initiating the time slot move at the particular node if the particular node is eligible to initiate the time slot move. 15. A method according to claim 14, wherein the step of determining, at a particular node, whether the particular node is eligible to initiate a time slot move, comprises: determining, at the particular node, whether there is at least one free time slot in the TDMA portion of the frame which has a lower slot number than at least one of the currently used time slot in the TDMA portion of the frame being used by the particular node;determining, at the particular node, whether at least one time slot in TDMA portion of the frame that is currently used by the particular node has a slot number equal to a neighborhood Highest Slot Number (HSN), if the particular node determines that there is at least one free time slot in the TDMA portion of the frame which has a lower slot number than one of the currently used time slot in the TDMA portion of the frame being used by the particular node. 16. A method according to claim 15, wherein the step of initiating the time slot move at the particular node if the particular node is eligible to initiate the time slot move, comprises: initiating the time slot move at the particular node if the particular node determines that at least one time slot in the TDMA portion of the frame that is currently used by the particular node has a slot number equal to the neighborhood Highest Slot Number (HSN). 17. A method according to claim 14, wherein the step of initiating the time slot move, comprises: transmitting, from the particular node, a Scout Request packet comprising a current transmission possible slot map (TPSM). 18. A method according to claim 17, wherein the step of transmitting a Scout Request packet comprising a current TPSM, comprises: scheduling, at the particular node, the Scout Request packet to be sent in the CSMA portion of the frame after the particular node completes a current transmission; andtransmitting, from the particular node, the Scout Request packet during the CSMA portion of the frame, wherein the Scout Request packet comprises a current TPSM map. 19. A method according to claim 18, further comprising: receiving, at a next hop node, the Scout Request packet from particular node and selecting, at the next hop node, a transmission possible time slot in the TDMA portion of the frame from the current TPSM map of the Scout Request packet;determining, at the next hop node, whether the selected transmission possible time slot has a lower slot number than one of the time slots in the TDMA portion of the frame that is currently being used by the next hop node;transmitting, from the next hop node, a Scout Reply packet comprising new slot allocation information to the particular node, if the selected transmission possible time slot has a lower slot number than one of the time slots in the TDMA portion of the frame that is currently being used by the next hop node; andreceiving, at the particular node, the Scout Reply packet and transmitting a Scout ACK message to the next hop node to acknowledge the time slot switch. 20. A method according to claim 19, wherein the Scout Reply packet further comprises information which identifies freed time slots in the TDMA portion of the frame which are no longer being used by the particular node after the time slot switch. 21. A method according to claim 19, wherein the Scout ACK message comprises: information which identifies freed time slots in the TDMA portion of the frame which are no longer being used by the particular node after the time slot switch. 22. A method according to claim 14, wherein the first number of the time slots of the TDMA portion of the frame are used to transmit periodic traffic if the first number is greater than one, and wherein the second number of virtual time slots of the CSMA portion of the frame are used to transmit non-periodic traffic. 23. A method for optimizing bandwidth utilization in a multi-hop ad hoc network comprising a plurality of nodes which communicate using a frame comprising a plurality of time slots, wherein the frame comprises: a first number of the time slots for a Time Division Multiple Access (TDMA) portion of the frame comprising at least one or more Hello time slots; and a Carrier Sense Multiple Access (CSMA) portion of the frame comprising a second number of virtual time slots, the method comprising: allocating, to each of the plurality of nodes, a hello time slot from the one or more hello time slots;transmitting, by at least one node of the plurality of nodes, at least a highest slot number (HSN) value in the allocated hello time slot of the one or more hello time slots, wherein the at least HSN value indicates a highest slot number being used by the at least one node or a neighbor node of the at least one node;determining, by the at least one node, a virtual boundary between the TDMA portion of the frame and the CSMA portion of the frame based on one or more boundary variables, wherein the one or more boundary variables are computed based on information contained in a hello message received in the hello time slot, wherein the information contained in the hello message comprises:one or more time slots currently being used by a node and its neighbor nodes, anda Highest Slot Number (HSN) field which indicates a highest slot number being used by the node or its neighbor nodes; determining whether the TDMA portion of the frame comprises free time slots which are no longer being used by the nodes; andupdating the virtual boundary by decreasing the first number if the frame includes free time slots by relocating currently used time slots in the TDMA portion of the frame to the free time slots in the TDMA portion of the frame.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.