Title of Invention

METHOD FOR SUBCLUSTERING OF NETWORK FOR A DECENTRALIZED WIRELESS NETWORK

Abstract

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. The invention explains a method and system for subclustering of the network for decentralized wireless network wherein a reservation owner creates two or three private or hard reservation with subclusters of devices which acts as subset of targets depending on network topology thereby, reusing same time of the reservations by two hop neighbors and achieving spatial reuse.

Full Text

> FIELD OF INVENTION This invention relates to up- 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 for devices those sending their beacons. More particularly, this mechanism relates to power save and wakeup mechanism of the devices in wireless network. More particularly, it provides mechanisms for announcement of local wakeup intervals and global wakeup intervals of the device operating in wireless network. Also more particularly, this invention encompasses a system and method for - announcement of local and global wakeup intervals in wireless personal area networks based on ultra wide band (UWB) systems. More particularly the present invention relates to system and method for subclustering of the network for decentralized wireless network. 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.oro) 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 i.- 'r of the c^vrrlteed 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 1 multiband OFDM Alliance (MBOA, http://www.multibandofdm.ora) draft v0.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 MASs constitute data period (comprising of data slots that may be used by different devices in the network to transmit data to other devices in the network), employs a superframe duration of 65,536 micro-second with 256 MASs, and each MAS is of 256 microsecond duration. Information about superframe is being broadcasted by each device in its broadcasted beacons, 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 that belong to the same beacon period shall utilize the same BPST for the superframe. However, some of the devices may define a different time as their BPST. In such case, 2 or more beacon groups may coexist for the device. MASs are numbered relative to this starting time. The devices shall transform the numbering of MASs of other beaconing periods into the time reference of their main beaconing period. A device can be part of several beaconing periods but has to select one beaconing period as its main beaconing period. Devices shall utilize the same BPST for the superframe. MASs 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 supu^me. Only the information of beacons received during a superframe is included in the brC'" sent in the following superframe. It is important to note here that BPOIE is a way to rep.^sent 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. MASs can be reserved through Distributed Reservation Protocol (DRP). The reservation can be of different reservation type like Hard, Soft or Private. All reservation type uses different access method to access the channel. Private reservation type does not define any access method; it is up to the implementation to use an access method in private reservation. Each device which is target of the reservation or owner of the reservation sends a DRP IE in their beacon. For an example, private reservation is used by Wireless USB for its communication over MBOA based UWB channel. Wireless USB being a central entity reserve private reservation in which other devices can work over the reservation. The present state of art in this field, has certain limitations, namely, there is no mechanism to cluster the devices in network based on topology to get advantage of spatial reuse. Currently the mechanism, as defined in current art, can suffer from following limitations: Limitations in current art are explained with help of Figure 3. — H (Centralized virtual coordinator, similar to WUSB Host) reserves a private or , hard reservation (can be multicast) with all its neighboring devices and ere*,' * a single ^ster. — Due to single reservation between multiple devices, system does not get any advantage of spatial reuse of decentralized network. — E.g. Device A can communicate with 1 without any interference at same time, when device 4 and H are communicating, but current system does not allow this because, during a reservation only one device can access the medium. — Because of above reasons spatial reuse cannot be achieved. SUMMARY OF THE INVENTION The primary object of the invention is therefore to provide a system and method for clustering of target devices of the reservation by virtual centralized device (owner of the reservation) for spatial reuse purpose for the UWB wireless personal area networks, which are based on wireless ad-hoc networks, in a decentralized network topology. It is another object of the invention to provide a mechanism where target devices of the reservation can be divided in to three subclusters depending on network topology. It is another object of the invention to provide a mechanism where target devices of the reservation can be divided in to three subclusters and update in subcluster membership on change in topology. It is another object of the invention to provide a mechanism where one reservation with all target devices for an owner of the reservation can be divided in to two or three reservations to achieve spatial reuse. The present invention comprised -? system and method which would solve the problems associated with current art, in the flowing manner: 1. Method for subclustering for target devices in to three subclusters of a reservation for owner depending on network topology. 2. Method for update membership of subclusters depending on change in network topology. 3. Method to divide the reservation in two or three reservations to achieve spatial reuse. Accordingly, the invention provides a mechanism where target devices of the reservation can be divided in to three subclusters depending on network topology. Accordingly, the invention provides a mechanism where target devices of the reservation can be divided in to three subclusters and update in subcluster membership on change in topology. Accordingly, the invention provides a mechanism where one reservation with all target devices for an owner of the reservation can be divided in to two or three reservations to achieve spatial reuse. Accordingly, this invention explains a method for subclustering of the network for decentralized wireless network wherein a reservation owner creates two or three private or hard reservation with subclusters of devices which acts as subset of targets depending on network topology thereby, reusing same time of the reservations by two hop neighbors and achieving spatial reuse. There exist a Beacon Group (BG) of the device which is the set of all devices in one hop neighborhood of the device where the device always receives beacon from each devices in its BG and each device in the device's BG is able to receive beacon fron t the device. There exists a extended beacon group (EBG) which is a set of all devices in iv.' hop neighborhood of the device except the devices in beacon group of the device. 1 i^rs exists a cluster coordinator (CC) which is the owner of the reservation. There exist subclusters which are subsets of devices which are from the targets of the reservation made by cluster coordinator (CC). The method for subclustering of the network for decentralized wireless network wherein Z1, 21 and Z3 are set of devices in subclusters 1, subcluster 2 and subcluster 3 respectively and END is defined as end of the procedure to find subcluster. If all devices in CC's BG are in range of each other then no different subclusters are possible and Z1 is BG of CC, Z2 and Z3 does not have any devices. If a device exists in CC's BG, which has highest number of devices in its BG, which are common with CC's BG, or else if there exists at least one device, which has highest number of devices in its BG, which is one of the devices from earlier subset then found device is considered to be first device in Z1. Devices in BG of the first device in Z1, other than CC, are considered to be part of Z1. If there are no devices in EBG of the first device in Z1, then remaining devices are considers other than Z1 and CC in BG of CC as Z2. Devices with positive hitcount is considered in EBG of first device in Z1, as part of Z1. If all devices in EBG of the first device in Z1 have positive hitcount, then remaining devices other than Z1 and CC in BG of CC as Z2 are considered. One of the devices from EBG of the first device of Z1, is considered which is not part of Z1, which has highest number of devices in its BG other than Z1 and CC, as part of Z2 where this is the first device of Z2. Devices in BG of the first device of Z2, is consider other than Z1 and other than CC, as part of Z2. If there are no devices present in EBG of the first device in Z2, other than Z1, remaining devices BG of the CC is considered other than Z1 and Z2 in Z3. If there are devices present in EBG of the first device in Z2 with positive hitcount, then those devices in Z2 are added and remaining devices BG of the CC is considered other than Z1 and Z2 in Z3. Hitcount is an unspecified function which returns positive or negative, where return positive is an indication to add device in subcluster and negative is an indication for not adding device in subcluster where the hitcount depends on requirement of the application, environment topology or any other local or global attributes. Owner use upper layer protocol to communicate information of subcluster create a'jffeeent reservations for different subcluster. To update the membership of fife subclusters for from the targets of the CC the said method should be used periodically depending on time or number of superframes to update the membership of the subcluster. If there are changes in membership of the subcluster then owner use upper layer protocol to communicate new subcluster information to create appropriate reservations. Accordingly, this invention further explains a system for subclustering of the network for decentralized wireless network wherein a reservation owner creates two or three private or hard reservation with subclusters of devices which acts as subset of targets depending on network topology thereby, reusing same time of the reservations by two hop neighbors and achieving spatial reuse. These and other objects, features and advantages of the present invention will become more apparent from the ensuing 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. Figure 2 illustrates the superframe structure in current art, which includes MASs and a dynamic beacon period (i.e. a BP with dynamic length). Figure 3 illustrates the decentralized network with virtual centralized device (owner of the reservation) as an example for explanation. DETAILED DESCRIPTION OF THE INVENTION The preferred embodiments of the present invention will now be explained with reference to the accompanying drawing It should be understood however that the disclosed embodiments are merely exemplary f 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. ! Accordingly, the invention provides a mechanism where target devices of the reservation can be divided in to three subclusters depending on network topology. Accordingly, the invention provides a mechanism where target devices of the reservation can be divided in to three subclusters and update in subcluster membership on change in topology. Accordingly, the invention provides a mechanism where one reservation with all target devices for an owner of the reservation can be divided in to two or three reservations to achieve spatial reuse. The subsequent subsections describe the operations to effect the invention: — Instead of one private or hard reservation, the reservation owner shall create two or three private or hard reservation with subset of targets depending on network topology. These subsets are called subclusters of devices. So, same time of the reservations can be reused by two hop neighbors and spatial reuse can be achieved. — Set of all devices in one hop neighborhood of the device is called Beacon Group (BG) of the device. The device always receives beacon from each devices in its BG. Each device in the device's BG is able to receive beacon from the device. — Set of all devices in two hop neighborhood of the device except the devices in beacon group of the device, are called extended beacon group (EBG). — The device which is owner of the reservation (Hard/Private/etc) is called cluster coordinator (CC). — The subset of devices which are from the targets of the reservation made by cluster coordinator (CC), is called subclusters. — Z1 is the set of devices in subcluster 1. — 72 is the set of devices in subcluster 2. — Z3 is the set of devices in subcluster 3. — END is defined as end of the procedure to find subcluster. The following subsections describe the mechanism for find the subclusters for from the targets of the CC: — If all devices in CC's BG are in range of each other then no different subclusters are possible. Z1 is BG of CC, 72 and Z3 does not have any devices. END. — If a device exists in CC's BG, which has highest number of devices in its BG, which are common with CC's BG, else there exists at least one device, which has highest number of devices in its BG, which is one of the devices from earlier subset Found device is considered to be first device in Z1. Devices in BG of the first device in Z1, other than CC, are considered to b$ part of Z1. — If there are no devices in EBG of the first device in Z1, then consider remaining devices other than Z1 and CC in BG of CC as 72. END. — Consider devices with positive hitcount in EBG of first device in Z1, as part of Z1. N — If all devices in EBG of the first device in Z1 have positive hitcount, then consider remaining devices other than Z1 and CC in BG of CC as 72. END. — Consider one of the devices from EBG of the first device of Z1, which is not part of Z1, which has highest number of devices in its BG other than Z1 and CC, as part of 72. This is first device of 72. — Consider devices in BG of the first device of 72, other than Z1 and other than CC, as part of Z2. — If there are no devices present in EBG of the first device in 72, other than Z1, consider remaining devices BG of the CC other than Z1 and 72 in Z3. — If there are devices present in EBG of the first device in 72 with positive hitcount then add those devices in 72, consider remaining devices BG of the CC other than Z1 and 72 in Z3. END — Hitcount is unspecified function which returns positive or negative, where return positive means to add device in subcluster and negative means do not add device in subcluster. It may depend on requirement of the application, environment, topology or any other local or global attributes. — Owner may use upper layer protocol to communicate information of subdiistsr and should create different reservations for different subcluster. The following subsections describe the mechanism to update the membership of the subclusters for from the targets of the CC: — The above algorithm should be used periodically depending on time or number of superframes to update the membership of the subcluster. — If there are changes in membership of the subcluster then owner may use upper layer protocol to communicate new subcluster information to create appropriate reservations. The following subsections describe the example to find the subclusters for from the targets of the CC using example illustrated Figure 3: — Devices in CC's BG are {1,2,3,4,5,6,7}. — Device in CC's BG with highest number of devices in its BG are; multiple device of that kind and those are {4,5,6}. — Device with highest number of devices in its BG from {4,5,6} is {5}. — {5} is part of Z1. So, Z1 = {5}. — BG of first device in Z1 is part of Z1, so, Z1 = {4,5,6,7}. — EBG of first device in Z1 which is also BG of CC is {3}. — Assume, Hitcount return value for {3} is negative. — So, {3} is not part of Z1. — devices from EBG of the first device of Z1, which is not part of Z1, which has highest number of devices in its BG other than Z1 and CC. That is {3}. — So, {3} as part of Z2. So, Z2 = {3}. — BG of first device of Z2 other than Z1 and CC is part of Z2. So, Z2 = {3} — EBG of first device in Z2 other than Z1. There are no such devices. — All remaining devices are part of Z3. So, Z3 = {1,2} - Finally, Z1 = {4,5,6,7}, Z2 = {3}, Z3 = {1,2j 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. V GLOSSARY OF TERMS AND DEFINITONS THEREOF BG: Beacon Group BP: Beacon Period BPOIE: Beacon Period Occupancy Information Element BPST: Beacon Period Start Time CC: Cluster Coordinator DEVID: Device Identifier DRP: Distributed Reservation Protocol EBG: Extended Beacon Group IE: Information Element IEEE: Institute of Electrical and Electronics Engineers MAC: Medium Access Control MAS: Medium Access Slot MBOA: Muiti Band OFDM Alliance OFDM: Orthogonal Frequency Division Multiplexing UWB: Ultra Wide Band WPAN: Wireless Personal Area Network WUSB: Wireless Universal Serial Bus WE CLAIM 1. A method for subclustering of the network for decentralized wireless network wherein a reservation owner creates two or three private or hard reservation with subclusters of devices which acts as subset of targets depending on network topology thereby, reusing same time of the reservations by two hop neighbors and achieving spatial reuse. 2. A method as claimed in claim 1 wherein there exist a Beacon Group (BG) of the device which is the set of all devices in one hop neighborhood of the - device where the device always receives beacon from each devices in its BG and each device in the device's BG is able to receive beacon from the device. 3. A method as claimed in claim 1 wherein there exists an extended beacon group (EBG) which is a set of all devices in two hop neighborhood of the device except the devices in beacon group of the device. 4. A method as claimed in claim 1 wherein there exists a cluster coordinator (CC) which is the owner of the reservation. 5. A method as claimed in claim 1 wherein there exist subclusters which are subsets of devices which are from the targets of the reservation made by cluster coordinator (CC). 6. A method for subclustering of the network for decentralized wireless network wherein Z1, 72 and Z3 are set of devices in subclusters 1, subcluster 2 and subcluster 3 respectively and END is defined as end of the procedure to find subcluster. 7. A method as claimed in claim 6 wherein if all devices in CC's BG are in range of each other then no different subclusters are possible and Z1 is BG of CC, Z2 and Z3 does not have any devices. 8. A method as afr^ed in claim 7 wherein if a device exists in CC's BG, which has highest number of uic'ses in its BG, which are common with CC's BG, or else if there exists at least one device, which has highest number of devices in its BG, which is one of the devices from earlier subset then found device is considered to be first device in Z1. 9. A method as claimed in claim 8 wherein devices in BG of the first device in Z1, other than CC, are considered to be part of Z1. 10. A method as claimed in claim 9 wherein if there are no devices in EBG of the first device in Z1, then remaining devices are considers other than Z1 and CC in BG of CC as Z2. 11. A method as claimed in claim 10 wherein devices with positive hitcount is considered in EBG of first device in Z1, as part of Z1. * 12. A method as claimed in claim 11 wherein if all devices in EBG of the first device in Z1 have positive hitcount, then remaining devices other than Z1 and CC in BG of CC as Z2 are considered. 13. A method as claimed in claim 12 wherein one of the devices from EBG of the first device of Z1, is considered which is not part of Z1, which has highest number of devices in its BG other than Z1 and CC, as part of Z2 where this is the first device of Z2. 14. A method as claimed in claim 13 wherein devices in BG of the first device of Z2, is consider other than Z1 and other than CC, as part of Z2. 15. A method as claimed in claim 14 wherein if there are no devices present in EBG of the first device in Z2, other than Z1, remaining devices BG of the CC is considered other than Z1 and Z2 in Z3. 16. A method as claimed in claim 15 wherein if there are devices present in EBQ of the first device in Z2 with positive hitcount, then those devices in Z2 are added and remaining devices BG of the CC is considered other than Z1 and 72 in Z3. 17. A method as claimed in claim 16 wherein hitcount is an unspecified function which returns positive or negative, where return positive is an indication to add device in subcluster and negative is an indication for not adding device in subcluster where the hitcount depends on requirement of the application, environment, topology or any other local or global attributes. 18. A method as claimed in claim 17 wherein owner use upper layer protocol to communicate information of subcluster and create different reservations for different subcluster. 19. A method as claimed in claim 1 wherein to update the membership of the subclusters for from the targets of the CC the said method should be used periodically depending on time or number of superframes to update the membership of the subcluster. 20. A method as claimed in claim 1 wherein if there are changes in membership of the subcluster then owner use upper layer protocol to communicate new subcluster information to create appropriate reservations. 21. A system for subclustering of the network for decentralized wireless network wherein a reservation owner creates two or three private or hard reservation with subclusters of devices which acts as subset of targets depending on network topology thereby, reusing same time of the reservations by two hop neighbors and achieving spatial reuse. 22. A method for subclustering of the network for decentralized wireless network substantially described particularly with reiv-ence to the accompanying drawings. c 23. A system for subclustering of the network for decentralized wireless network substantially described particularly with reference to the accompanying drawings.

Documents:

1105-CHE-2005 AMENDED PAGES OF SPECIFICATION 17-10-2013.pdf

1105-CHE-2005 AMENDED CLAIMS 17-10-2013.pdf

1105-CHE-2005 EXAMINATION REPORT REPLY RECEIVED 17-10-2013.pdf

1105-CHE-2005 FORM-1 17-10-2013.pdf

1105-CHE-2005 OTHER PATENT DOCUMENT 17-10-2013.pdf

1105-CHE-2005 POWER OF ATTORNEY 17-10-2013.pdf

1105-CHE-2005 FORM-13 19-06-2006.pdf

1105-CHE-2005 ABSTRACT.pdf

1105-CHE-2005 CLAIMS.pdf

1105-CHE-2005 CORRESPONDENCE OTHERS.pdf

1105-CHE-2005 DESCRIPTION (COMPLETE).pdf

1105-CHE-2005 DRAWINGS.pdf

1105-CHE-2005 FORM 1.pdf

1105-CHE-2005 FORM 13.pdf

1105-CHE-2005 FORM 18.pdf

1105-CHE-2005 FORM 6.pdf