Title of Invention

SYSTEM AND METHOD FOR TIME SYNCHRONIZATION IN WIRELESS PERSONAL AREA NETWORKS

Abstract

This invention explains a method and system for time synchronization in wireless personal area networks comprising the steps of: listening to two beacon periods by each device in the network where one is the BP in which device beacons and another is the first beacon period preceding the beacon period of the device, in which the device listens to beacon from at least one device; synchronizing to the device with slowest clock in its BG when the device listens to the beacons from the devices in its BG; and synchronizing with another device having a slower clock than its own clock, if the device hears a beacon from such a device while listening to the first BP preceding the BP of its own; wherein there is also a provision for the device to adjust to the faster clock in exceptional cases where the particular network topology cannot ensure time synchronization by normal rules of the invention.

Full Text

FIELD OF TECHNOLOGY This invention relates to the field of wireless mobile ad-hoc 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 are networks which does not have any central coordinator. More particularly, this invention relates to effective mechanisms for the devices to achieve time synchronization. More particularly, it provides mechanisms for time synchronization between devices when all devices do not listen to each other all the time. 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 devices in the network are time synchronized with each other 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 all the devices. All other devices seek help of the centralized coordinator for medium access operations like joining the network, reserving channel time, etc. All devices synchronize with the coordinator in centralized approach. 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 currently employ a centralized medium access control mechanisms, some distributed medium access control mechanisms are under discussions for WPANs as they offer flexibility, e.g. in terms of mobility of devices. Figure 1 shows 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 each of the devices is a 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, time synchronization etc. This is a Distributed WPAN system which is formed in an ad-hoc fashion. Each device periodically broadcasts the information about its neighbors, its clock information 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. Time slots are also referred to as Medium Access Slots in the literature. 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 may be referred as beacon slots and the slots in which data is sent may be referred as called data slots. The length of a beacon slot may be less than the length of a data slot. 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.org) 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 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 beacon slots, 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). Beacon Group (BG) of a device is referred to as the set of devices, whose beacons are received by the device in a beacon period in which, the device beacons. 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 periods may coexist. MASs are numbered relative to this starting time. The devices shall transform the numbering of MASs of other beaconing groups into the time reference of their main beaconing group. A device can be part of several beaconing groups but has to select one beaconing group as its main beaconing group. Cluster of a device is the set of devices those are in radio range of the device. Devices in cluster may not be in beacon group of the device, because some devices can be beaconing in some other beacon period. Device includes time stamp in its beacons that is used for time synchronization of the devices. A device listens to beacons from the devices in its beacon group in each superframe. Device synchronizes to the device, which has slowest clock in its beacon group by listening to beacon from the devices in its beacon group. The devices go to power save state, to save battery power, whenever possible. Specific power save mechanisms may be provided in the system. During power save, a device need not listen to the entire superframe. The present state of art in this field, as discussed in MBOA MAC vO.5, has certain limitations, namely, the time synchronization mechanism does not guarantee the synchronization and it can lead to overlap of data or beacon periods. Currently the medium access control mechanism, as defined in MBOA MAC vO.5 system, suffers from the following limitations: 1. Current mechanism does not provide time synchronization among the devices which beacons in different beacon periods. In other words, all devices in a beacon group are time synchronized but the devices in the cluster are not time synchronized. 2. Because two or more beacon periods in the superframe are individually time synchronized but not to each other, there is a possibility that MAS corresponding to one of the beacon period may overlap with MAS corresponding to another beacon period. This can result in overlapping of data to another data or beacon. 3. Device is allowed to send a beacon in more than one beacon period in the current art, but it is unclear that device should synchronize to which beacon group in such scenario. Also, there is no mechanism for time synchronization across multiple beacon periods. SUMMARY OF THE INVENTION The primary object of the invention is therefore to provide a system and method for time synchronization amongst devices in 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 dedicated central coordinator. More particularly, it is another object of the invention to provide a mechanism for time synchronization where a device does not need to listen to the entire superframe. It is another object of the invention to provide methods where the devices in the network get synchronized without compromising on power saving aspects. The present invention relates to a system that incorporates a distributed medium access control in the Wireless Personal Area Networks based on mobile ad-hoc networks. The invention relates to system and method which allow devices in the network to time synchronize with each other without listening to entire superframe. The system for the invention comprises of a new medium access control mechanism with new time synchronization method. The present invention comprises of system and method which would solve the problems associated with current art, in the following manner: 1 The device listens to two beacon periods (BP): (i) the BP in which the device beacons; and (ii) the first BP preceding the BP of the device in which the device can listen to beacon from at least one device. 2. When the device listens to the beacons from the devices in its BG corresponding to case 1(i) above, i.e. device listens to the BP, in which it beacons, it time synchronizes to the device with slowest clock in its BG. For the sake of explanation, this may be referred to as Intra BP Synchronization. 3. When the device listens to the beacons from devices in the BP corresponding to case 1(ii) above, i.e. device listens to the first BP preceding the BP of its own. If it hears a beacon from another device with slower clock than its own clock, then device time synchronizes with that another device. 4. When device listens to the first BP preceding the BP of its own, and if all devices in that BP have faster clocks, then device ignores that and continue with its normal activity. Since all the devices need to implement the time synchronization, the slower device adjusts its clock to faster device for time synchronization. Accordingly, the invention provides time synchronization amongst the devices beaconing in different beacon periods. More particularly, the invention provides method for time synchronization amongst the devices, without the devices having to listen to entire superframe and without compromising power saving schemes. Accordingly, the present invention explains a method for time synchronization in wireless personal area networks comprising the steps of: (a) listening to two beacon periods by each device in the network where one is the BP in which device beacons and another is the first beacon period preceding the beacon period of the device, in which the device listen to beacon from at least one device; (b) synchronizing to the device with slowest clock in its BG when the device listens to the beacons from the devices in its BG ; and (c) synchronizing with that another device if the device hears a beacon from another device with slower clock than its own clock when the device listens to the first BP preceding the BP of its own. wherein when the device listens to the first BP preceding the BP of its own, and if all devices in that BP have faster clocks, then device ignores and continue with its normal activity. The preceding beacon period is the beacon period that precedes in reference to time of beaconing. If the preceding BP does not exist for a device, then the said device listens to only its own BP. If the device cannot hear any beacon from beacon period other than its own beacon period the said device listen to one beacon period only. The device synchronizes to slowest clock in its BG when each device listens to all other beacons in its BG. If any of the devices in the BP other than its own BP has slower clock than the device's own clock, then device synchronize to the slower clock. When slower devices are not heard by any faster devices the said slower device is adapted to adjust to faster device. If all device clocks in the BP other than its own BP are faster than the device's own clock, then the device neglects it, after which it adjust to the fastest clock in BP other than its own BP. Accordingly, the present invention further explains a system for time synchronization in wireless personal area networks comprising: (a) means for listening to two beacon periods by each device in the network where one is the BP in which device beacons and another is the first beacon period preceding the beacon period of the device, in which the device listen to beacon from at least one device; (b) means for synchronizing to the device with slowest clock in its BG when the device listens to the beacons from the devices in its BG ; and (c) means for synchronizing with that another device if the device hears a beacon from another device with slower clock than its own clock when the device listens to the first BP preceding the BP of its own, wherein when the device listens to the first BP preceding the BP of its own, and if all devices in that BP have faster clocks, then device ignores and continue with its normal activity. The other objects, features and advantages 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. It also depicts range of all devices; Figure 2 illustrate the superframe structure in the current art, which includes MAS and beacon periods; Figure 3 illustrates the network topology and devices with different clock speed. Device A, B, C beacon in one BP and C, E, F beacon in another BP. Device B is the device with slowest clock in A, B and C, device with slowest clock from D, E and F is faster than clock of B; Figure 4 shows how unsynchronized BPs can result into drifting of MAS boundary which in turn causes overlap of data and beacon periods; Figure 5 shows the illustrative network topology with 8 devices and 3 BPs in a superframe; and Figure 6 shows superframe structures and dependency of time synchronization on network topology. DETAILED DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1 illustrates the WPAN as a decentralized and distributed ad-hoc network system and range of all devices. The black dots represent devices and the circles are the effective ranges of the respective devices. Note the absence of any centralized infrastructure. In such an ad hoc network, each device cooperates to provide various networking and management functions like device discovery, channel reservation, etc. Figure 2 illustrate the superframe structure in current art, which includes MAS and beacon periods. Beaconing slots are a group of slots which are reserved for sending beacon by various devices. When the number of slots available for beaconing is less than the number of devices, another group of slots may be designated as a beaconing period. Hence in such a scenario there may be multiple beaconing periods in the same superframe which may be assumed to be multiple time shifted superimpositions of the structure shown in Figure 2. Except for the beaconing slots, the rest of the MASs may be reserved by devices for their communication. The different beaconing groups need to be time synchronized with each other so that they do not interfere with the other MASs as reserved by devices in various beacon periods. Figure 3 illustrates the network topology and devices with different clock speed. Device A, B, C beacon in one BP and D, E, F beacon in another BP. Device B is the device with slowest clock in A, B and C, device with slowest clock from D, E and F is faster than clock of B. Hence to achieve overall time synchronization in the whole superframe, all the devices should eventually synchronize their clocks to the slowest time i.e. clock of Device B, Synchronization of A, C to B is achieved as Intra-BP Synchronization method and synchronization of D, E, F to B is achieved by Inter-BP Synchronization method. Figure 4 shows how unsynchronized BPs can result into drifting of MAS boundary which in turn causes overlap of data and beacon periods. This occurs because the data period shown in the Figure will have different start and end times in reference to the clocks of the devices in different beacon groups if these beacon groups are not synchronized to each other. If BP2 has slower clock than BP1 then it will migrate into the data period causing shortening of the usable data period for BP1. Figure 5 shows the illustrative network topology with 8 devices and 3 BPs in a superframe. Figure 6 shows superframe structures and dependency of time synchronization on network topology. It shows the working of the invention as to how the devices in different beaconing periods get time synchronized to each other over a period of time. Devices A, E and H have the slowest clock in their respective beacon periods. In addition, the slowest clock in the whole network is of Device A. As illustrated, first the devices synchronize to the clock of the other devices in their beacon group, thereby achieving Intra-BP Synchronization. Then the devices try to synchronize to clock of the devices they listen in the preceding BP. Over a period of superframes all the devices get synchronized to slowest clock in the network. Once all the devices are synchronized, the number of superframes required to achieve total synchronization is dependent on the network topology. DETAILED DESCRIPTION OF THE INVENTION A preferred embodiment of the present invention will now be explained with reference to the accompanying drawings. It should be understood however that the disclosed embodiment is 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 a distributed and 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 allow devices to get time synchronized within the network without having to listen to entire superframe. Accordingly, the invention provides method where the devices in the network get synchronized without compromising on power saving aspects. This helps in avoiding drift of MAS boundary as a result of imperfect time synchronization. The subsequent subsections describe the operation of the invention: First we define the rules that each of the devices in the network is required to adhere to. Later, we describe the proposed time synchronization procedure with illustrative example. 1. Beacon period listen rules: This section lists the rules that each device in the network need to follow. 1.1 Each device shall listen to two BPs. 1) One is the BP in which device beacons 2) Another one is the first BP preceding the BP of the device, in which the device can listen to beacon from at least one device. Some time, device cannot hear any beacon from beacon period other than its own beacon period because of network topology, in such case it shall listen to one beacon period only. Here, "preceding BP" means BP that precedes in reference to time of own beaconing. As an example, suppose if devices A and B are neighbors (in radio range of each other), device A beacons in BP1 and device B beacons in BP2. If device A in BP1 beacons early in time than device B in BP2, then BP1 precedes BP2. As a result of the above rules for listening beacon period, different devices in the same BP listens to different preceding BP. Exact situation of which device listens to which BP, depends upon the network topology. Figure 5 illustrates the situation of listening to different BPs with an example. Figure 5 shows the network topology with 8 devices and 3 BPs in a superframe. Following lists the devices and different BPs, that devices listen. Device A: Listens to SFn/BP1 only Device B: Listens to SFn/BP1 and SFn-1/BP2 (beacons of D&E) Device C: Listens to SFn/BP1 only Device D: Listens to SFn/BP2 and SFn/BP1 (beacon of B) Device E: Listens to SFn/BP2 and SFn/BP1 (beacon of B) Device F: Listens to SFn/BP3 and SFn/BP2 (beacon of E) Device G: Listens to SFn/BP3 and SFn/BP2 (beacon of E) Device H: Listens to SFn/BP3 and SFn/BP2 (beacon of E) Here abbreviation SFn means, the superframe numbered 'n'. That means that SFn-1 is the superframe numbered 'n-1' and hence is the preceding superframe to SFn. 2. Time Synchronization Procedure: This section describes the Time Synchronization Procedure, which uses rules for listening beacon periods as described in section 1. Invention achieves time synchronization by "Intra BP Synchronization" and "Inter BP Synchronization". 2.1 Intra BP Synchronization: 1. Each device listens to all other beacons in its BG in BP, in other words device listens to whole BP in which it beacons. 2. Device synchronizes to slowest clock in its BG. This is only specified synchronization scheme which is specified in current art, we refer this as "Intra BP Synchronization", in the present invention, for the sake of explanation. 2.2 Inter BP Synchronization: 1. Device listens to network as per Section 1 (Beacon Pehod Listen Rules). 2. Inter BP Synchronization is synchronization of the device across the devices beaconing in the BP other than its own BP, which it listens. 3. If any of the devices in the second BP (BP other than its own BP) has slower clock than the device's own clock, then device synchronize to that slower clock. 4. Since different devices within the same BP may listen to different second BP, hence all the BPs can achieve time synchronization to the slowest global clock. However, in some very specific cases, it is possible that, because of topology of the network, some of the slower devices are never heard by any other faster devices. In this case, as mentioned below, slower device would be required to adjust to faster device (as detailed in step 5). This situation for synchronization and its dependency on network topology is depicted in Figure 6. 5. As in step 4 above, If all devices' clocks in the second BP are faster than the device's own clock, then the device neglects it for mMaxNonSynch times, after which it adjust to the fastest clock in second BP. 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, 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 manner 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 BG: Beacon Group BP: Beacon Period BPST: Beacon Period Start Time 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 SF: Superframe UWB: Ultra Wide Band WPAN: Wireless Personal Area Network WE CLAIM 1. A method for time synchronization in wireless personal area networks comprising the steps of: (a) listening to two beacon periods by each device in the network where one is the BP in which device beacons and another is the first beacon period preceding the beacon period of the device, in which the device listens to beacon from at least one device; (b) synchronizing to the device with slowest clock in its BG when the device listens to the beacons from the devices in its BG; and (c) synchronizing with another device having a slower clock, if the device hears a beacon from such a device when it listens to the first BP preceding the BP of its own, wherein when the device listens to the first BP preceding the BP of its own, and if all devices in that BP have faster clocks, then device ignores and continue with its normal activity. 2. A method as claimed in claim 1 wherein the said preceding beacon period is the beacon period that precedes in reference to time of its own beaconing. 3. A method as claimed in claim 1 wherein if the preceding BP does not exist for a device, then the said device listens to only its own BP. 4. A method as claimed in claim 1 wherein if the device cannot hear any beacon from beacon period other than its own beacon period the said device listen to one beacon period only. 5. A method as claimed in claim 1 wherein the device synchronizes to slowest clock in its BG. 6. A method as claimed in claim 1 wherein if any of the devices in the BP other than its own BP has slower clock than the device's own clock, then device synchronize to the slower clock. 7. A method as claimed in claim 1 wherein when slower devices are not heard by any faster devices the said slower device is adapted to adjust to faster device after a certain number of superframes. 8. A method as claimed in claim 1 wherein if all device clocks in the BP other than its own BP are faster than the device's own clock, then the device neglects it for a certain number of superframes, after which it adjust to the fastest clock in BP other than its own BP. 9. A system for time synchronization in wireless personal area networks comprising: (a) means for listening to two beacon periods by each device in the network where one is the BP in which device beacons and another is the first beacon period preceding the beacon period of the device, in which the device listen to beacon from at least one device; (b) means for synchronizing to the device with slowest clock in its BG when the device listens to the beacons from the devices in its BG ; and (c) means for synchronizing with another device having slower clock than its own clock, if the device hears a beacon from such a device in the first BP preceding the BP of its own wherein when the device listens to the first BP preceding the BP of its own, and if all devices in that BP have faster clocks, then device ignores and continue with its normal activity. 10. A method for time synchronization in wireless personal area networks as substantially herein described particularly with reference to the drawings. 11. A system for time synchronization in wireless personal area networks substantially as herein described particularly with reference to the drawings. Dated this 14*^ day of June 2005

Documents:

0550-che-2004-abstract.pdf

0550-che-2004-claims.pdf

0550-che-2004-correspondnece-others.pdf

0550-che-2004-correspondnece-po.pdf

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

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

0550-che-2004-drawings.pdf

0550-che-2004-form 1.pdf

0550-che-2004-form 13.pdf

0550-che-2004-form 5.pdf

550-CHE-2004 CORRESPONDENCE OTHERS 25-05-2012.pdf

550-CHE-2004 POWER OF ATTORNEY 25-05-2012.pdf

550-CHE-2004 AMENDED CLAIMS 29-03-2012.pdf

550-CHE-2004 AMENDED CLAIMS 16-05-2012.pdf

550-CHE-2004 AMENDED PAGES OF SPECIFICATION 29-03-2012.pdf

550-CHE-2004 AMENDED PAGES OF SPECIFICATION 16-05-2012.pdf

550-CHE-2004 CORRESPONDENCE OTHERS 16-05-2012.pdf

550-CHE-2004 CORRESPONDENCE OTHERS 29-03-2012.pdf

550-CHE-2004 FORM-1 16-05-2012.pdf

550-CHE-2004 POWER OF ATTORNEY 29-03-2012.pdf

550-CHE-2004 POWER OF ATTORNEY 16-05-2012.pdf