Title of Invention

SETUP OF A WIREBOUND NETWORK BY DETERMINING AND USING LOCAL TOPOLOGY INFORMATION

Abstract

When setting up a wirebound network consisting of several communication terminals, it is usual for said communication terminals to be devoid of information on local topology. In the large non-wirebound mobile environment networks it is advisable to create an independent large-network setup, wherein individual communication terminals which are not yet connected and/or partial networks are integrated. The aim of the invention is to provide a method enabling automatic dynamic, large-network organization, taking into account communication terminals which are not yet connected. According to Claim 1 of the invention, this is achieved by exchanging messages between the communication devices in order to determine local topology information independently and by integrating the thus enhanced isolated individual communication terminals and partial networks.

Full Text

Description The present invention relates to a method for setting up a non-wired network by determining and utilizing local topology information. The wire-based network topology for transmitting data between a plurality of communication devices is associated with loss of mobility and therefore loss of convenience. By contrast, network technology which is not wire-based allows data to be transmitted over short distances without being subject to limitations in terms of mobility. In addition to this, the communication devices can connect spontaneously and autonomously. In a first method, a first communication device initially receives a list specifying the further communication devices to which it can connect. By advancing progressively through the list or by means of manual manipulation, the first communication device decides which further communication device it should ask to set up a connection. In a second method (Specification *of the Bluetooth System, Version 1.2, Core) for setting up a non-wired network, a distinction relating to communication devices is made between a communication control device which is responsible for the control of the communication and a communication device which is controlled by the communication control device. Two communication control devices or two controlled communication devices cannot generally connect to each other. The number of communication devices which can be controlled by a communication control device can be limited by technical and/or administrative measures. If a communication control device can only control a limited number of communication devices, this means that the size of a network is restricted by the subscriber capacity of its communication control device. A larger number of communication devices can be achieved by combining individual networks to form a larger overall network. There are two possibilities for creating the required bridge connection between two communication control devices. One possibility is for a device to function as a communication control device in the first network and as a controlled communication device in the second network. Another possibility is to connect two communication control devices via a controlled communication device. Various network topologies can be obtained in this context, e.g. tree-type, chain-type or mesh-type topologies. In one implementation of a non-wired network according to the second method at the Technion - Israel Institute of Technology in Haifa, information indicating whether it is to operate as a communication control device or as a controlled communication device is required from each device when it starts. Various topologies can then be generated on the basis of the positioning and the sequence in which the devices are switched on (http://wwwcomnet. technion.ac.il/~cn9w02). Such a network having a tree topology has been set up at the ETH in Zurich (http://www.tik.ee.ethz.ch/~beutel/bt_node.html). The formation algorithm is not known in greater detail. This method has a disadvantage in that no information concerning the local topology of the network is available to a communication device desiring to set up a connection. As a consequence, it is possible that an individual communication device or whole subnetworks are not integrated into the overall network. Furthermore, the setup of a network can only be achieved statically and therefore does not satisfy the dynamic requirements in the case of non-wired transmission involving a plurality of communication devices. The present invention addresses the problem of specifying a method by means of which an overall network comprising a plurality of communication devices can organize itself, and individual communication devices and/or subnetworks which are not yet connected are included when this network is set up. This problem is solved by a method having the features specified in claim 1. Advantageous developments of the invention are specified in the dependent claims. An essential aspect of the invention is the determining of the local topology information. In accordance with the claimed method as per claim 1, this is achieved by means of a message exchange between the communication devices. To this end, a first communication device sends a query message containing a list of identification codes of further communication devices, to which a connection can be set up, to second communication devices which are connected to said first communication device. At least one second communication device, wherein a connection exists between the second communication device and one of the further communication devices identified in the query message and/or wherein said second communication device is itself a communication device identified in the query message, sends a reply message to the first communication device. From the reply message, it is possible to determine the identification codes of the further communication devices which are connected to the second communication device and/or to extract the identification code of the second communication device if this is itself a communication device identified in the query message. The first communication device requests the setting up of a connection to at least one further communication device which is identified in the query message and to which no connection exists from a second communication device. A successful request results in a connection setup. Without restricting the generality of this term, communication devices are understood to include PCs and computer peripheral devices, mobile devices (laptops, handheld PCs, PDAs), telecommunication devices (mobile phones, ISDN installations), video and TV devices, audio devices and domestic appliances (washing machines, refrigerators), for example. These devices can be networked using IrDA, Bluetooth or WLAN modules, for example. In accordance with a further advantageous embodiment of the present invention, the identification codes of the further communication devices which are identified in the query message and connected to the second communication device are listed in the reply message of the second communication device and/or the identification code of the second communication device is listed if the latter is itself a communication device from the query message. This requires less storage space and therefore ensures a faster and more efficient message exchange. The mesh size of a non-wired network is advantageously adjusted by a step size for the message exchange, wherein said step size defines the number of communication devices via which a query message is sent within a network topology. A mesh-type topology of the network emerges in this context. The bigger the step size, the coarser the mesh of the overall network. Mesh-type topologies have the advantage that they are less susceptible to failure than other topologies such as tree-type or chain-type topologies. If one route in a network fails, the option of a second possible route still remains. In the event of a failure of a device or a subnetwork, it is usually possible already to repair the overall network after the next message exchange of a participating communication device. An additional advantage of a mesh-type topology is the faster routing of data. As a result of the multiple possible routes for a connection between two devices, a smaller traffic load is produced on individual devices/routes. Furthermore, the routes between two devices are usually shorter as a result of meshing than in the case of a chain topology, for example. According to an advantageous development of the present invention, the local topology information is determined by means of a message exchange between the communication control devices. A first communication control device sends a query message containing a list of identification codes of further communication devices, to which a connection can be set up, via a communication device which is controlled by a communication control device, to second communication control devices which are connected to said controlled communication device. At least one second communication control device, wherein a connection exists between the second communication control device and one of the further communication devices identified in the query message and/or wherein said second communication control device is itself a communication device identified in the query message, sends a reply message to the first communication control device. From the reply message, it is possible to determine the identification codes of the further communication devices which are connected to the second communication control device and/or to extract the identification code of the second communication control device if this is itself a communication device identified in the query message. The first communication control device requests the setting up of a connection to at least one further communication device which is identified in the query message and to which no connection exists from a second communication control device. A successful request results in a connection setup. Without restricting the generality of this term, communication control devices are understood to include a master device in accordance with the Bluetooth communication protocol or a primary station in accordance with the IrDA protocol. Consequently, a controlled communication device corresponds to a slave device in accordance with the Bluetooth protocol and to a secondary station in accordance with the IrDA protocol. The present invention is explained below using an exemplary embodiment with reference to the drawing, in which: Figure 1 shows a schematic illustration of an exemplary network topology comprising a plurality of communication control devices and controlled communication devices, Figure 2 shows a schematic illustration of the network topology from Figure 1 after execution of the algorithm using the step size n=2, Figure 3 shows a schematic illustration of the network topology from Figure 1 after execution of the algorithm using the step size n=4. In the Figures 1-3, the six black colored circles symbolize the communication control devices and the fourteen white colored circles symbolize the controlled communication devices. In this configuration, it is not possible for two communication control devices or two controlled communication devices to connect to each other directly. A connection between two communication control devices is only possible via a communication device which, in this exemplary embodiment, can be connected to a maximum of two communication control devices. In general, it is possible to extend the number of communication control devices which can be connected via a controlled communication device. In the following exemplary embodiment, the controlled communication devices are designated simply as communication devices. The term devices is used as a generic term for communication control devices and controlled communication devices. Figure 1 shows a subnetwork comprising four communication control devices 1,2,3,5 and ten communication devices 7,8,9,10,11,15,16,17,18,19, a subnetwork which is not connected to this and comprises two communication control devices 4,6 and three communication devices 12,13,20, and one individual communication device 14. The drawn partial circle 22 graphically illustrates the transmission range of the communication control device 1. An unbroken line 21 symbolizes an existing connection between the devices, the example for the line 21 being a connection between the communication control device 1 and the communication device 15. As a first step, the communication control device 1 receives a list containing the identification codes of the devices 14,16,17,19,2,18,3,15,11,4,6,12,20,13 within its transmission range. The communication control device 1 firstly removes the identification codes of the communication devices 15 and 16, to which it is directly connected, from its list, which therefore contains the identification codes of the devices 14,17,19,2,18,3,11,4,6,12,20,13. The execution of the algorithm is considered once using the step size n=2 and once using the step size n=4. n=2: After the communication control device 1 has sent the list to the communication control devices which are connected to it within the step size n=2, it receives the reply message identifying the devices 3,18 from the communication control device 3. Following receipt of the message, the communication control device 1 deletes the identification codes cited in the reply message from its list, which consequently contains the identification codes of the devices 14,17,19,2,11,4,6,12,20,13. The communication control device 1 successfully sets up a connection to communication device 14. A new query message is now generated containing the identification codes of the devices 17,19,2,11,4,6,12,20,13. There is no reply message in the present example, because the communication device 14 does not have a connection to any communication control device other than communication control device 1. The communication control device 1 now sets up a connection to communication device 17, which is also successful. A new query message containing the identification codes of the following devices 19,2,11,4,6,12,20,13 is now generated and sent. The communication control device 1 receives a reply message containing the identification codes of the devices 2,19 from the communication control device 2. Following receipt of the message, the communication control device 1 deletes the identification codes cited in the reply message from its list, which consequently contains the identification codes of the devices 11,4,6,12,20,13. The communication control device 1 successfully sets up a connection to communication device 11. A new query message containing the identification codes of the devices 4,6,12,20,13 is now generated and sent. Although the communication device 11 is connected to the communication control device 5, the communication control device 1 does not receive a reply message from the communication control device 5 because none of the devices known to the communication control device 5 is included in the query message. The communication control device 1 now attempts to set up a connection to the communication control device 4, but this fails because the communication control device 4 is itself a communication control device. The communication control device 4 is deleted from the list. The attempt to set up a connection to the communication control device 6 fails for the same reason. The communication control device 6 is deleted from the list. The connection setup to the communication device 12 likewise fails because the communication device 12 is already connected to two communication control devices. The communication device 12 is deleted from the list. The communication control device 1 successfully sets up a connection to the communication device 20. A query message containing the identification code of the communication device 13 is now generated and sent. Although the communication device 13 is connected to the communication control device 6, the communication control device 1 does not receive a reply message from the communication control device 6, because the communication control device 1 did not request a device to which the communication control device 6 is directly connected or which the communication control device 6 itself is. The communication control device 1 successfully sets up a connection to the communication device 13. Communication device 13 is deleted from the list, which is consequently empty. The execution of the algorithm is therefore complete. Figure 2 shows the network topology from Figure 1 after the above-described algorithm using the step size n=2 has been executed. It is clear that the individual communication device 14 and the subnetwork including the devices 4,6,12,13,20 have been integrated into the network by the communication control device 1. n=4: After the communication control device 1 has sent the list to the communication control devices which are connected to it within the step size n=4, it receives the reply message containing the identification codes of the devices 3,18 from the communication control device 3, the reply message containing the identification codes of the devices 2,18,17,19 from the communication control device 2, and the reply message containing the identification code of the communication device 11 from the communication control device 5. Following receipt of the message, the communication control device 1 deletes the identification codes cited in the reply message from its list, which consequently contains the identification codes of the devices 14,4,6,12,20,13. The communication control device 1 successfully sets up a connection to communication device 14. A new query message containing the identification codes of the following devices 4,6,12,20,13 is now generated. There is no reply message, because the communication device 14 does not have a connection to any communication control device other than communication control device 1. 10 The communication control device 1 now attempts to set up a connection to the communication control device 4, but this fails because the communication control device 4 is itself a communication control device. The communication control device 4 is deleted from the list. The attempt to set up a connection to the communication control device 6 fails for the same reason. The communication control device 6 is deleted from the list. The connection setup to the communication device 12 likewise fails because the communication device 12 is already connected to two communication control devices. The communication device 12 is deleted from the list. The communication control device 1 successfully sets up a connection to the communication device 20. A query message containing the identification code of the communication device 13 is now generated and sent. Because the communication device 20 is connected to the communication control device 6 and because the step size n=4, whereby the communication control device 4 is also reached, communication control device 1 receives the reply message containing the identification code of the communication device 13 from the communication control device 4. Communication device 13 is deleted from the list, which is consequently empty. The execution of the algorithm is therefore complete. Figure 3 shows the network topology from Figure 1 after the above-described algorithm using the step size n=2 has been executed. It is clear that the individual communication device 14 and the subnetwork including the devices 4,6,12,13,20 have been integrated into the network by the communication control device 1. In comparison with Figure 2, it is also clear that a more coarsely meshed topology is produced by the algorithm using the larger step size n=4. The application of the present invention is not restricted to the exemplary embodiments described here. We Claim: 1. A method for setting up a non-wired network, between the communication devices comprising the following steps- - sending from a first communication device (1), a query message containing a list of identification codes of further communication devices (14,17,19, 2, 18,3,11,4,6,12,20,13), within a transmission range of the first communication device to which a connection can be set up, to second communication devices (14, 17, 19,2, 18,3, 11,4,6, 12,20, 13) which are connected to said first communication device, - sending a reply message to the first communication device (1) from at least one second communication device (3) if a connection exists between the second communication device (3) and one of the further communication devices (14, 17,19, 2,18, 3,11,4, 6,12, 20,13) identified in the query message and/or if the second communication device is a communication device (14, 17,19, 2,18, 3,11, 4, 6,12, 20,13) identified in the query message, - determining from the reply message, the identification codes of the further communication devices which are identified in the query message and are connected to the second communication device (3), and/or to extract the identification code of the second communication device (3) if this is itself a communication device (14, 17,19,2,11,4,6,12, 20, 13) which is identified in the query message, - requesting by the first communication device (1) setting up of a connection to at least one further communication device (14) which is identified in the query message and to which no connection exists from a second communication device (3), - resulting is a successful request in a connection setup. 2. A method as claim in claim 1, wherein the identification codes of the further communication devices (14, 17,19,2, 18, 3,11,4, 6,12, 20, 13) which are identified in the query message and are connected to the second communication device are listed in the reply message of the second communication device and/or the identification code of the second communication device (2) is listed in said reply message if this second communication device is itself a communication device from the query message. 3. A method as claim in claim 1, wherein the identification codes of the further communication devices (14, 17,19,2,18,3, 11,4, 6, 12, 20, 13) which are identified in the query message but are not connected to the second communication device are listed in the reply message of the second communication device (3) and/or the identification code of the second communication device (14, 17, 19,2,18, 3,11,4, 6,12,20,13) is listed in said reply message if this second communication device is not itself a communication device from the query message. 4. A method as claim in claim 1, in which a step size can be specified for the message exchange, wherein said step size defines the number of communication devices via which a query message is sent within a network topology. 5. A method as claim in claim 1, wherein first and second communication device (1, 3) correspond to a communication control device, a connection between communication control devices (1, 3) is set up via a communication device which is controlled by a communication control device (1, 3). 6. A method as claim in claim 1, wherein as defined in Bluetooth Core Specification Version 1.2 a communication control device (1, 3) corresponds to a master and a communication device which is controlled by a communication control device corresponds to a slave. 7. A method as claim in claim l,wherein first and second communication device {1, 3) correspond to a master, in the case of a connection between two masters, a communication device functions as both master and slave (master/slave bridge). 8. A method as claim in claim 1, wherein the identification code of devices corre- sponds to a Medium Access Control address.

Documents:

1049-delnp-2007-abstract.pdf

1049-DELNP-2007-Claims-(13-08-2012).pdf

1049-delnp-2007-claims.pdf

1049-DELNP-2007-Correspondence Others-(13-08-2012).pdf

1049-delnp-2007-correspondence-others-1.pdf

1049-DELNP-2007-Correspondence-Others.pdf

1049-delnp-2007-description (complete).pdf

1049-delnp-2007-drawings.pdf

1049-DELNP-2007-Form-1.pdf

1049-delnp-2007-form-18.pdf

1049-delnp-2007-form-2.pdf

1049-delnp-2007-form-26.pdf

1049-DELNP-2007-Form-3-(13-08-2012).pdf

1049-delnp-2007-form-3.pdf

1049-delnp-2007-form-5.pdf

1049-delnp-2007-pct-237.pdf

1049-delnp-2007-pct-notification.pdf

1049-DELNP-2007-Petition-137-(13-08-2012).pdf

abstract.jpg