CN1408162A - Route discovery based piconet forming - Google Patents

Abstract

A method for establishing a route over which data packets are to be sent from a source node to a destination node in an ad-hoc network is provided. A source having packets to send to a destination node employs a reactive routing protocol if it does not posses the route to the destination node. Initially, it may be determined whether or not the source node is a member of an existing piconet. If the source node is a member of an existing piconet, a ROUTE request message may be broadcast to the nodes of the existing piconet, while the source awaits a timely REPLY message. If the source node is not a member of an existing piconet, or if a time REPLY message is not received, the source node may initiate a new route discovery process wherein the nodes attempt to establish new piconets that enable more efficient communication between the source and destination nodes.

Description

Piconet Construction Based on Route Discovery

field of invention

The present invention relates to the field of telecommunications. More specifically, the invention relates to the field of ad hoc telecommunications.

Background technique

"Bluetooth" is an example of a specific wireless networking technology that uses a frequency hopping scheme in the unregistered 2.4Ghz ISM (Industrial Scientific Medical) frequency band. Bluetooth was originally invented to eliminate cables between devices such as phones, PC cards, and wireless headsets in short-range wireless environments. Today, however, Bluetooth is a truly specific wireless networking technology that can be used for both synchronous services such as voice and asynchronous services such as IP-based data services. The destination is any digital communication device such as a phone, PDA, laptop, digital camera, video monitor, printer, fax machine, etc. may be able to communicate over a wireless interface by using a Bluetooth wireless chip and its accompanying software.

Figures 1A-C illustrate three typical piconets. According to Bluetooth technology, two or more Bluetooth (BT) units sharing the same channel form a piconet. In a piconet, a BT unit can be a master or a slave, although each piconet must have only one master and a maximum of 7 active slaves. Any BT unit can be the master unit.

Figure 2 illustrates a scatternet. A scatternet is formed by interconnecting two or more piconets. Two or more piconets are interconnected by a common shared BT unit that is a member of each piconet. BT unit 205 is an example of one BT unit shared by three piconets 1 , 2 and 3 .

Fig. 2 further illustrates a BT unit, which is shared by two or more piconets, can be a slave unit of multiple piconets, but can only be a master unit of one piconet. For example, BT unit 210 is the master unit of piconet 10, but only the slave unit of piconets 11 and 12. In addition, a BT unit belonging to two or more piconet members transmits and receives data in one piconet at the same time. Therefore, it is necessary to participate in multiple piconets on a time-division multiplexed basis. Note that there is no direct transmission connection between slave units, only direct transmission between master and slave units or vice versa.

Each BT unit has a globally unique 48-bit IEEE 802 address. This address is called the Bluetooth Device Address (BD_ADDR) and is assigned when the BT unit is manufactured and does not change thereafter. In addition, the master unit of the piconet assigns a local active member address (AM_ADDR) to each active member in the piconet. The AM_ADDR, which is only three bits long, is allocated or reallocated dynamically and is unique within a single piconet. The master uses AM-ADDR to poll specific slaves in the piconet. When a slave unit triggered by a master poll packet sends a packet to the master, it includes its own AM_ADDR in the packet header.

Although all data is transmitted in packets, packets also contain isochronous data on SCO links, primarily for voice traffic, and/or asynchronous data on asynchronous connectionless links (ACLs). If the packets contain asynchronous data, an acknowledgment and retransmission scheme is used to ensure reliable data transmission, as in Forward Error Correction (FEC) in channel coding formats.

Figure 3 illustrates the standard format of a Bluetooth packet, although there are exceptions for certain control packets. AM_ADDR is located at the head of the packet, followed by control parameters (such as bits indicating an acknowledgment or retransmission request) if applicable, and a Header Error Checking Code (HEC).

The format of the payload depends on the type of packet. The payload of an ACL packet consists of a header, a data field, and in many cases, a cyclic check (CRC) code. The payload of the SCO packet contains only one data field. In addition, there are mixed packets that contain two data fields, one for synchronous data and one for asynchronous data. Packets that do not contain a CRC are neither acknowledged nor retransmitted.

Figure 4 illustrates the protocol layers of the Bluetooth system. Baseband, LMP and L2CAP are existing bluetooth specific protocols, the "high level protocol or application" layer represents protocols that may or may not be bluetooth specific, there is no network layer in the current bluetooth specification.

An important limitation related to Bluetooth is that there is no defined method of addressing and routing packets from a BT unit in one piconet to a BT unit in another piconet. In other words, the current Bluetooth specification does not specify how to perform inter-piconet communication in a scatternet.

An important capability in any ad hoc network technology is to discover the characteristics of neighboring devices. The same is true for Bluetooth. Without the ability to discover neighboring devices, a BT unit cannot find other BT units it needs to communicate with, and therefore cannot form an ad hoc network. The process of discovering neighboring devices in Bluetooth includes an INQUIRY message and an INQUIRY RESPONSE message. A BT unit that wants to discover neighboring BT units within wireless coverage, repeatedly sends INQUIRY messages and listens for INQUIRY RESPONSE messages according to a specific timing and frequency sequence. An INQUIRY message contains only an Inquiry Access Code. The Inquiry Access Code can be a General Inquiry Access Code (GIAC) sent to find any neighboring BT units, or a Dedicated Inquiry Access Code (DIAC) sent to find a specific BT unit, a specific DIAC dedicated to the BT unit.

A BT unit that receives an inquiry message, whether the message contains a GIAC or a DIAC, responds with an INQUIRY RESPONSE message. The INQUIRY RESPONSE message is actually a Frequency Hopping Synchronization (FHS) packet. Bluetooth uses FHS packets for other purposes, eg, to synchronize frequency hopping channel sequences as the name suggests. In any event, by listening to the INQUIRY RESPONSE message, the INQUIRY-initiated BT unit can collect the BD_ADDR and internal clock values, both of which are included in the FHS packets of neighboring BT units.

Related to the INQUIRY process is the PAGE process. The PAGE procedure is used to establish an actual connection between two BT units. When the BD_ADDR of a neighboring BT unit is known as a result of the INQUIRY procedure, the neighboring BT unit may be paged with a PAGE message. Knowing the internal clock value of the paged BT unit speeds up the PAGE process because it is possible for the paging unit to estimate when and on which frequency hopping channels neighboring BT units are listening for PAGE messages.

The PAGE message contains the Device Access Code (DAC) from the BD_ADDR of the paged BT unit. A BT unit that receives a PAGE message containing its DAC responds with the same packet. The paged BT unit then replies with an FHS packet including the paged BT unit's BD_ADDR, the paged BT unit's current internal clock value, the AM_ADDR assigned to the paged BT unit and other parameters. The paged BT unit then responds again with its DAC and the connection between the two BT units is established.

If the paged BT unit is already the master unit of the existing piconet, the paged BT unit joins the existing piconet as a new slave unit. In addition, two BT units form a new piconet, and the paging BT unit acts as the master unit. Since the INQUIRY message does not include any information about the sender, the BT unit that starts the INQUIRY process is the only BT unit that can start the subsequent PAGE process. Thus, a BT unit that initiates an INQUIRY procedure will become the master of the piconet formed as a result of the subsequent PAGE procedure. However, if deemed necessary, the roles of master and slave units in Bluetooth can be switched by using a master-slave switching mechanism. However, this is a complex and extensive process to redefine the entire piconet which may include other slave units in the piconet.

The INQUIRY and PAGE procedures are well specified in the current Bluetooth standard. This is all the tools needed to form a new Bluetooth piconet and add new BT units to existing piconets. However, even though these tools are well specified, there are no rules and guidelines for how to use them. When neighbors are discovered, there is no way of knowing who to connect to to form a proper piconet. Furthermore, even if a master-slave transition mechanism exists, using it is a wide-ranging process as specified, and it is difficult to know when to use it in order to improve the efficiency of the piconet. Consequently, piconets are formed more or less randomly, often far from optimal piconet and scatternet structures as a result. An exception is when the BT unit initiating the INQUIRY procedure already knows the BD_ADDR of the BT unit it is connecting to.

An important aspect of Bluetooth is the support of IP at the top of the Bluetooth protocol stack. There are currently two proposals to achieve this. The first proposal treats each piconet as an IP subnet, running IP on top of each piconet's L2CAP. The second proposal treats the entire Bluetooth scatternet as one IP subnet. This requires an adaptation layer, referred to here as the Network Adaptation Layer (NAL) inserted between the L2CAP and IP layers as shown in FIG. 5 . The purpose of the NAL is to emulate a shared media network (eg broadcast media) assumed by the IP layer.

The first proposal suffers from several problems, partly because a Bluetooth piconet is not a shared media network. The second proposal is certainly not without its problems, but seems to be a more promising option. The present invention can be applied to the second proposal. Therefore, the present invention assumes that the protocol layer as shown in FIG. 5 includes NAL.

The NAL layer must support several features. For example, it must support a routing mechanism to route packets in a scatternet while causing the scatternet to emulate the shared media network assumed by the IP layer. Regardless of the routing scheme used to route packets through the scatternet, the scheme must rely on BT units that are members of more than one piconet to forward packets from one piconet to another. These BT units mentioned here are referred to below as forwarding nodes.

In general, routing protocols are divided into active and reactive. Proactive routing protocols maintain routes between nodes even if the route is not currently needed. Proactive routing protocols respond to topology changes even if no traffic is affected by the network topology change. Proactive routing protocols are very expensive in terms of overhead because each node must periodically send out control messages to other nodes in the network.

Another optional proposal is to use reactive routing. According to reactive routing, routes are established only when there is an explicit need to route packets to a specific destination. This means that the routing protocol only knows the routes needed to send the data. Therefore, the overhead caused by maintaining the route is small.

To establish a source-to-destination route, a source node typically broadcasts a REQUEST message requesting a route to a specified destination. All in-range nodes receive the REQUEST message. A node that receives a REQUEST message that is neither the destination node nor has a valid route to the destination node will rebroadcast the REQUEST message to its neighbors. When a destination node or a node with a valid route to the destination node receives a REQUEST message, it can limit network flooding by not rebroadcasting the REQUEST message and sending a unicast REPLY message back to the source node.

Typically, the source node uses the first received reply message, and it only requests a new route if the current route is broken. Routing can be done according to one of the following provisions. First, source routing, the entire route is received in the REPLY message. Intermediate nodes do not need information, only the source needs to know the route. The entire route is specified by each sent packet. The second contains a distance vector, which means that the RELAY message stores information in the routing table of the intermediate node. This means that only the destination needs to be in the sent packet.

The Bluetooth protocol, as described, has INQUIRY and PAGE procedures to build piconets, but it does not describe how these are used to form efficient scatternets. Furthermore, current solutions do not provide a way for nodes that have packets to be sent to a destination and are not members of any piconet.

Summary of the invention

These and other problems, disadvantages and limitations associated with the prior art are overcome according to the present invention, wherein a source node (i.e. a node from which a packet is sent) in a telecommunications network is capable of forming one or more new network connection.

It is therefore an object of the present invention to allow a reactive specific routing protocol to decide whether to establish a new network connection in order to form a route between a source node and a destination node.

Another object of the present invention is to provide means for the source node in the network to create a new network connection between the source node and the destination node to form a route as soon as a predefined event occurs.

According to an aspect of the invention, the above and other objects are achieved by a method in a communication network for establishing a route over which data packets are sent from a source node to a destination node. The method includes requesting route discovery between a source node and a destination node over an existing network connection. Finally, a determination is made whether the route discovery request has failed. If the route discovery request fails, a route between the source node and the destination node is formed by creating one or more new network connections.

Description of drawings

Objects and advantages of the present invention will be understood by reading the following detailed description when read in conjunction with the accompanying drawings.

Figures 1A-C illustrate three exemplary piconets;

Figure 2 illustrates an exemplary scatternet;

Figure 3 illustrates the standard format of a Bluetooth data packet;

Figure 4 illustrates the various protocol layers associated with a Bluetooth-based network;

Figure 5 illustrates the protocol layers, including the network adaptation layer, associated with a Bluetooth-based network;

Figure 6 illustrates a technique for accomplishing route discovery in accordance with an exemplary embodiment of the present invention; and

Figure 7 illustrates an alternative technique for accomplishing route discovery in accordance with an exemplary embodiment of the present invention.

Detailed description of the invention

Since Bluetooth is the main object, this invention will use Bluetooth terminology to describe the Bluetooth context. However, it will also briefly describe how the invention can be generalized to other network technologies, whether wired or wireless.

In general, the present invention combines reactive routing and piconet formation. The present invention accomplishes this as described below.

A source that has packets to send to a destination node will use the reactive routing protocol if it does not own a route to the destination node. The source node obtains the route through the reactive routing protocol, however, depending on whether the source node is a member of one or several existing piconets or not a member of any piconet will produce different behavior.

Figure 6 illustrates a technique in accordance with an exemplary embodiment of the invention. Initially, as shown in step 605, it is determined whether the source node is a member of an existing piconet. If, according to the "no" path of decision step 605, the source node is not a member of an existing piconet, then the technique continues to step 635, which will be described below. However, if, according to the "Yes" path of decision step 605, the source node is a member of an existing piconet, then the source node initiates a route discovery in the existing piconet, as shown in step 610. Of course, this is achieved by broadcasting a ROUTE request message to nodes connected through the existing piconet.

As shown in step 615, the source node then waits for a timely RELAY message. If, according to the "no" path of decision step 615, a timely response has not been received, then the process continues again to step 635. Alternatively, if a timely reply is received according to the "YES" path of decision step 615, the source node decides whether it wishes to send its packet via the route defined by the REPLY message.

Based on the "no" path of decision step 620, the source node may decide to more efficiently send its packets to the destination node along the route defined by the REPLY message. If this is the case, the source node will act as indicated by step 625 . On the contrary, according to the "Yes" path of decision step 620, the source node may decide that it is necessary to optimize the route, that is, define a new more efficient route. If so, the source node may begin sending packets through the route defined by the REPLY message, as shown in step 620 . However, at the same time, the source node starts a new route discovery process according to step 635, in which the node will try to build a new piconet that can communicate more efficiently between the source and destination nodes. Assuming a more efficient route can be established, the source node will route the packet through the newly formed piconet. Therefore, those skilled in the art will readily understand that route discovery according to the present invention affects the formation of new piconets.

Immediately starting to establish a new piconet is not optimal because piconet establishment is a relatively slow process that may take longer than the actual receipt of a REPLY message via an existing piconet to the destination's efficient route. Therefore, a source node may obtain a route faster if the destination node is reachable through an already existing piconet. However, nothing prohibits a node from reforming the piconet after the first successful route establishment. Another reason is that piconet formation during route discovery can result in many unnecessary piconets that need to be maintained and included in the piconet's schedule. Use of existing piconets

As mentioned above, if the source node is a member of one or several existing piconets, it will trigger the routing protocol to issue a normal ROUTE REQUEST message that diffuses the network. In this way, route request packets only flood existing piconets. In the worst case, however, the destination node is unreachable because eg it is not a member of any existing piconet, or the destination node is only a member of a piconet which does not have any connection for the source node to communicate with the destination node. In practice, source and destination nodes can be within range of each other's transmitters, but the necessary piconets just haven't been established yet.

Figure 7 illustrates an alternative embodiment of the present invention. As shown in the figure, after the source node does not successfully receive the timely REPLY message (such as according to the "No" path of decision step 615 in Fig. 6), immediately according to step 705, a new piconet is started by forming Route discovery process. But, if according to the "Yes" path of decision step 710, the REPLY message of responding to the original ROUTE REQUEST message is received before setting up the route through a new piconet, then even if the REPLY message is not in time, the source node can proceed as in step 715 As shown in , start transmitting the packet to the destination node through the route defined by the untimely REPLY message. This will continue following the "no" path of decision step 720 until a more efficient route is established through the newly formed piconet, or all packets have been transmitted to the destination node. Creation of new piconets

As explained above, the present invention allows new piconets to be established when routing attempts to find a route to a desired node. This occurs when a routing request on an existing piconet fails or the source node is not a member of any existing piconet.

In order to inform nodes to receive requests that they are allowed to establish new piconets, a specific request is required. This can be done by using a one-bit indication in the header of the REQUEST message packet. The request is special in the sense that it will inform other nodes that a new piconet can be established if they wish. Nodes receiving this request have some options. First, they can rebroadcast requests on existing piconets when piconet establishment occurs. When new piconets are created, requests will also be sent on these nets. This can happen serially, meaning that requests will be sent to each new piconet at the same rate that it was established. Second, they can form new piconets and then rebroadcast requests. Alternatively, they may be rebroadcasted only in existing piconets. The last item is needed because other BT units are not required to waste resources for another BT unit to establish a new piconet. A node can also decide for itself whether it is willing to accept piconet setups from other nodes (PAGE RESPONSE for PAGE).

The concept of a new piconet is formed when performing route discovery, which is in principle obtained in such a way that the source node can reach all other nodes in the network. If the destination is reachable at all, the source node will get a route to the destination.

The actual piconet establishment process means that the nodes (source node and node forwarding the request) must enter INQUIRY mode to scan the environment (other nodes must be in INQUIRY scan mode), that is, neighbor node discovery. A node will get multiple responses from neighboring nodes. A node can then make an informed decision about which nodes it will connect to and how the new piconet will be formed. Nodes can choose to create an entire new piconet or integrate with an existing piconet. This depends on how much information is available to the node. This can contain information such as piconet member addresses, which piconet nodes are able to forward packets, whether the node is a slave, master or both, and whether the node is a member of more than one piconet.

When a sensible decision is made, a node will actually connect by entering PAGE mode and sending PAGE packets to the node it wishes to connect to. By default it will be the master node of the new piconet, but can choose to be master-slave to change roles. A node will do so with all nodes it wishes to establish a piconet with. The result will be multiple new piconets and/or reorganization of already existing piconets. Higher protocol layer broadcast

The techniques described above will work as explained when the source node knows the destination BD_ADDR address. However, if used in conjunction with higher-layer protocol-level broadcasts (such as ARP and DHCP) that are handled by protocol layers above the NAL, and especially when combined with broadcast-triggered route discovery as described in co-pending U.S. Patent Application No. 09/455,460 There is a difference when used together. The main difference is that the destination address is a broadcast address rather than a specific node address. This means that the procedure described above will differ somewhat from that described below.

As before, the source node will first try to request on an existing piconet, but in this case, the broadcast data will be piggybacked in the route request packet and the message cached in the source node. Information must be cached to be able to request routing at a later time.

The timeout characteristics will also be somewhat different. If a route to this destination is not received within a preset time, a route request from a node with a known BD_ADDR address will time out. However this will not work in the broadcast case, since the routing request will not contain the specific destination BD_ADDR address, but the broadcast address. The solution is to always monitor the advanced broadcast at the source. The response to these broadcasts is a Routing Reply with piggybacked data (the Routing Reply will be a Piggybacking Routing Reply). If no piggyback routing acknowledgment is received, the source node may time out and initiate a routing request procedure allowing a new piconet to be formed.

However, there is still a problem to be solved with this solution, namely how to map a piggyback request with the correct piggyback reply. NAL is independent of higher level protocols and cannot use information from these layers. The problem is that in reality even the destination cannot map the correct request to the correct response. The solution to this is to allow only one piggybacked broadcast trigger routing request per node at a time. This means that nodes can easily map replies to the correct requests (one-to-one mapping). Such a solution would limit the number of broadcasts that are allowed to create new piconets. It must also be noted that it is not necessary to have multiple broadcasts creating piconets at the same time anyway. Alternatively, higher-level broadcasts can be disabled to build piconets, such as ordinary routing requests using only piggybacked data.

If no acknowledgment to piggyback data is received, a second phase is triggered, eg piggybacking broadcast data on a new routing request, but this time allowing piconet formation.

These kinds of higher-level broadcasts that are allowed to form new piconets must be limited in number, eg there must be a certain time interval to determine how often a node is able to do so. The reason is simply to limit the number of unnecessary broadcasts. There is no benefit in sending multiple broadcasts that are allowed to form a piconet if the time interval between broadcasts is too small. Data Packet Processing

When a routing protocol is searching for a route to route packets, what needs to be done with all data packets delivered to the routing protocol? There are essentially two options. First, packets can be buffered and then sent as soon as a reply with a valid route is received. The buffer will be limited in size and use the FIFO principle to determine which packets to discard when the buffer is full. Second, the packet may be dropped and higher layers such as TCP are allowed to process it.

This issue is important both for the case where the request message uses an existing piconet and for the case where a new piconet is established. The difference, however, is that the time scale is different in both cases. If a new piconet needs to be established it will take a long time to route.

In case a node uses the described broadcast mechanism, the node must cache data from higher layers, such as data piggybacked in the request. This is to ensure that the node can try the request again.

Although the main target of the invention is a Bluetooth scatternet, the invention is not limited to such a system. In general, the target system of the present invention is a digital packet based (wired or wireless) communication system comprising multiple networks. Each network consists of multiple nodes interconnected by point-to-point links. Forwarding in the network is performed at the network layer or at an adaptation layer between the link layer and the network layer, and is based on routing information included on the same respective layer. The routing protocol used in such systems is an on-demand protocol that finds routes on demand, using request and reply messages. The present invention provides the mechanism a node should employ when it wishes to be routed to a certain destination.

The two-step process can be summarized as follows. First, routing protocols are triggered when a node needs to route a packet to a destination node. The source node will flood the network with ROUTE REQUEST. The important aspect here is that the first routing request will only be flooded to nodes in the existing network. Nodes that are not part of any network will not receive messages. If the first routing request fails, the node will flood the network with new routing requests. This new routing request is special in the sense that it can connect new nodes to existing networks. Thus the source will obtain a route to the destination if the destination can be reached.

The invention has been described above with reference to several exemplary embodiments. However, it will be apparent that those skilled in the art will be able to implement the invention in specific forms other than the exemplary embodiment described above. This can be done without departing from the spirit of the invention. These exemplary embodiments are illustrative only and are not to be considered restrictive in any way. The scope of the invention is given by the appended claims rather than the foregoing description, and all changes and equivalents falling within the scope of the claims are intended to be embraced therein.

Claims (12)

1. In a telecommunications network, a method for establishing a route over which data packets are sent from a source node to a destination node, comprising the steps of: Request route discovery over existing network connections between source and destination nodes; determining whether the request for route discovery between a source node and a destination node failed over an existing network connection; and A route is established between the source node and the destination node by forming one or more new network connections if it is determined that the request for route discovery between the source node and the destination node failed over an existing network connection. 2. The method of claim 1, wherein said step of determining whether routing a discovery request between a source node and a destination node has failed over an existing network connection comprises the steps of: Determine whether the source node has received a timely reply in response to the route discovery request. 3. The method of claim 2, wherein said telecommunications network is an ad hoc network. 4. The method of claim 3, wherein said network is a Bluetooth technology-based network. 5. In a particular wireless telecommunication network comprising one or more existing subnetworks, a method for establishing a route between a source node and a destination node on which data packets are transmitted, said method comprising the steps of: If the source node is a member of one or more existing subnets, broadcast route discovery for a route between the source node and the destination node on one or more connections associated with one or more existing subnets request message; determining whether a timely reply message in response to the Broadcast Route Discovery Request message was received by the source node; and If it is determined that a timely reply message has not been received, a route between the source node and the destination node is established over one or more connections associated with the one or more newly formed subnetworks. 6. The method of claim 5 further comprising the steps of: If the source node is not a member of the one or more existing subnetworks, a route between the source node and the destination node is established over one or more connections associated with the one or more newly formed subnetworks. 7. The method of claim 5 further comprising the steps of: If the destination node is not a member of the one or more existing subnetworks, a route is established between the source node and the destination node over one or more connections associated with the one or more newly formed subnetworks. 8. The method of claim 5 further comprising the steps of: If it is determined that a timely reply in response to the route discovery request was received by the source node, then it is determined whether routes over one or more new connections associated with the one or more newly formed subnetworks are desired. 9. The method of claim 8 further comprising the steps of: If it is determined that a timely reply is received in response to the Route Discovery Request and it is determined that routes on one or more new connections associated with one or more newly formed subnets are not desired, then in conjunction with one or more Establishes a route between a source node and a destination node on one or more connections associated with an existing subnet. 10. The method of claim 8 further comprising the steps of: If it is determined that a timely reply is received in response to the Route Discovery Request and it is determined that routes on one or more new connections associated with one or more newly formed subnetworks are desired, then in connection with one or more establishes a route between the source node and the destination node on one or more connections associated with the existing subnet; and Route discovery is simultaneously initiated for a route between a source node and a destination node on one or more connections associated with one or more newly formed subnets. 11. The method of claim 5, wherein said particular wireless telecommunications network is a Bluetooth technology-based network. 12. The method of claim 11, wherein the existing and newly formed subnets are piconets.

Images