Title of Invention

METHOD FOR DYNAMICALLY SHIFTING AND COLLISION DETECTION OF BEACONS IN DISTRIBUTED WIRELESS NETWORKS

Abstract

This invention explains a method for dynamically shifting beacons and collision detection during shifting of beacons in distributed wireless networks utilizing the method of dynamic shifting of beacons which involves selection of a free beacon slot for beacon shifting and protection of the said beacon slot and the method of collision detection while shifting of beaon which involves detection by looking to the enhanced BPOIE. This invention relates to the field of wireless networks. Further, this invention relates to medium access control for wireless personal area networks that are based on wireless mobile ad-hoc networks. Particularly this invention relates to medium access control for wireless personal area networks which does not have any central coordinator. More particularly, this invention relates to effective mechanisms for the devices in sending their beacons.

Full Text

FIELD OF TECHNOLOGY This invention relates to the field of wireless networks. Further, this invention relates to medium access control for wireless personal area networks that are based on wireless mobile ad-hoc networks. Particularly this invention relates to medium access control for wireless personal area networks which does not have any central coordinator. More particularly, this invention relates to effective mechanisms for the devices in sending their beacons. More particularly, it provides mechanisms for dynamically shifting the location of beacon for better and efficient utilization of channel time. Also more particularly, this invention encompasses a system and method for beaconing in wireless personal area networks based on ultra wide band (UWB) systems. DESCRIPTION OF RELATED ART The wireless personal area networks are defined to operate in the personal operating space, i.e. in a range of approximately 10 meters. The IEEE (http://www.ieee.orq) is involved in defining standards for such wireless personal area networks. The Ultra Wide Band (UWB) technology can provide data rates exceeding several hundreds of Mbps in this personal operating space. In wireless personal area networks, the medium is shared between all the devices for communication with each other. This necessitates a medium access control mechanism for the devices to manage medium access, broadly including how it may join the network, how it can transfer data at the required rate to another device, how the medium is best used, how to detect and resolve beacon collisions etc. Medium access control for wireless personal area networks can be designed in two approaches - centralized and distributed. In the centralized approach, one of the device acts on behalf of the whole network to coordinate in managing the medium access operations for ail the devices. All other devices seek help of the centralized coordinator for medium access operations like joining the network, reserving channel time, etc. In the Distributed approach, the medium access operations are distributed evenly across all devices in the network and all the devices share the load of managing medium access operations for each other. While the IEEE standards employ a centralized medium access control mechanisms, some distributed medium access control mechanisms are under discussions for WPANs as they offer flexibility in terms of mobility of devices. Figure 1 show the wireless personal area network, which is based on distributed approach and which does not have any centralized coordinator. It involves a decentralized WPAN, in which devices are light coordinator and there is no dedicated coordinator present. All devices cooperate and share information with each other to perform the medium access control tasks such as allowing a new device to join, allocation of channel time to a device to transmit data to another device, synchronization mechanisms etc. This is a Distributed WPAN system which is formed in an ad-hoc fashion. Each device periodically broadcasts the information about its neighbors and allocated channel time to its neighbors. The Distributed medium access control approach relies on a timing concept called the Superframe. Superframe has a fixed length in time and is divided into a number of time windows which are called time slots. Some of the time slots are used by the devices to send their beacons and the other are used by the devices to send the data. The slots in which beacon is sent are called beacon slots and the slots in which data is sent are called data slots. The length of a beacon period may be less than the length of a data period. The beacon slots may be distributed across the slots in the superframe or may appear together at the start of the superframe. In addition, the number of beacon slots may be fixed or variable leading to different configurations of Distributed Medium Access Control mechanisms. Figure 2 illustrates the superframe structure, specified by the Multiband OFDM Alliance (MBOA, http://www.multibandofdm.orq) draft vO.5. It consists of several Medium Access Slots (as an example, the number is shown as 256). Some Medium Access Slots (MAS) constitute beacon period (comprising of beacon slots corresponding to multiple devices) and remaining MASes constitute data period (comprising of MASes those may be used by different devices in the network to transmit data to other devices in the network), employs superframe of duration 65 milli-second, and each MAS is of 256 microsecond duration. If the beacon period is of dynamic length, i.e. the length of the beacon period is increased when there are more number of devices beaconing and similarly, the length of beacon period is reduced when there are a few devices beaconing, then it is useful both for power saving aspects as well as for making a larger portion of superframe available for data communication when there are fewer devices. It is important to note here that the channel time allocation schemes and beaconing schemes should be independent of the actual values of these parameters. Information about superframe is being broadcasted by each device in its broadcasted beacons in beacon period, so neighbors of that device can use that information for further processing. The start time of the superframe is determined by the beginning of the beacon period and defined as the beacon period start time (BPST). Devices shall utilize the same BPST for the superframe. MASes are numbered relative to this starting time. All devices shall hear the beacon period at the start of the superframe and shall be time synchronized. Devices include the BPOIE in all beacons. The BPOIE shall only include beacon information of devices that are heard by the device in the beacon period. Upon reception of a beacon frame, a device saves the DEVID of the sender alongwith the slot index where the beacon is received. This information is included in the BPOIE sent in the following superframe. Only the information of beacons received during a superframe is included in the BPOIE sent in the following superframe. It is important to note here that BPOIE is a way to represent the occupancy of the beacon slot by a device in 2 hop neighborhood and it is independent of beaconing procedure. If the DEVID of the device is missing in the BPOIE from a neighboring beacon during mMaxLostBeacons consecutive superframes, the device shall change the beacon slot to an idle slot in the following superframe. The present state of art in this field, has certain limitations, namely, there is no mechanism to shift the beacon in such manner that overall size of beacon period get dynamically reduced allowing devices to use larger part of superframe for either data transfer or power saving. Currently the medium access control mechanism, as defined in current art, can suffer from following limitations: 1. In an environment where many devices are in use, a large beacon period might be established. As devices leave the area or are turned off, the beacon slots they use become free; it is possible that these free beacon slots are in middle of the BP. Even when there are free slots in middle of BR, size of BP is still large. This results in an inefficient use of the channel time of the superframe. 2. Device can scan the channel and can shift the beacon to a lower free slot (i.e. slot having an earlier location in time in the BP), but if many devices attempt to do same simultaneously then there can be a beacon collision again and device may loose its current beacon slot and does not get new beacon slot. 3. Due to large beacon period with less population of beacons, the usable portion of the superframe for data transfer is reduced. 4. Due to large beacon period, devices are required to keep awake for large amount of time thus impacting the power save features and requirements. SUMMARY OF THE INVENTION The primary object of the invention is therefore to provide a system and method for shifting beacon to another beacon slot for the UWB wireless personal area networks, which are based on wireless ad-hoc networks, in a decentralized network topology where all devices undertakes the role of a light coordinator and there is no central coordinator. It is another object of the invention to provide a mechanism where devices can shift their beacons to a lower free slot and reduce the size of beacon period. It is another object of the invention to provide a mechanism where devices can avoid the collision while shifting their beacons. It is another object of the invention to provide the mechanism for device to detect the possible collision due to beacon shifting and avoid beacon shifting in such cases. The present invention relates to a system that allows an improved medium access control in the Wireless Personal Area Networks based on mobile ad-hoc networks in decentralized and distributed manner. The invention relates to system and method which allows all devices to shift their beacons to lower free slot by avoiding the collision. Further, the shifting of beacon is stopped by detecting possible collision. The system for the invention comprises of a new medium access control mechanism involving a new method for shifting beacon slots, an extended usage of BPOIE, a method for detection of possible collision due to shifting of beacon. The present invention comprises of system and method which would solve the problems associated with current art, in the following manner: 1. Device finds that, if any free lower slot is available and if it can shift to that slot in order to reduce the size of BP. 2. Device protects the selected free lower slot, before shifting to that slot, and broadcasts that information in its BPOIE. 3. Neighbor of that device should respect and protect the selected slot for the device in their BPOIEs. 4. Device expects the protection from all of its neighbors and if device receives protection from its neighbors then it can shift to newly selected lower beacon slot and can leave its original beacon slot. 5. If device does not get protection of the slot from all neighbors then device shall not shift its beacon, update its BPOIE with removal of its entry for the protected slot and restart the procedure. 6. If some device receives request for protection of beacon slot from more than one device then the device can choose to provide the protection for any one device. Accordingly, the invention provides a method for shifting the beacon to lower free beacon period and size reduction in beacon period. Accordingly, the invention also provides a method where devices can avoid the collision while shifting their beacons and the mechanism for device to detect the possible collision due to beacon shifting and avoid beacon shifting in such cases. Accordingly, the invented method is not dependant on shifting of beacon to only lower free slots, but same methods are applicable to shifting of beacon to any other available free slot, should the need arises. Accordingly, this invention explains a method for dynamically shifting and collision detection of beacons in distributed wireless networks wherein the said method of dynamic shifting involves selection of a free beacon slot for beacon shifting and protection of the said beacon slot and the method of collision detection involves detection by looking to the enhanced BPOIE. In dynamically shifting of beacons, the device decides if there are any free lower slots available in beacon period by hearing the beacons from its neighbors in beacon period and by looking to the occupancy information from the devices through their BPOIE, where a free lower slot is selected out of the available free slots for shifting its beacon. Before shifting the beacon to the selected slot, device protects the slot for itself by advertising the selected free lower slot as occupied in its enhanced BPOIE with extra information of DEVID of itself and slot index of selected free lower slot. When the neighbors of the device hear an enhanced BPOIE, with information of the selected lower free slot along with the DEVID of the device, neighbors consider the slot as occupied and protect the slot from other devices in 2 hop neighborhood, by adding that slot index and requester device^s DEVID in their BPOIE. As an indication for the receiving device to protect the slot for the device which is trying to shift its beacon in that selected slot the neighbor receives a beacon from the device along with device's DEVID information in BPOIE with some slot index where the said indication is a protection request to the neighbors of the device, which is trying to shift its beacon. If a device gets an indication for protecting a free slot for the device which is trying to shift its beacon, then the device adds the entry of the DEVID and selected slot index in its enhanced BPOIE. The device enters for itself with its DEVID and the selected beacon slot in the BPOIE of its neighbors' beacons in the next superframe after protecting its selected free lower slot for shifting. If the device which is trying to shift its beacon, receives entry of its protected slot in BPOIE of all its neighbors, then the device shifts its beacon to the selected slot and leaves its original slot. If device which is trying to shift its beacon, does not receive entry of protected slot, in the BPOIE from all its neighbors then it does not shift to protected slot and continue beaconing in its original slot. If the subsequent BPOIE sent by the device does not contain its DEVID against the same lower free slot then the device selects a new lower free slot. If a device receives protection request for some slot from more than one device, then device protects the slot for only one of such devices. In collision detection the device which has a higher beacon slot index in which it is beaconing currently is selected for protection which reduces the length of the dynamic beacon period. Or in collision detection a device having a lower/higher DEVID is selected for protection further BPOIE contains the information of beacon slot occupancy in the beacon period, in form of DEVID of the device and beacon slot index in which the device is beaconing. The enhanced BPOIE, includes the extra information of protected beacon slot for shifting in form of DEVID of the device which is trying to shift its beacon and slot index which is chosen by the device to shift. The device which is trying to shift its beacon uses enhanced BPOIE, which has an entry for the device sending the particular BPOIE where it acts as a protection request by the device to all its neighbors who hear this BPOIE. The neighboring device which receives the beacon distinguishes the enhanced BPOIE from the normal BPOIE. When the neighboring device sends its BPOIE in the next superframe, the DEVID of the device that is trying to shift its beacon is included twice, one against the slot index where the device is currently beaconing and another against the slot index where the device is trying to shift its beacon as per protection request. Accordingly, this invention further explains a system for dynamically shifting and collision detection of beacons in distributed wireless networks utilizing the method of dynamic shifting which involves selection of a free beacon slot for beacon shifting and protection of the said beacon slot and the method of collision detection which involves detection by looking to the enhanced BPOIE. The other objects, features and advantages of the present invention will be more apparent from the detailed description of the invention taken in conjunction with the accompanying drawings. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1 illustrates the WPAN as a decentralized and distributed ad-hoc network system and range of all devices; and Figure 2 illustrate the superframe structure in current art, which includes MASes and a dynamic beacon period (i.e. a BP with dynamic length); DETAILED DESCRIPTION OF THE INVENTION The preferred embodiments of the present invention will now be explained with reference to the accompanying drawings. It should be understood however that the disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms. The following description and drawings are not to be construed as limiting the invention and numerous specific details are described to provide a thorough understanding of the present invention, as the basis for the claims and as a basis for teaching one skilled in the art how to make and/or use the invention. However in certain instances, well-known or conventional details are not described in order not to unnecessarily obscure the present invention in detail. The present invention relates to a system that allows an improved medium access control in the decentralized Wireless Personal Area Networks based on mobile ad-hoc networks. The invention relates to system and method which allows device to shift its beacon to free lower slots in order to reduce the size of the beacon period, without collision due to shifting. This is done by protecting the slots, in which device wishes to shift the beacon. The system for the invention comprises of a new medium access control mechanism involving a new method for protecting the beacon slot in which a device wants to shift its beacon, a new method for detection of possible collision in the newly selected beacon slot for shifting the beacon and enhanced usage of the BPOIE for accomplishing the invented methods. Accordingly, the invention provides a method for shifting the beacon to a lower free beacon slot in the beacon period and size reduction in beacon period. Accordingly, the invention also provides a method where devices can avoid the collision while shifting their beacons and the mechanism for device to detect the possible collision due to beacon shifting and avoid beacon shifting in such cases. Accordingly, the invented method is not dependant on shifting of beacon to only lower free slots, but same methods are applicable to shifting of beacon to any other available free slot, should the need arises. The subsequent subsections describe the operations to effect the invention: 1 Selection of a free beacon slot for beacon shifting and protection of such beacon slot Following are the invented steps for protection of beacon slots by the device and its neighbors for shifting of beacon to the selected slot in a beacon collision avoidance mechanism. Invented method incorporates enhancement in the usage of BPOIE by providing extra information of beacon slot, selected for beacon shifting, for its protection. Protection of the slot ensures that the selected slot shall not be taken up by some other device for beaconing in 2 hop neighbors of the device. 1) Device hears the beacons from its neighbors in beacon period and by looking to the occupancy information from the devices through their BPOIE, device decides if there are any free lower slots available in beacon period. It then selects a free lower slot out of the available slots for shifting its beacon. Device may try shifting its beacon to any of the free lower slots randomly. 2) After selecting free lower slot, and before shifting the beacon to that selected slot, device protects that slot for itself by advertising it (selected free lower slot) as occupied in its enhanced BPOIE with extra information of DEVID of itself and slot index of selected free lower slot. The enhanced BPOIE is in the sense that, though the device is actually beaconing in some other slot, the device also includes information of its DEVID corresponding to the selected free lower slot in the BPOIE sent by it. 3) When the neighbors hear this enhanced BPOIE, with information of the selected lower free slot along with the DEVID of the device, neighbors of the device should also consider that slot as occupied and thus protect that slot from other devices in 2 hop neighborhood. So whenever some neighbor receives a beacon from the device along with device's DEVID information in BPOIE with some slot index, then it is an indication for the receiving device to protect that slot for the device (which is trying to shift its beacon in that selected slot). This indication may be considered as a protection request to the neighbors of the device, which is trying to shift its beacon. 4) If a device gets an indication for protecting a free slot for the device which is trying to shift its beacon, then the device should add the entry of the DEVID and selected slot index in its enhanced BPOIE. 5) In next superframe after protecting its selected free lower slot for shifting, device which is trying to shift its beacon expects all its neighbors, as listed above in previous step, to protect the selected slot. The device expects the entry for itself with its DEVID and the selected beacon slot in the BPOIE of its neighbors' beacons. 6) If the device which is trying to shift its beacon, receives entry of its protected slot, as expected, in BPOIE of all its neighbors, then the device can shift its beacon to the selected slot and henceforth shall leave its original slot. 7) If device which is trying to shift its beacon, does not receive entry of protected slot, as expected, in the BPOIE from all its neighbors then it shall not shift to protected slot and continue beaconing in its original slot. Further, the device should remove the protection of the slot, in which it was planning to shift to. Thus, the subsequent BPOIE sent by this device shall not contain its DEVID against the same lower free slot. However, the device can select a new lower free slot and may restart the procedure again. 2, Collision detection in selected slot for shifting beacon If more than one device selects the same free slot for shifting their beacons, then a device that can hear all of such devices can detect the possible collision by looking to the enhanced BPOIE. 1) If a device receives protection request for some slot from more than one device, then device can protect the slot for only one of such devices. 2) The device which has a higher beacon slot index (in which it is beaconing currently) can be selected for protection. This enables in reducing the length of the dynamic beacon period. 3) Further, the device having a lower/higher DEVID can be selected for protection. The subsequent subsections describe the entity to effect the invention: 1. BPOIE BPOIE contains the information of beacon slot occupancy in the beacon period from the view of the device, in form of DEVID of the device and beacon slot index in which the device is beaconing. The proposed Enhanced BPOIE, as per the invention, includes the extra information of (a) protected beacon slot for shifting in form of DEVID of the device which is trying to shift its beacon and (b) slot index which is being chosen by the device to shift. The device which is trying to shift its beacon uses enhanced BPOIE, which has an entry for the device sending the particular BPOIE. This is a protection request by the device to all its neighbors who hear this BPOIE. The neighboring device which receives the beacon can distinguish the enhanced BPOIE from the normal BPOIE, in the sense that enhanced BPOIE also contains the DEVID of the sending device. As mentioned elsewhere in this document, this enhanced BPOIE is treated as a protection request by the sending device to protect that beacon slot. When the neighboring device sends its BPOIE in the next superframe, the DEVID of the device (that is trying to shift its beacon) is included twice, in view of the protection request, (a) against the slot index where the device is currently beaconing and (b) against the slot index where the device is trying to shift its beacon as per protection request. Using the embodiments of the invention, it may be possible for a device, that is trying to shift its beacon, to select and protect more than one free slot, if required. It will also be obvious to those skilled in the art that other control methods and apparatuses can be derived from the combinations of the various methods and apparatuses of the present invention as taught by the description and the accompanying drawings and these shall also be considered within the scope of the present invention. Further, description of such combinations and variations is therefore omitted above. It should also be noted that the host for storing the applications include but not limited to a microchip, microprocessor, handheld communication device, computer, rendering device or a multi function device. Although the present invention has been fully described in connection with the preferred embodiments thereof with reference to the accompanying drawings, it is to be noted that various changes and modifications are possible and are apparent to those skilled in the art. Such changes and modifications are to be understood as included within the scope of the present invention as defined by the appended claims unless they depart therefrom. The above-presented description is of the best mode contemplated for carrying out the present invention. The manner and process of making and using it is in such a full, clear, and concise and exact terms as to enable to any person skilled in the art to which it pertains to make and use this invention. New embodiments in particular, which also lie within the scope of the invention can be created, in which different details of the different examples can in a purposeful way be combined with one another. This invention is however, susceptible to modifications and alternate constructions from that disclosed above which are fully equivalent. Consequently, it is not the intention to limit this invention to the particular embodiment disclosed. On the contrary, the intention is to cover all modifications and alternate constructions coming within the spirit and scope of the invention as generally expressed by the following claims which particularly point out and distinctly claim the subject matter of the invention. GLOSSARY OF TERMS AND DEFINITONS THEREOF BR: Beacon Period BPOIE: Beacon Period Occupancy Information Element BPST: Beacon Period Start Time DEVID: Device Identifier IE: Information Element IEEE: Institute of Electrical and Electronics Engineers MAC: Medium Access Control MAS: Medium Access Slot MBOA: Multi Band OFDM Alliance OFDM: Orthogonal Frequency Division Multiplexing UWB: Ultra Wide Band WPAN: Wireless Personal Area Network WE CLAIM 1. A method for dynamically shifting and collision detection of beacons in distributed wireless networks wherein the said method of dynamic shifting involves selection of a free beacon slot for beacon shifting and protection of the said beacon slot and the method of collision detection while shifting of beacon, which involves detection by looking to the enhanced BPOIE. 2. A method as claimed in claim 1, wherein in dynamically shifting of beacons, the device decides if there are any free lower slots available in beacon period by hearing the beacons from its neighbors in beacon period and by looking to the occupancy information from the devices through their BPOIE, where a free lower slot is selected out of the available slots for shifting its beacon. 3. A method as claimed in claim 2 wherein before shifting the beacon to the selected slot, device protects the slot for itself by advertising the selected free lower slot as occupied in its enhanced BPOIE with extra information of DEVID of itself and slot index of selected free lower slot. 4. A method as claimed in claim 3 wherein in enhanced BPOIE the device includes information of its DEVID and the selected free lower slot in the BPOIE sent by it. 5. A method as claimed in claim 3 wherein when the neighbors of the device hear an enhanced BPOIE, with information of the selected lower free slot along with the DEVID of the device, neighbors consider the slot as occupied and protects the slot from other devices in 2 hop neighborhood. A method as claimed in claim 5 wherein as an indication for the receiving device to protect the slot for the device which is trying to shift its beacon in that selected slot the neighbor receives a beacon from the device along with device's DEVID information in BPOIE with some slot index where the said indication is a protection request to the neighbors of the device, which is trying to shift its beacon. A method as claimed in claim 6 wherein if a device gets an indication for protecting a free slot for the device which is trying to shift its beacon, then the responder device, adds the entry of the DEVID and selected slot index in its enhanced BPOIE. A method as claimed in claim 7 wherein the device enters DEVID of the device trying to shift its beacon and the selected beacon slot in the BPOIE of itself in beacon in the next superframe. A method as claimed in claim 8 wherein if the device which is trying to shift its beacon, receives entry of its protected slot, in BPOIE of all its neighbors, then the device shifts its beacon to the selected slot and leaves its original slot. I. A method as claimed in claim 8 wherein if device which is trying to shift its beacon, does not receive entry of protected slot, in the BPOIE from all its neighbors then it does not shift to protected slot and continue beaconing in its original slot. .A method as claimed in claim 8 wherein if the subsequent BPOIE sent by the responder device does not contain its DEVID against the same lower free slot then the device, which is trying to shift its beacon selects a new lower free slot. !.A method as claimed in claim 1 wherein in collision detection while beacon shifting if a device receives protection request for some slot from more than one device, then device protects the slot for only one of such devices. I. A method as claimed in claim 12 wherein in collision detection while beacon shifting the device which has a higher beacon slot index in which it is beaconing currently is selected for protection which reduces the length of the dynamic beacon period. i.A method as claimed in claim 12 wherein in collision detection while beacon shifting a device having a lower/higher DEVID is selected for protection further. i.A method as claimed in claim 1 wherein BPOIE contains the information of beacon slot occupancy in the beacon period, in form of DEVID of the device and beacon slot index in which the device is beaconing. A method as claimed in claim 1 wherein the enhanced BPOIE, includes the extra information of protected beacon slot for shifting in form of DEVID of the device which is trying to shift its beacon and slot index which is chosen by the device to shift. A method as claimed in claim 1 wherein the device which is trying to shift its beacon uses enhanced BPOIE, which has an entry for DEVID of the device sending the particular BPOIE and selected free lower slot for shifting, where it acts as a protection request by the device to all its neighbors. A method as claimed in claim 1 wherein the neighboring device which receives the beacon distinguishes the enhanced BPOIE from the normal BPOIE. A method as claimed in claim 1 wherein when the neighboring device sends its BPOIE in the next superframe, the DEVID of the device that is trying to shift its beacon is included twice, one against the slot index where the device is currently beaconing and another against the slot index where the device is trying to shift its beacon as per protection request. A system for dynamically shifting and collision detection of beacons in distributed wireless networks utilizing the method of dynamic shifting which involves selection of a free beacon slot for beacon shifting and protection of the said beacon slot and the method of collision detection while beacon shifting which involves detection by looking to the enhanced BPOIE. 21. A method for dynamically shifting and collision detection of beacons in distributed wireless networks substantially as herein described particularly with reference to the drawings. 22. A system for dynamically shifting and collision detection of beacons in distributed wireless networks substantially as herein described particularly with reference to the drawings.

Documents:

0716-che-2004 abstract-duplicate.pdf

0716-che-2004 claims-duplicate.pdf

0716-che-2004 description (complete)-duplicate.pdf

0716-che-2004 drawings-duplicate.pdf

716-che-2004-abstract.pdf

716-che-2004-claims.pdf

716-che-2004-correspondnece-others.pdf

716-che-2004-correspondnece-po.pdf

716-che-2004-description(complete).pdf

716-che-2004-description(provisional).pdf

716-che-2004-drawings.pdf

716-che-2004-form 1.pdf

716-che-2004-form 5.pdf

716-che-2004-form 9.pdf