Indian Patents. 211879:SYSTEM AND METHOD FOR SPATIAL REUSE IN WIRELESS PERSONAL AREA NETWORKS

Title of Invention	SYSTEM AND METHOD FOR SPATIAL REUSE IN WIRELESS PERSONAL AREA NETWORKS
Abstract	The invention relates to a system and method which allows multiple pair of devices to communicate simultaneously given the condition that they are sufficiently separated in spatial domain so as not to interfere with each other. The system for the invention comprises of a new mechanism within the existing medium access control involving a new algorithm for the devices to access the channel.

Full Text	FIELD OF THE INVENTION This invention relates to the field of wireless mobile ad-hoc networks. Further, this invention relates to spatial reuse for wireless personal area networks that are based on wireless mobile ad-hoc networks. Particularly, this invention relates to effective mechanisms of allowing multiple pair of devices to communicate with each other simultaneously, thereby shanng the same spatial region for improved throughput. More particularly, this invention encompasses a system and method for spatial reuse 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. at a distance of approximately 10 meters. The IEEE (http://www.ieee.org) 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. Medium Access Control mechanisms to deal with such high data rates are currently being discussed in IEEE draft P802.15.3/D17. The medium access control mechanisms broadly include how a device may join the network, how it can transfer data at the required rate to another device, how the medium is best used etc. Figure 1 show the IEEE-802.15.3 based wireless personal area network. It involves a network referred as piconet, in which a device may act as coordinator (referred as piconet coordinator or PNC in literature). The PNC performs the functions of allowing a device (referred as DEV) to join, allocating it a channel (time slot) to transmit to another device, synchronization mechanisms etc. This is a centralized WPAN system which is formed in an ad-hoc fashion. The PNC periodically broadcasts the information to all the associated devices in the beacon. Figure 2 illustrates the superframe structure. Superframe is channel distribution specified by the PNC among the DEVs in piconet. It is informed to DEVs through beacon frame, which is being broadcasted by PNC. Superframe is composed of 3 parts: 1. Beacon: It is used to set the timing allocations and to communicate management Information for the piconet. All the associated devices listen to this beacon. 2. Contention access period (CAP): It is used to communicate commands from the DEV to PNC or vice versa. It may also be used for asynchronous data if it is present in the superframe. The length of the CAP is determined by the PNC and communicated to the DEVs in the piconet via the beacon. The CAP uses CSMA/CA protocol for the medium access. 3. Channel time allocation period (CTAP): It consists of channel time allocations (CTAs), including management CTAs (MCTAs). CTAs are used for commands, isochronous streams and asynchronous data connections. A PNC may choose to use MCTAs instead of the CAP for sending command frames, unless otherwise restricted by the physical layer (PHY). An open MCTA is one where the SrcID is the BcstID; Any DEV that is associated in the piconet may attempt to send a command frame to the PNC in an open MCTA. An MCTA with the UnassocID as the SrcID is an association MCTA. Any DEV not currently associated in the piconet may attempt to send an Association Request command to the PNC in an association MCTA. The CTAP, in contrast to CAP, uses a standard TDMA protocol where the devices (DEVs) have specified time windows which are called the CTAs. CTAs are either assigned to a specific source/destination pair and use TDMA for access or they are shared CTAs that are accessed using the slotted aloha protocol. The invention also considers the Indian patent application bearing application No. 221/CHE/2004 titled "SYSTEM AND METHOD FOR MEDIUM ACCESS CONTROL IN WIRELESS MOBILE AD-HOC NETWORKS" as part of current art. A device can find out the presence of another device, and also whether it is in range of another device, using mechanisms provided in the mentioned patent application. Device Access Period (DAP), as mentioned in the referred patent application, is used by all the associated DEVs in piconet to send their respective heart beat frames. By listening to the heart beat frames as contained in DAP, it is possible for a first associated device to know exactly whether a second associated device is in range (reachable) or not, depending upon whether the first associated device was able to listen to the heart beat frame sent by the second associated device in the DAP. LIMITATIONS The present state of art in this field, as discussed in IEEE 802.15.3 (http://www.ieee.orq). has certain limitations, namely, there is no mechanism where the PNC can allocate the same CTA to more than one pair of communicating devices given that the pairs are suitable away from each other to interfere with each other's communication. In addition the PNC also does not have the information about the positions of the devices and is unable to optimize this allocation of CTAs. Also, the dependent piconets share the channel time with their parent piconet thereby limiting the amount of superframe time available to devices. Consequently, in high load cases and for dependent piconets the amount of channel time available may be less than as required. Currently in the medium access control mechanism as defined in IEEE-802.15.3 system; the following limitations arise due to the nature of channel time allocation via CTA: 1. Only a limited number of CTAs can be allocated in a superframe since the size of the superframe is maximally bound. 2. Because of the above condition in dense piconets with high network load, PNC will have to choose between more CTAs with less time per CTA or less CTAs with more time. This affects the QoS possible. 3. A pair of devices which is not in range of another pair can communicate at the same time when the other pair is communicating without interfering. This possible optimization, known as Spatial Reuse is not addressed in the current 802.15.3 draft. 4. The dependent piconets have to share the channel time with the parent piconet in the same superframe. Hence very less channel time is available to the devices in the lower hierarchy of the dependent piconet structure in the current art. 5. Under utilization of the channel time for dependent piconets since their superframes have very less usable channel time and the rest of the superframe is reserved region. OBJECTS OF THE INVENTION The primary object of the invention is to provide a system and method for spatial reuse for the UWB wireless personal area networks, which are based on wireless ad-hoc networks, in a centralized network topology where one of the devices undertakes the role of a coordinator. In other words, the invention provides a scheme for allowing various pairs of devices to communicate within the same CTA period given the condition that they are not in range of each other and hence will not be a source of potential interference to each other. It is another object of the invention to provide a method for increasing the overall throughput of the piconet and for improving the QoS via the provision of spatial reuse. It is another object of the invention to mitigate interference between piconets in the same spatial region and even try to detect the presence of other piconets in the neighborhood. It is a further object of the invention to provide a mechanism for improved channel utilization in the UWB WPAN. SUMMARY OF THE INVENTION The present invention relates to a system that allows spatial reuse in channel, access in the Wireless Personal Area Networks based on mobile ad-hoc networks. The invention relates to system and method which allow multiple pair of devices to communicate simultaneously given the condition that they are sufficiently separated in spatial domain so as not to interfere with each other. The system for the invention comprises a new mechanism within the existing medium access control involving a new algorithm for the devices to access the channel. Accordingly, this invention explains a system for spatial reuse in wireless personal area network comprising: a. a piconet coordinator having information of previously allocated CTAs and the positions of the devices to allocate multiple pair of devices to the same CTA where the extra CTAs allocated with in the CTA period constitute a VCTA; b. multiple pair of devices communicating within the same CTA period without interfering with each other if the devices having been allocated the VCTA judge that they are out of range of the CTA devices ; and where the first priority is given to the devices having the CTA to communicate and accessing the channel within the CTA is in three stages - Scan Period, CTS Period, Data Period. The present invention comprises a system and method which would solve the limitations associated with current art, in the following manner: 1 The PNC uses the information of previously allocated CTAs and the positions of the devices (if available) to allocate multiple pair of devices to the same CTA. The extra CTAs allocated with in the CTA period are called the Virtual CTAs (VCTA). 2. First priority is given to the devices having the CTA to communicate. If the devices having been allocated the VCTA judge that they are out of range of the CTA devices then they too can communicate. Hence multiple pair of devices can communicate within the same CTA period without interfering with each other. 3. The device pair which is allocated the CTA has the first priority to communicate. Devices which have been allocated the VCTA communicate only if they find the channel to be free or in other words, they are outside the range of other higher priority device pairs that are communicating within the same CTA. The manner in which this is accomplished is a part of the method of the proposed invention. 4. The proposed superframe structure maintains the same CTA structure but instead the access of the channel within the CTA is divided into three stages - Scan Period, CTS Period, Data Period. This is illustrated in Figure 3. 5. In the Scan Period, the various pairs of devices allocated to the CTA, scan the channel for external interference which signifies some communication in progress. In this manner devices can decide if they will interfere with each other or not. 6. In the Clear to Send (CTS) Period, the destination device is required to send a CTS packet to the source to signify that it is free to receive the data from the source device. This implicitly signals that the destination device has found the channel to be suitably free to indulge in data communication with the source. 7. The actual data communication takes place in the Data period. 8. The CTA period will not be used by the devices to communicate if some interference is detected during the Scan Period or if the CTS is not send by the destination or if the CTS is not received by the source. Accordingly, the present invention comprises a system for spatial reuse in wireless personal area network, wherein the multiple pair of devices are sufficiently separated in spatial domain so as not to interfere with each other and which utilizes a superframe structure where the CTA period is divided into three stages - Scan Period, CTS Period, Data Period. Accordingly, the present invention further comprises a method for spatial reuse in wireless personal area network with better channel time allocation using a channel access mechanism within the CTA, comprising the steps of: (a) dividing the CTA period into Scan Period which is the time at the start of the CTA wherein the various devices assigned to communicate within this CTA listen to the channel and find its status whether it is free or busy; (b) dividing the CTA period into Clear to Send Period during which the destination devices send the CTS packet to the source devices to signify that the channel is free for communication for destination device; and (c) dividing the CTA period into Data Period for actual communication between the pairs of devices and all the sources who received CTS can start communication with their destinations. The other objects, features and advantages of the present invention will be apparent from the accompanying drawings and the detailed description as follows. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1 illustrates the piconet in WPAN ad-hoc network system. The piconet range, different piconet elements like DEV and PNC, frames being transferred in piconet like beacon and data transfer between DEV to DEV, PNC to DEV and DEV to PNC are shown; Figure 2 illustrates the superframe structure in current art, which includes the beacon. CAP, MCTA and CTA; Figure 3 illustrates the superframe structure with the CTA structure of the present invention. Figure 4 illustrates the Channel Time Allocation Information element along with the Channel Time Allocation Block in the current art. Figure 5 illustrates the proposed VCTA block. Figure 6 illustrates the state diagram for communication within the CTA for the source devices. Figure 7 illustrates the state diagram for communication within the CTA for the destination devices. Figure 8 illustrates the scenario of Intra-Piconet spatial reuse. Figure 9 illustrates the scenario of Inter-Piconet spatial reuse. Figure 10 illustrates superframe structure for parent and dependent piconet. Figure 11 illustrates superframe structure for inter piconet spatial reuse showing the allocation of CTA and VCTA by the PNCs. DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a system that allows improved channel time utilization in the Wireless Personal Area Networks based on mobile ad-hoc networks. Implementation of the mechanisms of the present invention results in better throughput and QoS compared to the current art. The invention relates to system and method which allow spatial reuse of channel time by pair of devices outside the range of each other. The system for the invention comprises of a new channel access mechanism within the CTAs. The invention also proposes Virtual CTAs. Accordingly, the invention provides a method for better channel time allocation and utilization in a piconet than present in current art. Accordingly, the invention provides a method to improve the throughput and QoS in the piconet by providing spatial reuse of the channel. Accordingly, the invention also provides a method to multiple pairs of devices to communicate simultaneously given that they do not interfere with each other. Accordingly, the invention also provides a method to mitigate the interference between simultaneously operating piconets. The subsequent subsections describe the individual entities to effect the invention. 1. Figure 3 illustrates the invented channel access mechanism within the CTA. - Scan Period is the time in the starting of the CTA wherein the various devices assigned to communicate within this CTA listen to the channel and find if it's free or busy. - Clear to Send Period is for the destination devices to send the CTS packet to the source devices to signify that the channel is free for communication. - Data Period is for actual communication between the pairs of devices. All the sources which received CTS can start communication with their destinations. 2. The VCTA and the CTA differ in only the length of the Scan Period which is least for the CTA. Hence CTA can be visualized as a VCTA with zero Scan Period. 3. All the Channel Time Allocations can be described in terms of VCTAs itself. The CTA is still maintained for backward compatibility. Hence CTA can be visualized as a VCTA with zero Scan Period. 4. In the present invention, a new Channel Time Allocation Block for the Channel Tinne Allocation Information Element in the beacon frame is being proposed for adding VCTAs. It is illustrated in Figure 5. The invented block is called the VCTA Block and differs from that in the current art in the following way: - The invented block is called the VCTA block. - VCTA Block describes the allotment of a VCTA in the CTAP, like the CTA Block in the current art describes the allotment of a CTA in the CTAP. - The VCTA Scan Duration field details the length of the scan period for a particular VCTA. - The location of VCTA is given by the VCTA Location field. " The length of VCTA is given by the VCTA Duration field. - The VCTA block does not includes the information of the priority of the VCTA but multiple VCTAs can be allocated with increasing priorities. The lower the duration of the scan period for the VCTA, the higher would be its priority. Scan Period length = duration = (1/Priority) * (Minimum Length of Scan Period) + Length of CTS Period Different VCTAs have different length of the Scan period. Hence the Channel Time Allocations are prioritized with the CTA having the highest priority due to its smallest duration of Scan Period. VCTAs cannot guarantee channel time like CTA does. In the presence of a suitable mechanism to allocate the VCTAs properly, so that the different pairs of devices chosen for the VCTAs within the same channel time are out of interfering range of each other, the VCTAs can be used to maximize spatial reuse. The subsequent subsections describe the operation of the invention: I. CTA Allocations As in the current art, the source devices send CTA Request Command to the PNC to request a CTA allocation with the destination. In case the source has knowledge of its neighbors then it includes that information in the CTA request. From the various requests received the PNC can conclude whether the superframe has enough time to allocate all the requests as CTAs else the PNC would have to allocate some of the requests as VCTAs. It should be noted that without a mechanism to find the neighbors of a device, it is not possible for the PNC to allocate the VCTAs in the best possible manner to minimize the interference. The PNC can also use the information from the allotments in the previous superframes along with the knowledge if the VCTA was usable by the pair to shuffle around the allotments to find the appropriate locations of the various VCTAs and CTAs in the CTAP. The CTAs and VCTAs are allocated by the PNC and are advertised in the CTAIE in the beacon. The CTA is advertised by the CTA Block and the VCTA by the VCTA Block. Devices that receive the beacon for the PNC get the information of the various allotments in the superframe. 2. CTA Utilization Once allocated, a CTA or a VCTA, the source and destination have to cycle through a 3 step process to communicate. In the first step the devices scan the channel, in the second the destination sends CTS to the receiver and in the third, the data communication takes place. The state diagram of communication for the source devices is shown in figure 6 and for destination devices is shown in figure 7. The state machine is further described as follows: 1 Scan Period: Both the source and destination devices scan the channel for the entire duration of the Scan Period. Since various VCTAs differ in the duration of the Scan Period, the VCTAs which have a larger period may detect the channel to be busy in case any other in range devices has already started communication. If the channel is detected to be busy at the destination end then it goes to the Abort mode and does not try to receive any data in current superframe. If the channel is detected to be busy at the source end then it goes to the Abort mode and des not try to transmit any data in current superframe. If the channel is detected to be free then the devices proceed to the next step of the state machine at the end of the Scan Period. 2. CTS Period: During this period, the destination device which has not aborted the communication during the Scan Period sends a CTS (clear to send) packet to the source. Since different VCTAs have different lengths of Scan Period, two CTS will not collide. The devices which are in Scan Period and hear the CTS will decide the channel to be busy and act accordingly by aborting their trial to communicate. In this way, the VCTAs with smaller scan period have higher priority. At the end of the CTS period, the source which has failed to successfully receive CTS will go to the Abort mode and will not try to transmit any data in current superframe. At the end of CTS period, the destination device which has successfully sent the CTS will get ready to receive data in the Data Period. 3. Data Period: Data communication takes place between the pair of devices which have detected the medium to be free and which have successfully sent the CTS across from the destination to the source. In case the pair of devices could not communicate within the current superframe, they may inform this to the PNC via CAP to aid the PNC in selecting the proper arrangement of CTA and VCTA allocations in order to minimize the chances that CTA and VCTA for devices which are in range of each other are allocated in the same period of the superframe. The SCAN period is intended for the receiver and transmitter in the VCTA to discover if the devices allocated by the CTA are within interfering range and hence decide if this VCTA can be utilized for communication. The SCAN period for the VCTA is thereby designed to be larger than the sum of SCAN period and CTS period of the CTA. The SCAN period is also intended to reduce interference from neighboring piconets and neighboring communicating devices. If there is no SCAN period for transmitter then it may interfere with communication in the nearby piconets which are within range. If there is no SCAN period for the receiver then it will not be able to discover the presence of some neighboring interfering devices. The actual length of the Scan Period can be determined based on the Physical layer capabilities. The larger the SCAN duration, the less will be the actual period available for data communication, but greater the probability of detecting interference from other piconets or devices. Using the above scheme for VCTA allocation with CTAs and the 3 step communication process, two types of spatial reuse can be utilized in the piconet: 1. Intra-Piconet spatial reuse, wherein multiple pairs of devices within the same piconet are communicating in the same CTA period. 2. Inter-Piconet spatial reuse, wherein multiple pairs of devices in different piconets are communicating in the same CTA period. The scenario of Intra-Piconet spatial reuse is illustrated in figure 8. Source and Destination pairs A & B and C & D are not within the range of each other. Hence the PNC can allocate the CTA for one pair and VCTA for another pair in the same CTA slot in CTAP. As per invented mechanism of spatial reuse mentioned elsewhere in the document, pair C, D has been allocated the VCTA, Hence C will wait a longer duration before transmitting its data to D than A will wait to transmit to B (because of greater duration of Scan Period for VCTA). Hence, even in case the device pairs that come into range of each other after CTA/ VCTA allocations, there would be no interference since the SCAN/CTS method disallows the transmission in such cases where channel is found to be busy or CTS is not received. Hence, dynamically the devices can adjust to mobility scenarios and interference. It is important to note that VCTA cannot guarantee QoS on its own but proper allotment of CTAs and VCTAs can improve the QoS by spatial reuse. The scenario of Inter-Piconet spatial reuse is illustrated in figure 9. As per the current proposal in 802.15.3, the dependent piconets share the same channel with the parent piconet. Hence their superframe has to be allocated within the superframe of the parent which has a fixed size. The size of the dependent piconet superframe which comes within the allotted CTA is the usable period, the rest being termed as reserved period. The Superframe Structure for parent and Dependent Piconet is illustrated in figure 10. The dependent piconet cannot communicate within the reserved period. Hence with increase in number of piconets or increase in hierarchy of the piconet structure, there is an increased load on the PNCs to allocate CTAs but lesser time within the superframe is actually usable for the allocation. Finally it must be noted that the VCTAs cannot be allocated by PNC along with another CTA for BROADCAST or MULTICAST, (i.e. those CTAs wherein no explicit CTS is transmitted by the receivers), or during the parent's beacon period. The present invention provides for improved spatial reuse to allow the dependent piconets to utilize the reserved period of their superframe wherever possible. In figure 9, consider that the pairs of devices A, B and C, D, which are in different piconets. PNC2 is a device within the PNC1 and the superframe for PNC2 is allocated within a CTA in PNC1 superframe. PNC2 allocates the VCTAs in the reserved region of its superframe which start and end at the CTA boundaries as allocated by the parent PNC i.e. PNC1. Hence during the CTA where A, B might be communicating, the pair of devices C, D may also communicate if they find the channel to be free. The SCAN/CTS procedure is well suited to every kind of mobility scenario as well as cases where the neighborhood of the devices may or may not be easy to determine. Figure 11 shows the actual allocation of the CTA and the VCTA by the two PNCs. VCTAs can be allocated by the dependent PNC (which is a device within the piconet of the parent PNC). The dependent PNC is aware of the CTA allocations of the parent PNC and thereby allocated VCTAs respecting the CTA boundaries as allocated by the parent PNC. Finally it must be noted that the VCTAs cannot be allocated by the dependent PNC along with a BROADCAST or MULTICAST CTA of the parent PNC, (i.e. those CTAs wherein no explicit CTS is transmitted by the receivers), or during the parent's beacon period. The extension of this VCTA allocation to dependent piconet of dependent PNC follows the same order. By combination of Intra and Inter Piconet Spatial Reuse by allotting multiple CTAs (CTAA/CTA) within the CTAP, spatial reuse can be accomplished with substantial increase in throughput within the piconet. The invented scheme can be extended to multiple pairs of devices communicating at the same time and also to multiple hierarchies of piconets. The length of the SCAN and CTS periods can be properly chosen to accomplish the minimum overhead in the operation. The length can also be dynamically decided and broadcasted as an IE in the Beacon Frame by the PNC. In scenarios characterized with high mobility, the sender and receiver may go out of range of each other. In the traditional approach the sender has no way to discover it and hence the transmitted packet is not received by the receiver. The sender times out due to lack of ACK and may decide that the packet has been corrupted or not received by the receiver and hence it retransmits the packet which may not be received for the same reason. Eventually the communication breaks down. With the proposed scheme, the sender is sure that the receiver is available in range, when it receives the CTS. If the CTS is not received for any reason including the out of range of the receiver, the transmission is aborted and hence this CTA can be now used by other devices which have been allocated VCTA. In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention. Embodiments of the invention may be implemented by using a programmed general purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nano-engineered systems, components and mechanisms may be used. In general, the functions of the present invention can be achieved by any means as is known in the art. Distributed, or networked systems, components and circuits can be used. Communication, or transfer, of data may be wireless, wired or by any other means. It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope of the present invention to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above. Additionally, any signal arrows in the drawings/Figures should be considered only as exemplary, and not limiting, unless otherwise specifically noted. Furthermore, the term "or" as used herein Is generally intended to mean "and/or" unless otherwise indicated. Combinations of components or steps will also be considered as being noted, where terminology is foreseen as rendering the ability to separate or combine is unclear. As used in the description herein and throughout the claims that follow, "a", "an", and "the" includes plural references unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of "in" includes "in" and "on" unless the context clearly dictates othenA/ise. The foregoing description of illustrated embodiments of the present invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed herein. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes only, various equivalent modifications are possible within the spirit and scope of the present invention, as those skilled in the relevant art will recognize and appreciate. As indicated, these modifications may be made to the present invention in light of the foregoing description of illustrated embodiments of the present invention and are to be included within the spirit and scope of the present invention. Thus, while the present invention has been described herein with reference to particular embodiments thereof, a latitude of modification, various changes and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of embodiments of the invention will be employed without a corresponding use of other features without departing from the scope and spirit of the invention as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit of the present invention. It is intended that the invention not be limited to the particular terms used in following claims and/or to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the invention will include any and all embodiments and equivalents falling within the scope of the appended claims. GLOSSARY OF TERMS AND DEFINITONS THEREOF ACK: Acknowledgement CAP: Contention Access Period CSMA/CA: Carrier Sense Multiple Access - Collision Avoidance OTA: Channel Time Allocation CTAP: Channel Time Allocation Period DEV: Device DEVID: Device Identifier FCS: Frame Check Sequence ID: Identifier IE: Information Element IEEE: Institute of Electrical and Electronics Engineers MAC: Medium Access Control MCTA: Management Channel Time Access PHY: Physical Layer PNC: Piconet Coordinator SIFS: Short Interframe Space TDMA: Time Division Multiple Access UWB: Ultra Wide Band VCTA: Virtual CTA WPAN: Wireless Personal Area Network WE CLAIM lA system for spatial reuse in wireless personal area network comprising: c. a piconet coordinator having information of previously allocated CTAs and the positions of the devices to allocate multiple pair of devices to the same CTA where the extra CTAs allocated with in the CTA period constitute a VCTA; d. multiple pair of devices communicating within the same CTA period without interfering with each other if the devices having been allocated the VCTA judge that they are out of range of the CTA devices ; and where the first priority is given to the devices having the CTA to communicate and accessing the channel within the CTA is in three stages - Scan Period, CTS Period, Data Period. 2. A system as claimed in claim 1 wherein the device pair which is allocated the CTA has the first priority to communicate and the devices which have been allocated the VCTA communicate only if the said device find the channel to be free or if they are outside the range of other higher priority device pairs that are communicating within the same CTA. 3. A system as claimed in claim 1 wherein the pairs of devices allocated to the CTA scan the channel for external interference in the Scan Period. 4. A system as claimed in claim 1 wherein the destination device sends a CTS packet to the source to signify that the device is free to receive the data from a source device in the CTS Period. 5. A system as claimed in claim 1 wherein the actual data communication takes place in the Data period. 6. A system as claimed in claim 1, wherein the system further comprises of a channel access mechanism within the CTAs. 7. A system as claimed in claim 1, wherein the system comprises of a new Channel Time Allocation Block for the Channel Time Allocation Information Element in the beacon frame which is called the VCTA Block. 8. A method for spatial reuse in wireless personal area network with better channel time allocation using a channel access mechanism within the CTA, comprising the steps of: (a) dividing the CTA pehod into Scan Period which is the time at the start of the CTA wherein the various devices assigned to communicate within this CTA listen to the channel and find its status whether it is free or busy; (b) dividing the CTA period into Clear to Send Period during which the destination devices send the CTS packet to the source devices to signify that the channel is free for communication for destination device; and (c) dividing the CTA period into Data Period for actual communication between the pairs of devices and all the sources who received CTS can start communication with their destinations. 9. A method as claimed in claim 8, wherein the scan period length is given by "Scan Period length = duration = (1/Priority) * (Minimum Length of Scan Period) + Length of CTS Period ". 10. A method as claimed in claim 8, wherein extra CTAs are allocated with in the CTA period, boundary lined with original CTA which are called the Virtual CTAs (VCTA). 11. A method as claimed in claim 8, wherein the VCTA and the CTA differ in only the length of the Scan Period which is least for the CTA and hence CTA is a VCTA with zero Scan Period. 12. A method as claimed in claim 8, wherein a CTA allocation method is performed where different pairs of devices chosen for the VCTAs within the same channel time are out of interfering range of each other and the VCTAs maximize the spatial reuse. 13. A method as claimed in claim 8. wherein from the various Channel Time requests received the PNC estimates whether the superframe has enough time to allocate all the requests as CTAs, else the PNC allocates some of the requests as VCTAs. 14. A method as claimed in claim 8 wherein the PNC uses the information from the allotments in the previous superframes along with the knowledge if the VCTA was usable by the pair to shuffle around the allotments to find the appropriate locations of the various VCTAs and CTAs in the CTAP. 15. A method as claimed in claim 8, wherein the CTAs and VCTAs are allocated by the PNC and are advertised in the CTAIE in the beacon where the CTA is advertised by the CTA Block and the VCTA by the VCTA Block and devices that receive the beacon for the PNC get the information of the various allotments in the superframe. 16. A method as claimed in claim 8, wherein both the source and destination devices scan the channel for the entire duration of the Scan Period. 17. A method as claimed in claim 8, wherein the VCTAs which have a larger period detect whether the channel is busy and check whether any other in range devices have already started communication since various VCTAs differ in the duration of the Scan Period. 18. A method as claimed in claim 8, wherein if the channel is detected to be busy at the destination end then it goes to the Abort mode and does not receive any data in current superframe, also it does not send CTS to source. 19. A method as claimed in claim 8, wherein if the channel is detected to be busy at the source end then it goes to the Abort mode and does not transmit any data in current superframe. 20. A method as claimed in claim 8, wherein the destination device which has not aborted the communication during the Scan Period sends a CTS (clear to send) packet to the source in the CTS period. 21. A method as claimed in claim 8 wherein two CTS will not be colliding, as different VCTAs have different lengths of Scan Period. 22. A method as claimed in claim 8, wherein the devices which are in Scan Period and hear the CTS or other interference will decide the channel to be busy and act accordingly by aborting their trial to communicate. 23. A method as claimed in claim 8 wherein at the end of the CTS period, the source which has failed to successfully receive CTS will go to the Abort mode and will not transmit any data in current superframe. 24. A method as claimed in claim 8, wherein at the end of CTS period, the destination device which has successfully sent the CTS gets ready to receive data in the Data Period. 25. A method as claimed in claim 8, wherein data communication takes place between the pair of devices which have detected the medium to be free and which have successfully sent the CTS across from the destination to the source. 26. A method as claimed in claim 8, wherein if the part of devices could not communicate within the current superframe, they may inform this to the PNC via CAP to aid the PNC in selecting the proper arrangement of CTA and VCTA allocations in order to minimize the chances that CTA and VCTA for devices which are in range of each other are allocated in the same period of the superframe. 27. A method as claimed in claim 8, wherein the SCAN period is intended for the receiver and transmitter in the VCTA to discover if the devices allocated the CTA are within interfering range and hence decide if this VCTA can be utilized for communication. 28. A method as claimed in claim 8, wherein the SCAN period for the VCTA is designed larger then the 'SCAN + CTS period of the CTA' and the SCAN period is also intended to reduce interference from neighboring piconets and neighboring communicating devices. 29. A method for Intra-Piconet spatial reuse in wireless personal area network wherein, multiple pairs of devices within the same piconet are communicating in the same CTA period during which the devices scan the channel, destination sends CTS to the receiver and data is communicated between pairs of devices 30. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein Source and Destination pairs A & B and C & D are not within the range of each other and hence the PNC allocates the CTA for one pair and VCTA for another pair in the same CTA slot in CTAP. 31. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein Source and Destination pairs A & B and C & D are not within the range of each other and if pair C, D has been allocated the VCTA then C will wait a longer duration before transmitting its data to D than A will wait to transmit to B (because of greater duration of Scan Period for VCTA). 32. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein if the device pairs come into range of each other after CTA/ VCTA allocations, there would be no interference since the SCAN/CTS method disallows the transmission in such cases where channel is found to be busy or CTS is not received where by dynamically the devices can adjust to mobility scenarios and interference which ensures lesser PER. 33. A method of Inter-Piconet spatial reuse, wherein multiple pairs of devices in different piconets are communicating in the same CTA period. 34. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein the dependent piconets share the same channel with the parent piconet and their superframe is allocated within the superframe of the parent which has a fixed size. 35. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein the pair of devices A, B and C, D, are in different piconets. 36. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein PNC2 is a device within the PNC1 and the superframe for PNC2 is allocated within a CTA in PNC1 superframe where PNC2 allocates the VCTAs in the reserved region of its superframe which start and end at the CTA boundaries as allocated by the parent PNC i.e. PNC1 and hence during the CTA where A, B might be communicating, the pair of devices C, D may also communicate if they find the channel to be free. 37. A system for spatial reuse in wireless personal area network such as substantially herein described particularly with reference to the drawings. 38. A method for spatial reuse in wireless personal area network with better channel time allocation using channel access mechanism such as substantially herein described particularly with reference to the drawings.

Full Text

FIELD OF THE INVENTION
This invention relates to the field of wireless mobile ad-hoc networks. Further, this invention relates to spatial reuse for wireless personal area networks that are based on wireless mobile ad-hoc networks. Particularly, this invention relates to effective mechanisms of allowing multiple pair of devices to communicate with each other simultaneously, thereby shanng the same spatial region for improved throughput. More particularly, this invention encompasses a system and method for spatial reuse 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. at a distance of approximately 10 meters. The IEEE (http://www.ieee.org) 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. Medium Access Control mechanisms to deal with such high data rates are currently being discussed in IEEE draft P802.15.3/D17. The medium access control mechanisms broadly include how a device may join the network, how it can transfer data at the required rate to another device, how the medium is best used etc.
Figure 1 show the IEEE-802.15.3 based wireless personal area network. It involves a network referred as piconet, in which a device may act as coordinator (referred as piconet coordinator or PNC in literature). The PNC performs the functions of allowing a device (referred as DEV) to join, allocating it a channel (time slot) to transmit to another device, synchronization mechanisms etc. This is a centralized WPAN system which is formed in an ad-hoc fashion. The PNC periodically broadcasts the information to all the associated devices in the beacon.

Figure 2 illustrates the superframe structure. Superframe is channel distribution specified by the PNC among the DEVs in piconet. It is informed to DEVs through beacon frame, which is being broadcasted by PNC.
Superframe is composed of 3 parts:
1. Beacon: It is used to set the timing allocations and to communicate management Information for the piconet. All the associated devices listen to this beacon.
2. Contention access period (CAP): It is used to communicate commands from the DEV to PNC or vice versa. It may also be used for asynchronous data if it is present in the superframe. The length of the CAP is determined by the PNC and communicated to the DEVs in the piconet via the beacon. The CAP uses CSMA/CA protocol for the medium access.
3. Channel time allocation period (CTAP): It consists of channel time allocations (CTAs), including management CTAs (MCTAs). CTAs are used for commands, isochronous streams and asynchronous data connections. A PNC may choose to use MCTAs instead of the CAP for sending command frames, unless otherwise restricted by the physical layer (PHY). An open MCTA is one where the SrcID is the BcstID; Any DEV that is associated in the piconet may attempt to send a command frame to the PNC in an open MCTA. An MCTA with the UnassocID as the SrcID is an association MCTA. Any DEV not currently associated in the piconet may attempt to send an Association Request command to the PNC in an association MCTA.
The CTAP, in contrast to CAP, uses a standard TDMA protocol where the devices (DEVs) have specified time windows which are called the CTAs. CTAs are either assigned to a specific source/destination pair and use TDMA for access or they are shared CTAs that are accessed using the slotted aloha protocol.

The invention also considers the Indian patent application bearing application No. 221/CHE/2004 titled "SYSTEM AND METHOD FOR MEDIUM ACCESS CONTROL IN WIRELESS MOBILE AD-HOC NETWORKS" as part of current art. A device can find out the presence of another device, and also whether it is in range of another device, using mechanisms provided in the mentioned patent application. Device Access Period (DAP), as mentioned in the referred patent application, is used by all the associated DEVs in piconet to send their respective heart beat frames. By listening to the heart beat frames as contained in DAP, it is possible for a first associated device to know exactly whether a second associated device is in range (reachable) or not, depending upon whether the first associated device was able to listen to the heart beat frame sent by the second associated device in the DAP.
LIMITATIONS
The present state of art in this field, as discussed in IEEE 802.15.3 (http://www.ieee.orq). has certain limitations, namely, there is no mechanism where the PNC can allocate the same CTA to more than one pair of communicating devices given that the pairs are suitable away from each other to interfere with each other's communication. In addition the PNC also does not have the information about the positions of the devices and is unable to optimize this allocation of CTAs. Also, the dependent piconets share the channel time with their parent piconet thereby limiting the amount of superframe time available to devices. Consequently, in high load cases and for dependent piconets the amount of channel time available may be less than as required.
Currently in the medium access control mechanism as defined in IEEE-802.15.3 system; the following limitations arise due to the nature of channel time allocation via CTA:
1. Only a limited number of CTAs can be allocated in a superframe since the size of the superframe is maximally bound.

2. Because of the above condition in dense piconets with high network load, PNC will have to choose between more CTAs with less time per CTA or less CTAs with more time. This affects the QoS possible.
3. A pair of devices which is not in range of another pair can communicate at the same time when the other pair is communicating without interfering. This possible optimization, known as Spatial Reuse is not addressed in the current 802.15.3 draft.
4. The dependent piconets have to share the channel time with the parent piconet in the same superframe. Hence very less channel time is available to the devices in the lower hierarchy of the dependent piconet structure in the current art.
5. Under utilization of the channel time for dependent piconets since their superframes have very less usable channel time and the rest of the superframe is reserved region.
OBJECTS OF THE INVENTION
The primary object of the invention is to provide a system and method for spatial reuse for the UWB wireless personal area networks, which are based on wireless ad-hoc networks, in a centralized network topology where one of the devices undertakes the role of a coordinator.
In other words, the invention provides a scheme for allowing various pairs of devices to communicate within the same CTA period given the condition that they are not in range of each other and hence will not be a source of potential interference to each other.
It is another object of the invention to provide a method for increasing the overall throughput of the piconet and for improving the QoS via the provision of spatial reuse.
It is another object of the invention to mitigate interference between piconets in

the same spatial region and even try to detect the presence of other piconets in the neighborhood.
It is a further object of the invention to provide a mechanism for improved channel utilization in the UWB WPAN.
SUMMARY OF THE INVENTION
The present invention relates to a system that allows spatial reuse in channel, access in the Wireless Personal Area Networks based on mobile ad-hoc networks.
The invention relates to system and method which allow multiple pair of devices to communicate simultaneously given the condition that they are sufficiently separated in spatial domain so as not to interfere with each other.
The system for the invention comprises a new mechanism within the existing medium access control involving a new algorithm for the devices to access the channel.
Accordingly, this invention explains a system for spatial reuse in wireless personal area network comprising:
a. a piconet coordinator having information of previously allocated CTAs
and the positions of the devices to allocate multiple pair of devices to
the same CTA where the extra CTAs allocated with in the CTA period
constitute a VCTA;
b. multiple pair of devices communicating within the same CTA period
without interfering with each other if the devices having been allocated
the VCTA judge that they are out of range of the CTA devices ; and

where the first priority is given to the devices having the CTA to communicate and accessing the channel within the CTA is in three stages - Scan Period, CTS Period, Data Period.
The present invention comprises a system and method which would solve the limitations associated with current art, in the following manner:
1 The PNC uses the information of previously allocated CTAs and the positions of the devices (if available) to allocate multiple pair of devices to the same CTA. The extra CTAs allocated with in the CTA period are called the Virtual CTAs (VCTA).
2. First priority is given to the devices having the CTA to communicate. If the devices having been allocated the VCTA judge that they are out of range of the CTA devices then they too can communicate. Hence multiple pair of devices can communicate within the same CTA period without interfering with each other.
3. The device pair which is allocated the CTA has the first priority to communicate. Devices which have been allocated the VCTA communicate only if they find the channel to be free or in other words, they are outside the range of other higher priority device pairs that are communicating within the same CTA. The manner in which this is accomplished is a part of the method of the proposed invention.
4. The proposed superframe structure maintains the same CTA structure but instead the access of the channel within the CTA is divided into three stages - Scan Period, CTS Period, Data Period. This is illustrated in Figure 3.
5. In the Scan Period, the various pairs of devices allocated to the CTA,

scan the channel for external interference which signifies some communication in progress. In this manner devices can decide if they will interfere with each other or not.
6. In the Clear to Send (CTS) Period, the destination device is required to send a CTS packet to the source to signify that it is free to receive the data from the source device. This implicitly signals that the destination device has found the channel to be suitably free to indulge in data communication with the source.
7. The actual data communication takes place in the Data period.
8. The CTA period will not be used by the devices to communicate if some interference is detected during the Scan Period or if the CTS is not send by the destination or if the CTS is not received by the source.
Accordingly, the present invention comprises a system for spatial reuse in wireless personal area network, wherein the multiple pair of devices are sufficiently separated in spatial domain so as not to interfere with each other and which utilizes a superframe structure where the CTA period is divided into three stages - Scan Period, CTS Period, Data Period.
Accordingly, the present invention further comprises a method for spatial reuse in wireless personal area network with better channel time allocation using a channel access mechanism within the CTA, comprising the steps of:
(a) dividing the CTA period into Scan Period which is the time at the start of the CTA wherein the various devices assigned to communicate within this CTA listen to the channel and find its status whether it is free or busy;

(b) dividing the CTA period into Clear to Send Period during which the
destination devices send the CTS packet to the source devices to signify that the
channel is free for communication for destination device; and
(c) dividing the CTA period into Data Period for actual communication between
the pairs of devices and all the sources who received CTS can start
communication with their destinations.
The other objects, features and advantages of the present invention will be apparent from the accompanying drawings and the detailed description as follows.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
Figure 1 illustrates the piconet in WPAN ad-hoc network system. The piconet range, different piconet elements like DEV and PNC, frames being transferred in piconet like beacon and data transfer between DEV to DEV, PNC to DEV and DEV to PNC are shown;
Figure 2 illustrates the superframe structure in current art, which includes the beacon. CAP, MCTA and CTA;
Figure 3 illustrates the superframe structure with the CTA structure of the present invention.
Figure 4 illustrates the Channel Time Allocation Information element along with the Channel Time Allocation Block in the current art.
Figure 5 illustrates the proposed VCTA block.

Figure 6 illustrates the state diagram for communication within the CTA for the source devices.
Figure 7 illustrates the state diagram for communication within the CTA for the destination devices.
Figure 8 illustrates the scenario of Intra-Piconet spatial reuse.
Figure 9 illustrates the scenario of Inter-Piconet spatial reuse.
Figure 10 illustrates superframe structure for parent and dependent piconet.
Figure 11 illustrates superframe structure for inter piconet spatial reuse showing the allocation of CTA and VCTA by the PNCs.
DETAILED DESCRIPTION OF THE INVENTION
The present invention relates to a system that allows improved channel time utilization in the Wireless Personal Area Networks based on mobile ad-hoc networks. Implementation of the mechanisms of the present invention results in better throughput and QoS compared to the current art.
The invention relates to system and method which allow spatial reuse of channel time by pair of devices outside the range of each other.
The system for the invention comprises of a new channel access mechanism within the CTAs. The invention also proposes Virtual CTAs.
Accordingly, the invention provides a method for better channel time allocation and utilization in a piconet than present in current art.

Accordingly, the invention provides a method to improve the throughput and QoS in the piconet by providing spatial reuse of the channel.
Accordingly, the invention also provides a method to multiple pairs of devices to communicate simultaneously given that they do not interfere with each other.
Accordingly, the invention also provides a method to mitigate the interference between simultaneously operating piconets.
The subsequent subsections describe the individual entities to effect the invention.
1. Figure 3 illustrates the invented channel access mechanism within the
CTA.
- Scan Period is the time in the starting of the CTA wherein the various devices assigned to communicate within this CTA listen to the channel and find if it's free or busy.
- Clear to Send Period is for the destination devices to send the CTS packet to the source devices to signify that the channel is free for communication.
- Data Period is for actual communication between the pairs of devices. All the sources which received CTS can start communication with their destinations.

2. The VCTA and the CTA differ in only the length of the Scan Period which is least for the CTA. Hence CTA can be visualized as a VCTA with zero Scan Period.
3. All the Channel Time Allocations can be described in terms of VCTAs itself. The CTA is still maintained for backward compatibility. Hence CTA can be visualized as a VCTA with zero Scan Period.

4. In the present invention, a new Channel Time Allocation Block for the Channel Tinne Allocation Information Element in the beacon frame is being proposed for adding VCTAs. It is illustrated in Figure 5. The invented block is called the VCTA Block and differs from that in the current art in the following way:
- The invented block is called the VCTA block.
- VCTA Block describes the allotment of a VCTA in the CTAP, like the CTA Block in the current art describes the allotment of a CTA in the CTAP.
- The VCTA Scan Duration field details the length of the scan period for a particular VCTA.
- The location of VCTA is given by the VCTA Location field.
" The length of VCTA is given by the VCTA Duration field.
- The VCTA block does not includes the information of the priority of
the VCTA but multiple VCTAs can be allocated with increasing
priorities. The lower the duration of the scan period for the VCTA,
the higher would be its priority.
Scan Period length = duration = (1/Priority) * (Minimum Length of Scan Period) + Length of CTS Period
Different VCTAs have different length of the Scan period. Hence the Channel Time Allocations are prioritized with the CTA having the highest priority due to its smallest duration of Scan Period.
VCTAs cannot guarantee channel time like CTA does. In the presence of a suitable mechanism to allocate the VCTAs properly, so that the different pairs of devices chosen for the VCTAs within the same channel time are out of interfering range of each other, the VCTAs can be used to maximize spatial reuse.
The subsequent subsections describe the operation of the invention:

I. CTA Allocations
As in the current art, the source devices send CTA Request Command to the PNC to request a CTA allocation with the destination. In case the source has knowledge of its neighbors then it includes that information in the CTA request.
From the various requests received the PNC can conclude whether the superframe has enough time to allocate all the requests as CTAs else the PNC would have to allocate some of the requests as VCTAs. It should be noted that without a mechanism to find the neighbors of a device, it is not possible for the PNC to allocate the VCTAs in the best possible manner to minimize the interference.
The PNC can also use the information from the allotments in the previous superframes along with the knowledge if the VCTA was usable by the pair to shuffle around the allotments to find the appropriate locations of the various VCTAs and CTAs in the CTAP.
The CTAs and VCTAs are allocated by the PNC and are advertised in the CTAIE in the beacon. The CTA is advertised by the CTA Block and the VCTA by the VCTA Block. Devices that receive the beacon for the PNC get the information of the various allotments in the superframe.
2. CTA Utilization
Once allocated, a CTA or a VCTA, the source and destination have to cycle through a 3 step process to communicate. In the first step the devices scan the channel, in the second the destination sends CTS to the receiver and in the third, the data communication takes place. The state diagram of communication for the source devices is shown in figure 6 and for destination devices is shown in figure 7. The state machine is further described as follows:

1 Scan Period: Both the source and destination devices scan the channel for the entire duration of the Scan Period. Since various VCTAs differ in the duration of the Scan Period, the VCTAs which have a larger period may detect the channel to be busy in case any other in range devices has already started communication. If the channel is detected to be busy at the destination end then it goes to the Abort mode and does not try to receive any data in current superframe. If the channel is detected to be busy at the source end then it goes to the Abort mode and des not try to transmit any data in current superframe. If the channel is detected to be free then the devices proceed to the next step of the state machine at the end of the Scan Period.
2. CTS Period: During this period, the destination device which has not aborted the communication during the Scan Period sends a CTS (clear to send) packet to the source. Since different VCTAs have different lengths of Scan Period, two CTS will not collide. The devices which are in Scan Period and hear the CTS will decide the channel to be busy and act accordingly by aborting their trial to communicate. In this way, the VCTAs with smaller scan period have higher priority. At the end of the CTS period, the source which has failed to successfully receive CTS will go to the Abort mode and will not try to transmit any data in current superframe. At the end of CTS period, the destination device which has successfully sent the CTS will get ready to receive data in the Data Period.
3. Data Period: Data communication takes place between the pair of devices which have detected the medium to be free and which have successfully sent the CTS across from the destination to the source. In case the pair of devices could not communicate within the current superframe, they may inform this to the PNC via CAP to aid the PNC in selecting the proper arrangement of CTA and VCTA allocations in order to minimize the chances that CTA and VCTA for devices which are in range of each other are allocated in the

same period of the superframe.
The SCAN period is intended for the receiver and transmitter in the VCTA to discover if the devices allocated by the CTA are within interfering range and hence decide if this VCTA can be utilized for communication. The SCAN period for the VCTA is thereby designed to be larger than the sum of SCAN period and CTS period of the CTA. The SCAN period is also intended to reduce interference from neighboring piconets and neighboring communicating devices. If there is no SCAN period for transmitter then it may interfere with communication in the nearby piconets which are within range. If there is no SCAN period for the receiver then it will not be able to discover the presence of some neighboring interfering devices.
The actual length of the Scan Period can be determined based on the Physical layer capabilities. The larger the SCAN duration, the less will be the actual period available for data communication, but greater the probability of detecting interference from other piconets or devices.
Using the above scheme for VCTA allocation with CTAs and the 3 step communication process, two types of spatial reuse can be utilized in the piconet:
1. Intra-Piconet spatial reuse, wherein multiple pairs of devices within the same piconet are communicating in the same CTA period.
2. Inter-Piconet spatial reuse, wherein multiple pairs of devices in different piconets are communicating in the same CTA period.
The scenario of Intra-Piconet spatial reuse is illustrated in figure 8. Source and Destination pairs A & B and C & D are not within the range of each other. Hence the PNC can allocate the CTA for one pair and VCTA for another pair in the same CTA slot in CTAP. As per invented mechanism of spatial reuse mentioned elsewhere in the document, pair C, D has been allocated the VCTA, Hence C will wait a longer duration before transmitting its data to D than A will wait to

transmit to B (because of greater duration of Scan Period for VCTA). Hence, even in case the device pairs that come into range of each other after CTA/ VCTA allocations, there would be no interference since the SCAN/CTS method disallows the transmission in such cases where channel is found to be busy or CTS is not received. Hence, dynamically the devices can adjust to mobility scenarios and interference. It is important to note that VCTA cannot guarantee QoS on its own but proper allotment of CTAs and VCTAs can improve the QoS by spatial reuse.
The scenario of Inter-Piconet spatial reuse is illustrated in figure 9. As per the current proposal in 802.15.3, the dependent piconets share the same channel with the parent piconet. Hence their superframe has to be allocated within the superframe of the parent which has a fixed size. The size of the dependent piconet superframe which comes within the allotted CTA is the usable period, the rest being termed as reserved period. The Superframe Structure for parent and Dependent Piconet is illustrated in figure 10. The dependent piconet cannot communicate within the reserved period. Hence with increase in number of piconets or increase in hierarchy of the piconet structure, there is an increased load on the PNCs to allocate CTAs but lesser time within the superframe is actually usable for the allocation. Finally it must be noted that the VCTAs cannot be allocated by PNC along with another CTA for BROADCAST or MULTICAST, (i.e. those CTAs wherein no explicit CTS is transmitted by the receivers), or during the parent's beacon period.
The present invention provides for improved spatial reuse to allow the dependent piconets to utilize the reserved period of their superframe wherever possible. In figure 9, consider that the pairs of devices A, B and C, D, which are in different piconets. PNC2 is a device within the PNC1 and the superframe for PNC2 is allocated within a CTA in PNC1 superframe. PNC2 allocates the VCTAs in the reserved region of its superframe which start and end at the CTA boundaries as allocated by the parent PNC i.e. PNC1. Hence during the CTA where A, B might be communicating, the pair of devices C, D may also communicate if they find

the channel to be free. The SCAN/CTS procedure is well suited to every kind of mobility scenario as well as cases where the neighborhood of the devices may or may not be easy to determine. Figure 11 shows the actual allocation of the CTA and the VCTA by the two PNCs. VCTAs can be allocated by the dependent PNC (which is a device within the piconet of the parent PNC). The dependent PNC is aware of the CTA allocations of the parent PNC and thereby allocated VCTAs respecting the CTA boundaries as allocated by the parent PNC. Finally it must be noted that the VCTAs cannot be allocated by the dependent PNC along with a BROADCAST or MULTICAST CTA of the parent PNC, (i.e. those CTAs wherein no explicit CTS is transmitted by the receivers), or during the parent's beacon period.
The extension of this VCTA allocation to dependent piconet of dependent PNC follows the same order.
By combination of Intra and Inter Piconet Spatial Reuse by allotting multiple CTAs (CTAA/CTA) within the CTAP, spatial reuse can be accomplished with substantial increase in throughput within the piconet. The invented scheme can be extended to multiple pairs of devices communicating at the same time and also to multiple hierarchies of piconets. The length of the SCAN and CTS periods can be properly chosen to accomplish the minimum overhead in the operation. The length can also be dynamically decided and broadcasted as an IE in the Beacon Frame by the PNC.
In scenarios characterized with high mobility, the sender and receiver may go out of range of each other. In the traditional approach the sender has no way to discover it and hence the transmitted packet is not received by the receiver. The sender times out due to lack of ACK and may decide that the packet has been corrupted or not received by the receiver and hence it retransmits the packet which may not be received for the same reason. Eventually the communication breaks down. With the proposed scheme, the sender is sure that the receiver is available in range, when it receives the CTS. If the CTS is not received for any

reason including the out of range of the receiver, the transmission is aborted and hence this CTA can be now used by other devices which have been allocated VCTA.
In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention.
Embodiments of the invention may be implemented by using a programmed general purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nano-engineered systems, components and mechanisms may be used. In general, the functions of the present invention can be achieved by any means as is known in the art. Distributed, or networked systems, components and circuits can be used. Communication, or transfer, of data may be wireless, wired or by any other means.
It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope of the present invention to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above.

Additionally, any signal arrows in the drawings/Figures should be considered only as exemplary, and not limiting, unless otherwise specifically noted. Furthermore, the term "or" as used herein Is generally intended to mean "and/or" unless otherwise indicated. Combinations of components or steps will also be considered as being noted, where terminology is foreseen as rendering the ability to separate or combine is unclear.
As used in the description herein and throughout the claims that follow, "a", "an", and "the" includes plural references unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of "in" includes "in" and "on" unless the context clearly dictates othenA/ise.
The foregoing description of illustrated embodiments of the present invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed herein. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes only, various equivalent modifications are possible within the spirit and scope of the present invention, as those skilled in the relevant art will recognize and appreciate. As indicated, these modifications may be made to the present invention in light of the foregoing description of illustrated embodiments of the present invention and are to be included within the spirit and scope of the present invention.
Thus, while the present invention has been described herein with reference to particular embodiments thereof, a latitude of modification, various changes and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of embodiments of the invention will be employed without a corresponding use of other features without departing from the scope and spirit of the invention as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit of the present invention. It is intended that the invention not be limited

to the particular terms used in following claims and/or to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the invention will include any and all embodiments and equivalents falling within the scope of the appended claims.

GLOSSARY OF TERMS AND DEFINITONS THEREOF
ACK: Acknowledgement
CAP: Contention Access Period
CSMA/CA: Carrier Sense Multiple Access - Collision Avoidance
OTA: Channel Time Allocation
CTAP: Channel Time Allocation Period
DEV: Device
DEVID: Device Identifier
FCS: Frame Check Sequence
ID: Identifier
IE: Information Element
IEEE: Institute of Electrical and Electronics Engineers
MAC: Medium Access Control
MCTA: Management Channel Time Access
PHY: Physical Layer
PNC: Piconet Coordinator
SIFS: Short Interframe Space
TDMA: Time Division Multiple Access
UWB: Ultra Wide Band
VCTA: Virtual CTA
WPAN: Wireless Personal Area Network

WE CLAIM
lA system for spatial reuse in wireless personal area network comprising:
c. a piconet coordinator having information of previously allocated CTAs
and the positions of the devices to allocate multiple pair of devices to
the same CTA where the extra CTAs allocated with in the CTA period
constitute a VCTA;
d. multiple pair of devices communicating within the same CTA period
without interfering with each other if the devices having been allocated
the VCTA judge that they are out of range of the CTA devices ; and
where the first priority is given to the devices having the CTA to communicate and accessing the channel within the CTA is in three stages - Scan Period, CTS Period, Data Period.
2. A system as claimed in claim 1 wherein the device pair which is allocated the CTA has the first priority to communicate and the devices which have been allocated the VCTA communicate only if the said device find the channel to be free or if they are outside the range of other higher priority device pairs that are communicating within the same CTA.
3. A system as claimed in claim 1 wherein the pairs of devices allocated to the CTA scan the channel for external interference in the Scan Period.
4. A system as claimed in claim 1 wherein the destination device sends a CTS packet to the source to signify that the device is free to receive the data from a source device in the CTS Period.
5. A system as claimed in claim 1 wherein the actual data communication takes

place in the Data period.
6. A system as claimed in claim 1, wherein the system further comprises of a channel access mechanism within the CTAs.
7. A system as claimed in claim 1, wherein the system comprises of a new Channel Time Allocation Block for the Channel Time Allocation Information Element in the beacon frame which is called the VCTA Block.
8. A method for spatial reuse in wireless personal area network with better channel time allocation using a channel access mechanism within the CTA, comprising the steps of:
(a) dividing the CTA pehod into Scan Period which is the time at the start of the
CTA wherein the various devices assigned to communicate within this CTA listen
to the channel and find its status whether it is free or busy;
(b) dividing the CTA period into Clear to Send Period during which the
destination devices send the CTS packet to the source devices to signify that the
channel is free for communication for destination device; and
(c) dividing the CTA period into Data Period for actual communication between
the pairs of devices and all the sources who received CTS can start
communication with their destinations.
9. A method as claimed in claim 8, wherein the scan period length is given by
"Scan Period length = duration = (1/Priority) * (Minimum Length of Scan Period)
+ Length of CTS Period ".
10. A method as claimed in claim 8, wherein extra CTAs are allocated with in the
CTA period, boundary lined with original CTA which are called the Virtual CTAs
(VCTA).

11. A method as claimed in claim 8, wherein the VCTA and the CTA differ in only
the length of the Scan Period which is least for the CTA and hence CTA is a
VCTA with zero Scan Period.
12. A method as claimed in claim 8, wherein a CTA allocation method is performed where different pairs of devices chosen for the VCTAs within the same channel time are out of interfering range of each other and the VCTAs maximize the spatial reuse.
13. A method as claimed in claim 8. wherein from the various Channel Time requests received the PNC estimates whether the superframe has enough time to allocate all the requests as CTAs, else the PNC allocates some of the requests as VCTAs.
14. A method as claimed in claim 8 wherein the PNC uses the information from the allotments in the previous superframes along with the knowledge if the VCTA was usable by the pair to shuffle around the allotments to find the appropriate locations of the various VCTAs and CTAs in the CTAP.
15. A method as claimed in claim 8, wherein the CTAs and VCTAs are allocated by the PNC and are advertised in the CTAIE in the beacon where the CTA is advertised by the CTA Block and the VCTA by the VCTA Block and devices that receive the beacon for the PNC get the information of the various allotments in the superframe.
16. A method as claimed in claim 8, wherein both the source and destination devices scan the channel for the entire duration of the Scan Period.
17. A method as claimed in claim 8, wherein the VCTAs which have a larger period detect whether the channel is busy and check whether any other in range

devices have already started communication since various VCTAs differ in the duration of the Scan Period.
18. A method as claimed in claim 8, wherein if the channel is detected to be busy at the destination end then it goes to the Abort mode and does not receive any data in current superframe, also it does not send CTS to source.
19. A method as claimed in claim 8, wherein if the channel is detected to be busy at the source end then it goes to the Abort mode and does not transmit any data in current superframe.
20. A method as claimed in claim 8, wherein the destination device which has not aborted the communication during the Scan Period sends a CTS (clear to send) packet to the source in the CTS period.
21. A method as claimed in claim 8 wherein two CTS will not be colliding, as different VCTAs have different lengths of Scan Period.
22. A method as claimed in claim 8, wherein the devices which are in Scan Period and hear the CTS or other interference will decide the channel to be busy and act accordingly by aborting their trial to communicate.
23. A method as claimed in claim 8 wherein at the end of the CTS period, the source which has failed to successfully receive CTS will go to the Abort mode and will not transmit any data in current superframe.
24. A method as claimed in claim 8, wherein at the end of CTS period, the destination device which has successfully sent the CTS gets ready to receive data in the Data Period.
25. A method as claimed in claim 8, wherein data communication takes place between the pair of devices which have detected the medium to be free and

which have successfully sent the CTS across from the destination to the source.
26. A method as claimed in claim 8, wherein if the part of devices could not communicate within the current superframe, they may inform this to the PNC via CAP to aid the PNC in selecting the proper arrangement of CTA and VCTA allocations in order to minimize the chances that CTA and VCTA for devices which are in range of each other are allocated in the same period of the superframe.
27. A method as claimed in claim 8, wherein the SCAN period is intended for the receiver and transmitter in the VCTA to discover if the devices allocated the CTA are within interfering range and hence decide if this VCTA can be utilized for communication.
28. A method as claimed in claim 8, wherein the SCAN period for the VCTA is designed larger then the 'SCAN + CTS period of the CTA' and the SCAN period is also intended to reduce interference from neighboring piconets and neighboring communicating devices.
29. A method for Intra-Piconet spatial reuse in wireless personal area network wherein, multiple pairs of devices within the same piconet are communicating in the same CTA period during which the devices scan the channel, destination sends CTS to the receiver and data is communicated between pairs of devices
30. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein Source and Destination pairs A & B and C & D are not within the range of each other and hence the PNC allocates the CTA for one pair and VCTA for another pair in the same CTA slot in CTAP.
31. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein Source and Destination pairs A & B and C & D are not within the range of each other and if pair C, D has been allocated the VCTA then C will wait a longer

duration before transmitting its data to D than A will wait to transmit to B (because of greater duration of Scan Period for VCTA).
32. A method of Intra-Piconet spatial reuse as claimed in claim 29, wherein if the device pairs come into range of each other after CTA/ VCTA allocations, there would be no interference since the SCAN/CTS method disallows the transmission in such cases where channel is found to be busy or CTS is not received where by dynamically the devices can adjust to mobility scenarios and interference which ensures lesser PER.
33. A method of Inter-Piconet spatial reuse, wherein multiple pairs of devices in different piconets are communicating in the same CTA period.
34. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein the dependent piconets share the same channel with the parent piconet and their superframe is allocated within the superframe of the parent which has a fixed size.
35. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein the pair of devices A, B and C, D, are in different piconets.
36. A method of Inter-Piconet spatial reuse as claimed in claim 33, wherein PNC2 is a device within the PNC1 and the superframe for PNC2 is allocated within a CTA in PNC1 superframe where PNC2 allocates the VCTAs in the reserved region of its superframe which start and end at the CTA boundaries as allocated by the parent PNC i.e. PNC1 and hence during the CTA where A, B might be communicating, the pair of devices C, D may also communicate if they find the channel to be free.
37. A system for spatial reuse in wireless personal area network such as substantially herein described particularly with reference to the drawings.

38. A method for spatial reuse in wireless personal area network with better channel time allocation using channel access mechanism such as substantially herein described particularly with reference to the drawings.

Documents:

0575-che-2004-other documents.pdf

575-che-2004-abstract.pdf

575-che-2004-claims.pdf

575-che-2004-correspondnece-others.pdf

575-che-2004-correspondnece-po.pdf

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

575-che-2004-drawings.pdf

575-che-2004-form 1.pdf

575-che-2004-form 26.pdf

575-che-2004-form 5.pdf

« Previous Patent

Next Patent »

Patent Number

211879

Indian Patent Application Number

575/CHE/2004

PG Journal Number

02/2008

Publication Date

11-Jan-2008

Grant Date

13-Nov-2007

Date of Filing

17-Jun-2004

Name of Patentee

M/S. SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED

Applicant Address

BAGMANE LAKEVIEW ,BLOCK B" NO.66/1,BAGMANE TECH PARK,V. RAMAN NAGAR , BANGALORE-560 093,

Inventors:

#	Inventor's Name	Inventor's Address
1	WASON,PRASHANT	BAGMANE LAKEVIEW ,BLOCK B" NO.66/1,BAGMANE TECH PARK,V. RAMAN NAGAR , BANGALORE-560 093,

PCT International Classification Number

H 04 J 001/00

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA