GB2524797A

GB2524797A - A method of configuring devices of a communication system comprising a plurality of devices

Info

Publication number: GB2524797A
Application number: GB1405998.4A
Authority: GB
Inventors: Julien Sevin; Lionel Tocze; Pierre Visa; Pascal Lagrange
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 2014-04-03
Filing date: 2014-04-03
Publication date: 2015-10-07
Anticipated expiration: 2034-04-03
Also published as: GB201405998D0; GB2524797B

Abstract

A method of configuring devices of a communication system such as a personal area network, wherein each device has one or more possible communication links to directly communicate with another device, the method comprising: selecting an initial interconnection scheme having at least one alternative interconnection scheme, the initial scheme defining an initial configuration comprising, for each pair of devices, a communication link selected from among said possible communication links between the devices of the pair; determining, based on the initial interconnection scheme, a routing path from a source device to a destination device; wherein all key pairs of conflicting (interfering) links of an alternative configuration defined by the alternative interconnection scheme are also comprised in the initial configuration (a key pair being a pair of conflicting links, one of which is on the routing path). The method also comprises configuring the plurality of devices according to the initial configuration; and in case a communication link of the initial configuration becomes defective, reconfiguring the plurality of devices according to the alternative configuration while keeping the same determined routing path to transmit data from the source device to the destination device. The invention allows management of link deficiencies without re-computing the routing path and without the risk of new conflicts arising from the reconfiguration.

Description

A METHOD OF CONFIGURING DEVICES OF A COMMUNICATION SYSTEM

COMPRISING A PLURALITY OF DEVICES

FIELD OF THE INVENTION

The present invention relates in general to wireless communications and in particular to the configuration of devices of a communication system, allowing optimized management of wireless communication link deficiencies.

BACKGROUND OF THE INVENTION

Generally, a communication system, for instance a Personal Area Network, comprises several nodes. Each node is generally equipped with at least one communication module, either wired or wireless so that it may be linked with one or more other communication modules of other nodes.

Some applications, for example using HD image or video data, need data to be transmitted at a high data rate. To that end, high gain antennas, for example array antennas, may be used in the communication modules to achieve wireless communications with a high data rate. Such antennas may use beamforming techniques. They are typically steerable and can each generate a beam in a required direction. In a variant, several high gain antennas may be used for communicating in several directions.

Thanks to the good directivity of high gain antennas, several wireless communication links may exist between two communication modules, corresponding to different directions of the beams generated by the respective antennas, and that fulfil the requirements for data transmission, in terms of data rate and robustness.

In view of configuring the antennas for performing communications, the best wireless communication link is selected from among the several possible wireless communication links identified, for each pair of communication modules. Generally, the wireless communication link which is best adapted to wireless communications, in terms of data rate and robustness, is selected.

The identification of the possible wireless communication links, and the selection of the best one for each pair of communication modules that may communicate with each other are referred to as an antenna configuration process which is generally launched at the communication system initialization.

The set of links composed of the aforementioned selected links for each pair of communication modules defines an interconnection scheme of the communication system. Note that the interconnection scheme also includes the wired links between pairs of communication modules.

Thus, an interconnection scheme defines a configuration comprising, for each pair of communication modules, a communication link selected from among the possible communication link or links between the modules of said pair.

Even if high gain antennas are configured so that the signal energy is focused in particular directions, it may happen that, at the communication system level, two communication links between two pairs of communication modules interfere with each other. These two communication links may not be able to be simultaneously active without causing errors in the transmission of data.

The conflicts existing between the wireless communication links of the configuration defined by a given interconnection scheme may be identified during a process called conflicts identification process.

However, it is to be noted that such process identifies the conflicts existing between the wireless communication links of the configuration defined by a given interconnection scheme and not between all the possible wireless communication links of all the configurations defined by existing interconnection schemes.

Taking into account the conflicts existing between the wireless communication links of a considered configuration defined by an interconnection scheme, and given the capability of each link, a route of intermediary nodes, also called routing path, is chosen for each transmission of data between each pair of source and destination nodes. In particular, several routing paths may have to be determined when several concurrent transmissions are performed over the communication system, and conflicts may thus appear between links used for each concurrent transmission.

Thus, when considering the whole communication system, transmissions of data from the source nodes to the destination nodes require a double configuration phase: first, at the node level, a link is selected between each pair of antennas, thus defining a configuration of links, and then, at the system level, routes of intermediary nodes are determined between source nodes and destination nodes, based on the capabilities of the selected links and conflicts existing between the selected links of the configuration.

Generally speaking, wireless communications are known to be very sensitive to masking phenomena, in particular in the context of 60 3Hz wireless communications. Indeed, static or moving obstacles such as furniture, objects, human being may cut or disturb the communication link between two communication modules, and cause transmission errors.

Thus, when a wireless communication link is cut or disturbed, another wireless communication link between the communication modules is generally selected according to its robustness and data rate capability. The change of wireless communication link at the node level is known as an antenna control process.

Such a change of wireless communication link between two communication modules (and thus a change of interconnection scheme) may result in new conflicts between other links of the configuration defined by the new interconnection scheme that are involved in concurrent transmissions.

Consequently, the routing path as determined for the previous interconnection scheme may be out-of-date, since conflicting links may cause errors in the transmitted data, or data may not be received at all by the destination nodes.

A solution against such outdating may be to implement again a conflicts identification process for the new interconnection scheme, and to compute a new routing path in accordance with the new conflicts identified between the communication links of the new interconnection scheme.

However, re-processing conflicts identification and re-computing the routing path each time a new antenna control process is performed (i.e. each time a change of wireless communication link occurs between two communication modules, resulting in a change of interconnection scheme) may be very costly in terms of calculations and may result in an interruption in the transmission of data.

SUMMARY OF THE INVENTION

The present invention has been devised to address one or more of the foregoing concerns, with the aim of managing link deficiencies that may occur in a communication system.

In this context, according to a first aspect of the invention, there is provided a method of configuring devices of a communication system comprising a plurality of devices, wherein each device has one or more possible communication links to directly communicate with another device, the method comprising: selecting an initial interconnection scheme having at least one alternative interconnection scheme, the initial interconnection scheme defining an initial configuration comprising, for each pair of devices, a communication link selected from among said possible communication link or links between the devices of the pair; determining, based on the initial interconnection scheme, a routing path defining a route of intermediary devices to transmit data from a source device to a destination device; wherein all key pairs of conflicting links of an alternative configuration defined by the alternative interconnection scheme are also comprised in the initial configuration; a key pair of conflicting links is a pair of conflicting links, one of which being selected for a pair of intermediary devices of the routing path; and conflicting links are wireless communication links interfering with each other when data are simultaneously transmitted over these links; the method also comprising: configuring the plurality of devices according to the initial configuration; and in case a communication link of the initial configuration becomes defective, reconfiguring the plurality of devices according to the alternative configuration while keeping the same determined routing path to transmit data from the source device to the destination device.

Thus, the present invention allows management of the link deficiencies without systematically re-computing the routing path for transmitting data over the communication system, thus avoiding undesired interruptions in the transmission of data.

This is achieved thanks to the initial step of configuring the devices using an initial configuration defined by an initial interconnection scheme, which initial interconnection scheme has an alternative interconnection scheme, all key pairs of conflicting links of which being also comprised in the initial configuration defined by the initial interconnection scheme.

This is also achieved thanks to the use of an alternative configuration defined by the alternative interconnection scheme to replace the initial configuration defined by the initial interconnection scheme in case of link deficiency.

This is because since the alternative interconnection scheme defines an alternative configuration comprising key pairs of conflicting links already existing in the initial interconnection scheme, the same or less potential conflicts are likely to exist along the same routing path in case of reconfiguring the devices based on the alternative configuration.

Reconfiguring devices using the alternative configuration makes it possible to keep the same routing path without risking the occurrence of new conflicts between the communication links that are used in concurrent transmissions, if any, in this area, that would impact the routing path.

Optional features of the invention are further defined in the dependent appended claims.

In first embodiments, the method may comprise a preliminary step of grouping interconnection schemes into groups, each group having a reference interconnection scheme and one or more other interconnection schemes, wherein all the pairs or key pairs of conflicting links of a configuration defined by each other interconnection scheme of a group are also comprised in a reference configuration defined by the reference interconnection scheme of the group, wherein the alternative interconnection scheme is from a group for which the initial interconnection scheme is the reference interconnection scheme.

This preliminary step of grouping allows the efficiency of the whole method to be improved by grouping together interconnection schemes that does not incur new conflicts at least along the routing path, in comparison to the reference interconnection scheme. Indeed, in case of link deficiency, the alternative interconnection scheme defining the alternative configuration used to reconfigure the devices of the communication system can be merely selected from the group of the initial interconnection scheme, with the certainty that no new conflicts will appear between communication links at least along the determined routing path.

In particular, after such reconfiguration, if only key pairs of conflicting links are considered for the grouping, no new conflict is expected to occur along the routing path.

Advantageously, the groups based only on key pairs of conflicting links may be computed in a short time since only the links along the routing path are considered.

Otherwise, if all pairs of conflicting links are considered for the grouping, no new conflict is expected to occur anywhere in the system, after a reconfiguration based on an alternative interconnection scheme of the same group is conducted. A group may include sub-groups each having a reference interconnection scheme which is one of the other interconnection schemes of the group. Thus, a given sub-group having a given reference interconnection scheme comprises one or more other interconnection schemes, wherein all the pairs or key pairs of conflicting links of a configuration defined by each other interconnection scheme of the sub-group are also comprised in a reference configuration defined by the reference interconnection scheme of the sub-group. Correspondingly, a sub-group may also comprise itself smaller sub-groups defined accordingly, and so on. An alternative interconnection scheme is thus preferably selected as a new current interconnection scheme, from the reference interconnection schemes of the sub-groups, in order to directly have interconnection schemes alternative to this new current interconnection scheme.

In second embodiments, the method may comprise a preliminary step of grouping interconnection schemes into groups, wherein all interconnection schemes of a given group define configurations comprising exactly the same pairs or key pairs of conflicting links, if any.

In these second embodiments, the preliminary step of grouping allows the efficiency of the whole method to be improved by grouping together interconnection schemes that have a similar behaviour in terms of conflicts.

Indeed, no additional conflict will appear between the links at least along the routing path, when reconfiguring the devices based on the alternative interconnection scheme, since it belongs to the same group as the initial interconnection scheme and so comprises exactly the same conflicting links at least along the routing path.

In particular, if only key pairs of conflicting links are considered for the grouping, no new conflict is expected to occur along the routing path, and if all pairs of conflicting links are considered for the grouping, no new conflict is expected to occur anywhere in the system.

The routing path can be thus kept without increasing the risk of transmission errors due to conflicting links used to perform concurrent communications, if any.

These second embodiments are particularly advantageous since any interconnection scheme of a group may be used as an alternative interconnection scheme for any other interconnection scheme of the same group.

Advantageously, the groups based only on key pairs of conflicting links may comprise a larger number of interconnection schemes than the groups based on all pairs of conflicting links, therefore providing more alternative interconnection schemes in case of deficiency of communication links.

In some embodiments, the initial interconnection scheme is selected from a group comprising interconnection schemes defining configurations such that there are, in said group, different possible communication links for the largest number of pairs of devices. In variants, the initial interconnection scheme is selected from a group comprising interconnection schemes defining configurations such that there are, in said group, different possible communication links for the largest number of pairs of intermediary devices of the routing path.

These provisions are advantageous since the larger the number of pairs of devices having several alternative communication links to communicate with each other, the lower the risk of the routing path having to be modified on account of an isolated communication link becoming deficient.

In some embodiments, the initial interconnection scheme is selected from a group comprising the largest number of interconnection schemes.

Thus, the initial interconnection scheme has the largest possible number of alternative interconnection schemes. This may help decrease the necessity of re-computing a new routing path in case of successive link deficiencies, without, however, incurring significant transmission errors.

Preferably, the alternative configuration defined by the alternative interconnection scheme selected to reconfigure the plurality of devices comprises a possible communication link different from the deficient communication link for the same pair of devices.

In some embodiments, the initial interconnection scheme has a plurality of alternative interconnection schemes, and the alternative interconnection scheme is the one, among the plurality of alternative interconnection schemes, that defines a configuration comprising the largest number of communication links in common with the initial configuration.

Thanks to that provision, only few communication links have to be changed during the reconfiguration, which is thus performed in less time. Of course, this configuration may advantageously be combined with the selection of an alternative interconnection scheme which provides another possible communication link as an alternative to the deficient one.

At least parts of the method according to the invention may be computer implemented. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects which may all generally be referred to herein as a

B

"device" or "system". Furthermore, the present invention may take the form of a computer program product embodied in any tangible medium of expression having computer usable program code embodied in the medium.

Since the present invention can be implemented in software, the present invention can be embodied as computer readable code for provision to a programmable apparatus on any suitable carrier medium, for example a tangible carrier medium or a transient carrier medium. A tangible carrier medium may comprise a storage medium such as a floppy disk, a CD-ROM, a hard disk drive, a magnetic tape device or a solid state memory device and the like. A transient carrier medium may include a signal such as an electrical signal, an electronic signal, an optical signal, an acoustic signal, a magnetic signal or an electromagnetic signal, e.g. a microwave or RE signal.

According to a second aspect of the present invention, there is also provided a configuration module for configuring devices of a communication system comprising a plurality of devices, wherein each device has one or more possible communication links to directly communicate with another device, the configuration module comprising instructions to implement the following steps: sending a first control message for configuring the plurality of devices according to an initial configuration defined by an initial interconnection scheme, the initial interconnection scheme being selected so that it has at least one alternative interconnection scheme, the initial configuration comprising, for each pair of devices, a communication link selected from among said possible communication link or links between the devices of the pair; the first control message also indicating a routing path defining a route of intermediary devices for transmitting data from a source device to a destination device; wherein all key pairs of conflicting links of an alternative configuration defined by the alternative interconnection scheme are also comprised in the initial configuration; a key pair of conflicting links is a pair of conflicting links, one of which being selected for a pair of intermediary devices of the routing path; and conflicting links are wireless communication links interfering with each other when data are simultaneously transmitted over these links; and in case a communication link of the initial configuration becomes defective, sending a second control message for reconfiguring at least one device of the plurality of devices according to the alternative configuration while keeping the same determined routing path to transmit data from the source device to the destination device.

According to a third aspect of the present invention, there is provided a communication system comprising a plurality of devices wherein each device has one or more possible communication links to directly communicate with another device, the communication system comprising a configuration module as aforementioned.

The configuration module and the communication system present the same features and advantages as the corresponding method that they may implement.

The invention also concerns a communication system as hereinbefore described, with reference to, and as shown in, Figure 1 of the accompanying drawings.

The invention also concerns a configuration module as hereinbefore described, with reference to, and as shown in, Figure 2 of the accompanying drawings.

The invention also concerns a configuration method as hereinbefore described, with reference to, and as shown in, Figure 3 of the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the invention will now be described, by way of example only, and with reference to the following drawings in which: Figure 1 illustrates a communication system according to some embodiments; Figure 2 schematically represents an example of architecture for a communication device and/or a configuration module according to some embodiments; Figure 3 is a flowchart illustrating general steps of a configuration method according to some embodiments; Figure 4 illustrates a table of interconnection schemes that may be obtained during a configuration method according to some embodiments; Figure 5 illustrates a table of conflicts between wireless communication links of a configuration defined by a given interconnection scheme which may be obtained during a configuration method according to some embodiments.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

The invention provides a method and module for configuring devices of a communication system comprising a plurality of communication devices.

As described below with reference to several examples, a method according to the invention comprises a step of selecting an initial interconnection scheme defining an initial configuration comprising a communication link selected for each pair of devices of the communication system, when possible. Based on this initial interconnection scheme, it is determined a routing path defining a route of intermediary devices for transmitting data from a source device to a destination device.

In particular, the initial interconnection scheme is selected so as it has at least one alternative interconnection scheme.

The alternative interconnection scheme is an interconnection scheme defining an alternative configuration wherein all pairs of conflicting links, i.e. pairs of wireless communication link interfering with each other when data are simultaneously transmitted over these links, linking a pair of intermediary devices of the routing path, are also comprised in the initial configuration defined by the initial interconnection scheme. These pairs of conflicting links belonging to the routing path are named "key

pairs" in the remainder of the description.

The alternative interconnection scheme may thus define a configuration comprising exactly the same conflicting links along the routing path, as the initial interconnection scheme.

Or, in a variant, an alternative interconnection scheme may define a configuration comprising only some of the conflicting links of the initial configuration defined by the initial interconnection scheme along the routing path.

Thus, according to the method, the plurality of devices is configured according to the initial configuration defined by the initial interconnection scheme, which has the particularity to have at least one alternative interconnection scheme with the same or less conflicting links along the routing path.

Next, if a communication link of the initial interconnection scheme becomes defective, the plurality of devices is reconfigured according to the alternative configuration defined by the alternative interconnection scheme that has the same or only some of the conflicting links along the routing path as the initial interconnection scheme. This results in having no need to change the determined routing path for transmitting data from the source device to the destination device, since no new conflict are likely to appear along the routing path, i.e. in case of reconfiguration.

In case a concurrent communication is performed between another pair of source and destination devices, the risks of simultaneously transmitting data over links that interfere (i.e. conflicting links, one of which being between two intermediate devices of the routing path) are managed.

Such method takes into account the fact that two devices may be linked by one or more possible communication links, notably in the case of wireless communications, and the fact that in a given interconnection scheme, the communication links may entail conflicts, along the routing path or anywhere else.

According to the invention, link deficiencies are thus managed without incurring mandatory re-computation of the routing path despite a change of interconnection scheme.

This is because the alternative interconnection scheme used to reconfigure all or some of the devices comprise the same or only some of the conflicting links along the routing path, as the initial interconnection scheme used to initially configure the devices. This means that no new conflict would arise along the routing path when using the alternative interconnection scheme. The calculated routing path is thus still relevant.

In other words, according to the present invention, the initial interconnection scheme is chosen based on the ease of managing link deficiencies without incurring additional conflicts which would disturb the transmission of data and so impact the routing path. Instead, in the prior art, the initial interconnection scheme is chosen so that each link between devices offers the best data rate and the best robustness, regardless of the conflicts that may appear in case one of these links have to be changed due to a deficiency (e.g. cut link).

As described below, instead of considering only the key pairs of conflicting links to define an alternative interconnection scheme, the pairs of conflicting links regardless of their belonging to the routing path may be considered.

For the remainder of the description, the expressions "interconnection scheme" and "configuration" are used indifferently to designate the set of selected links thus forming a meshed network between the devices of the system.

Figure 1 illustrates an example of a communication system 100, according to possible embodiments of the present invention.

The communication system 100 comprises a plurality of devices (also called nodes), here six devices 110, 120, 130, 140, 150 and 160.

Generally, each device comprises at least one communication module to communicate with another device equipped correspondingly.

For instance, in the example of Figure 1, device 110 comprises communication modules 111 and 112, and device 120 comprises communication modules 121 and 122. Device 110 can thus communicate with device 120 using their respective communication modules 111 and 121. Device 110 can also communicate with device 140 using their respective communication modules 112 and 141.

Also, devices 120 and 130 can communicate with each other using modules 122 and 132, devices 130 and 140 using modules 132 and 161, devices 140 and 150 using modules 142 and 151, and devices 150 and 160 can communicate with each other using modules 152 and 162.

The aforementioned communications may be either wireless or wired communications, depending on the types of communication modules engaged in the communications.

In particular, a given pair of communication modules for wired communications may be equipped with an Ethernet port and linked by an Ethernet cable. In a variant, they may be equipped with USB ports.

In the example of Figure 1, links 115, 116, 135 and 155 between respectively devices 110 and 120, 110 and 140, 130 and 160, and devices 150 and 160, are wired links.

Another pair of communication modules for wireless communications may be equipped with one or more antennas, preferably high gain antennas. Such antennas allow several wireless communication links to be established between a pair of communication modules.

High gain antennas may use beamforming techniques. According to these techniques, each radiating element of each antenna is electronically controlled in phase and power to form a steering (advantageously in two dimensions) and varyingly narrow beam (i.e. width of antenna main lobe).

In addition, such antennas are generally steerable in order to generate a beam in a required direction. In other words, the antenna parameters (e.g weighting coefficients associated with the elements of an antenna array) are controlled such that the radiation pattern, in case of emission, or the antenna sensitivity pattern, in case of reception, is accentuated in a given direction relatively to other directions.

Such antennas may transmit a signal via a single narrow main beam with an angle equals to 5 degrees when measured at -3dBi from the maximum, where "dBi" represents a measure of antenna gain relative to an isotropic antenna. The main beam gain may thus be relatively high, for example 25 dBi. The antenna has thus different gain characteristics at different reception angles. A maximum gain is obtained in the direction of the main beam.

Often, it is not possible to cover all directions even with a single antenna having a wide beam. In order to overcome this issue, complementary antennas may be used in the same device, each one covering some of the directions. For instance, in a case wherein a device comprises two antennas, the first antenna covers the directions between 0 and 180 degrees and the second antenna covers the directions between 181 and 360 degrees. Consequently, when a device has to send data towards a given direction, it may select the antenna which covers it.

A wireless communication between two communication modules may be operated in the 5 GHz unlicensed spectrum, or in the 2.4 GHz unlicensed spectrum, or in the 57-66 GHz millimeter-wave unlicensed spectrum. In this last case in particular, several possible wireless communication links may be established between two wireless communication modules, as explained above.

Back to the example of Figure 1, devices 120 and 130 may be equipped with wireless communication modules (e.g. high gain antennas) so that they may communicate using one of the possible wireless communication links 125, 126 or 127.

Similarly, devices 140 and 150 may be correspondingly equipped to communicate together using one of the possible wireless communication links 145, 146, or 147.

Figure 2 schematically represents an example of architecture 200 for a communication device, for instance the devices 100-160 in Figure 1, or for a communication module according to some embodiments.

Such configuration module is adapted to implement a configuration method according to some embodiments of the present invention and may be included in any device of the communication system 100.

In a variant, the configuration module may be an independent device, for instance a programmable computing machine, such as a PC (Personal Computer'), a DSP ("Digital Signal Processor"), a microcontroller, an FPGA ("Field-Programmable Gate Array"), an ASIC ("Application-Specific Integrated Circuit"), or a workstation or a light portable device.

In this case, the configuration module and the devices of communication system 100 comprise specific means for exchanging configuration messages and commands. These means allow robust communications to be performed while having a lower rate than the communications performed between the devices of the communication system 100. To that end, a specific modulation/demodulation scheme may be used for these communications.

Back to the example of Figure 2, the architecture 200 may comprise a communication bus connected to: -a central processing unit 201, such as a microprocessor, denoted CPU; -a random access memory 202, denoted RAM, of which the capacity may be expanded by an optional RAM connected to an expansion port for example; -a read only memory 203, denoted ROM, for storing computer programs for implementing embodiments of the invention; -a communication module 204, which is typically connected to the communication system 100 over which data to be processed are transmitted or received. The communication module 204 can be a single network interface, or composed of a set of different network interfaces (for instance wired and wireless interfaces, or different kinds of wired or wireless interfaces). The wireless interface integrates for instance one or more high gain antennas as described with reference to Figure 1. Data packets are written to the network interface for transmission or are read from the network interface for reception under the control of the software application running in the CPU 201; -a user interface 205 for receiving inputs from a user or to display information to a user; -a hard disk 206 denoted HD; -an input/output I/O module 207 for receiving/sending data from/to external devices such as a video source or a display.

The central processing unit 201 is adapted to control and direct the execution of the instructions or portions of software code of the program or programs according to the invention. On powering up, the program or programs that may be stored in a non-volatile memory, for example in the read only memory 203, may be then transferred into the random access memory 202, which then contains the executable code of the program or programs, as well as registers for storing the variables and parameters necessary for implementing the invention (e.g. table of interconnection schemes, groups, tables of conflicts, routing path and routing scheme, as they will be described hereafter).

The executable code may also be stored in read only memory 203, or on the hard disk 206 or on a removable digital medium for example such as a disk.

According to a variant, the executable code of the programs can be received by means of a communication network, for instance via the communication module 204, in order to be stored in one of the storage means of the device, such as the hard disk 206, before being executed.

Figure 3 is a flowchart illustrating general steps of a configuration method according to some embodiments. These steps may be implemented in a configuration module, as described with reference to Figure 2.

The configuration method an example of which is described below aims at configuring the devices of a communication system as described with reference to Figure 1.

In these embodiments of Figure 3, all the conflicting links (thus including the key pairs) are considered to determine the initial configuration of the devices, and not only the key pairs of conflicting links.

At preliminary step 300, an initial interconnection scheme is selected which defines an initial configuration comprising, for each pair of devices, a communication link selected from the possible communication link or links available for the pair.

In practice, at the communication system initialization, all possible links that may exist between each pair of devices of the communication system, and more precisely, between each pair of communication modules, are identified during a discovety phase.

In particular, during a discovery time slot, for each communication module equipped for wireless communications, a discovery message with a given PHY configuration (modulation and coding scheme) of the antenna is transmitted by the communication module in transmission mode.

During this discovery time slot, the other communication modules are in reception mode and measure a reception quality as the Signal Noise Ratio (SNR), the Radio Signal Strength Indication (RSSl) or additional information such as a Cyclic Redundancy Check (CRC) contained in the received discovery packet.

Next, a predetermined condition is checked (whether RSSI/SNR is more than a predetermined radio threshold or not, CRC OK or NOK) to consider whether there exists a wireless communication link between the pair of communication modules.

In case of directional antennas, an exhaustive discovery protocol is used, which tests all the directions with different PHY characteristics (modulation and coding scheme) since several wireless communication links can be found.

Basically, a discovery message is sent in each direction for the transmitting and receiving communication modules. At the end of the discovery phase, a set of L wireless communication links can be found (each one corresponding to a direction for the transmitting communication module and the receiving communication module) for each pair of communication modules i. They can be ordered according to a channel assessment (RSSI for instance).

Next, a table of interconnection schemes, as shown in Figure 4, is computed. In this table 400, a row 410 corresponds to an interconnection scheme and a column 420 corresponds to a pair of devices. Not all pairs of communication modules are in table 400. Indeed, only the pairs of communication modules that have at least one possible communication link (wired and/or wireless) to communicate with each other appear in the table. In the example of Figure 4, there is a number p of pairs of devices that are linked by at least one possible communication link.

As explained above, each interconnection scheme (i.e. each line 410 in the table of Figure 4) defines a configuration that corresponds to the selection of one link for each pair i of communication modules (or devices). The selected link corresponds to an element 430 of table 400. In case of a wired link, there is only one possibility and a default value is attributed (0 for instance). A wireless communication link is selected from amongst the L possible links found during the discovery phase. Thus, in the table 400, a number between 1 and L is used to designate one specific link among the L possible wireless communication links.

One may note that several interconnection schemes (configurations) exist for a given communication system when at least one pair of communication modules has more than one possible communication link to communicate.

Generally speaking, a communication system comprising p pairs of communication modules with each pair i having L possible communication links (wired or wireless) has a number N of different interconnection schemes (configurations) which is equal to N=Li*L2*L3. .. .. Lp* All these interconnection schemes (configurations) constitute the rows of table 400.

In the communication systeni example of Figure 1, the number of different interconnection schemes is equal to N=1*3*1*1*1*3*1 = 9. In particular, the following sets of links define the different interconnection schemes (configurations) of the communication system 100: -{115, 125, 135, 116, 145, 155} -{115, 125, 135, 116, 146, 155} -{115, 125, 135, 116, 147, 155} -{115, 126, 135, 116, 145, 155} -{115, 126, 135, 116, 146, 155} -{115, 126, 135, 116, 147, 155} -{115, 127, 135, 116, 145, 155} -{115, 127, 135, 116, 146, 155} -{115, 127, 135, 116, 147, 155}.

Once table 400 of interconnection schemes (configurations) has been computed, pairs of links that interfere with each other during concurrent simultaneous communications, are identified in each configuration during a conflicts identification process as described above. In particular, for each interconnection scheme (configuration), a table of conflicting links may be computed, an example of which is shown on Figure 5. It is to be noted that only wireless communication links may interfere.

Table 500, referred to as C=(c)?l, stores the conflicts between the pairs of wireless communication modules; a row k and a column n correspond respectively to the pairs of wireless communication modules (tx_modk,rx_modk) and (tx_mod,rx_mod) as configured in the interconnection scheme considered. Each element of table 500 ckfl has a value of 1 if there is a conflict between the two wireless communication links corresponding to (tx_modk,rx_modk) and (tx_mod,rx_mod) and 0 otherwise. Its value is determined by the conflict identification process described above.

When considering two pairs of communication modules referred to as (tx_mod1, rx_mod1) and (tx_mod2, rx_mod2) which are linked respectively by wireless communication links l and 12, to determine if there is a conflict between wireless communication links l and 12, two discovery messages m1 and m2 are generated and sent simultaneously. For example, message m1 is sent by communication module tx_mod1 and message m2 is sent by communication module tx_mod2.

Each message contains a specified pattern, Pi for m1 and P2 for m2. On reception, communication module rx_mod1 checks if the pattern Pi of m1 has been well received (for instance without error). Respectively, communication module rx_mod2 checks if the pattern P2 of m2 has been well received (for instance without error). If the check is positive for communication module rx_mod1 and communication module rx_mod2, the two wireless communication links l and 12 are considered not in conflict.

Otherwise, the two wireless communication links are considered in conflict.

For each interconnection scheme (configuration) of table 400, a table similar to Table 500 is completed based on the principle just described.

One may note that to reduce computation costs, the result of the conflicts identification process for a configuration can be directly reused for another configuration; in particular for the pairs of communication links they have in common.

Thus, only N occurrences of the conflicts identification process are required for the whole set of interconnection schemes.

Once all the conflict tables 500 have been computed, it may be checked, for a given interconnection scheme (configuration), whether there is another interconnection scheme (configuration) having the same conflicts as the given interconnection scheme, or less conflicts than the given interconnection scheme but all of them being also conflicts of the given interconnection scheme.

This other interconnection scheme is called alternative interconnection scheme according to the meaning of the invention because the two interconnection schemes defines configurations that have the same or less conflicting links (for one of them in comparison with the other taken as a reference). One may note that consequently all the conflicting links along any routing path in the alternative interconnection scheme are also conflicting links in the given interconnection scheme, thus ensuring the same routing path to be kept when switching from the given interconnection scheme to the alternative interconnection scheme. The given interconnection scheme could thus be used as an initial interconnection scheme in the meaning of the invention.

In this example, all the conflicting pairs of links as set forth in table 500 are considered. In other words, it is checked whether there is another interconnection scheme having the same conflicting links as the given interconnection scheme (in such a case, the given interconnection scheme and the other, i.e. alternative, interconnection scheme have exactly the same conflict table 500), or less conflicting links but all being also conflicting links of the given interconnection scheme.

The given interconnection scheme may be selected at step 300 to become the aforementioned initial interconnection scheme, since it has an alternative interconnection scheme as defined above.

In this approach, the first interconnection scheme encountered that has an alternative interconnection scheme may be selected. However, plenty of candidates for the initial interconnection scheme may exist and thus an efficient selection thereof may be implemented.

In some embodiments, the selection of the initial interconnection scheme at step 300 may comprise a preliminary step of grouping all the interconnection schemes based on the similarity of their respective conflict tables 500. Such groups make it easier to select efficiently an initial interconnection scheme and to find alternative interconnection schemes when link deficiencies occur.

Each group may comprise all the interconnection schemes that have exactly the same conflict table 500, in which case the groups are disjoint (i.e. separate) one from each other.

Thus, all the interconnection schemes of a given group have exactly the same behaviour in terms of conflicts, and so they may be inter-changed without any consequence (in terms of conflicts) on the concurrent communications.

In some other embodiments, the selection of the initial interconnection scheme at step 300 may comprise another kind of preliminary step of grouping interconnection schemes into groups.

According to these embodiments, each group is first defined with a reference interconnection scheme and one or more other interconnection schemes are added to the group depending on the reference interconnection scheme.

For example, any other interconnection scheme is added to a group if all the pairs of conflicting links of the configuration defined by this other interconnection scheme are also comprised in the reference configuration defined by the reference interconnection scheme of the group.

This results in having groups that may overlap, since the same interconnection scheme (e.g. an interconnection scheme without any conflicting links) may be alternative to two or more reference interconnection schemes (e.g. if the reference interconnection scheme has at least one pair of conflicting links).

Note that the reference interconnection schemes may be initially determined as a subset of all the possible interconnection schemes. However, all the possible interconnection schemes may also be used as reference interconnection schemes.

In these embodiments, a reference interconnection scheme is thus selected as the initial interconnection scheme for the configuring method of the invention and the alternative interconnection scheme is selected from the same group, i.e. from the group for which the initial interconnection scheme is the reference interconnection scheme.

In some embodiments, the initial interconnection scheme may be selected in the group having the largest number of interconnection schemes.

Thus, the initial interconnection scheme has the largest possible number of alternative interconnection schemes and this may help decrease the necessity of re-computing new routing path in case of successive link deficiencies (this will be described in detail below), without, however, incurring important transmission errors.

A main group may include sub-groups each having a reference interconnection scheme which is one of the other interconnection schemes of the main group, each sub-groups being built as described below with reference to groups. Such situation occurs for example when all the interconnection schemes are used as reference interconnection scheme. This is because the group for any interconnection scheme alternative to a first interconnection scheme, has to be considered as a sub-group in the group generated from the first interconnection scheme.

With groups and sub-groups, the initial interconnection scheme may be selected in the group having the largest number of sub-groups and/or the larger number of sub-group levels to further reduce the risks to compute new routing paths.

In some embodiments, the initial interconnection scheme may be selected in the group having interconnection schemes that define configurations such that there are, in said group, different possible communication links (wired or wireless) for the largest number of pairs of devices, i.e., in the group having the best robustness R, R being defined as follows: R = wherein R is a robustness variable for each pair i of communication modules.

For instance, ft is equal to 1 if there are different wireless communication links set for the same pair i, of devices by the interconnection schemes of the group.

Otherwise, R is equal to 0.

In a variant, R1 is equal to the number of different wireless communication links set for the same pair i, of devices by the interconnection schemes of the group.

Otherwise, R is equal to 0. Other variants may exist.

One may note that the larger the number of pairs of devices having several alternative communication links to communicate with each other, the less the risk of an isolated communication link becoming deficient requiring the routing path to be modified. This is why it may be advantageous to take this criterion into account when selecting the initial interconnection scheme.

In some embodiments, once the group has been selected, the initial interconnection scheme may be chosen so that it has the larger number of alternative interconnection schemes in the group with a maximum of links in common with the initial interconnection scheme.

This optional grouping of interconnection schemes and subsequent selection of the initial interconnection scheme as described above allows the efficiency of the whole configuration method to be improved, since, in case of link deficiency (this case will be described in detail below), the devices are reconfigured using an alternative interconnection scheme selected from the group of the initial interconnection scheme, thus ensuring that no new conflicts, in particular along the routing path, will arise. No negative impact is thus expected to appear when concurrent simultaneous transmissions of data are performed.

Back to Figure 3, once the initial interconnection scheme has been selected at step 300, a routing path is determined (step 310) in order to set a route of intermediary devices for the transmission of data between a source device S and a destination device D. The determination of a given routing path is described in detail below, and the determination of other routing paths for concurrent transmissions, if any, is similar Obviously, the present invention is not limited thereto and in practice, two or more routing paths may be determined to achieve concurrent simultaneous transmissions of data between pairs of source and destination devices, over the communication system. This is why taking into account potential conflicts between wireless communication links is very important when selecting an interconnection scheme.

For illustrative purposes only, in communication system 100 of Figure 1, a routing path for transmitting data from the source device S (110) to the destination device D (160) may be composed of devices 110, 120, 130 and 160. Another routing path may be composed of devices 110, 140, 150 and 160.

Back to the general case, fora communication i, a routing path p starts with a source device s, ends with a destination device d and comprises between these two devices a list of intermediate devices. The set of routing paths for all communications performed over a communication system is called routing scheme.

In practice, the routing scheme may be determined as a solution to a multi-commodity flow (MCF) problem. As known by the person skilled in the art, such a problem is a function of a given configuration (interconnection scheme) with its pairs of conflicting communication links, a list of communications to be performed, and one or more objective variables among bandwidth, robustness, and latency to maximize or minimize depending on the objective variable.

Determining the routing scheme thus consists of finding a compromise between the capacities of the links of the configuration (interconnection scheme) and the flow demand due to several simultaneous communications, interferences that may arise due to competing communications, given the objective variable to maximize or minimize.

This is why taking ease of finding an alternative configuration with similar conflicts around the routing path into account in the choice of the initial interconnection scheme is important since the routing path and the routing scheme depend directly on these conflicts.

Once the routing path has been determined at step 310, both initial interconnection scheme and determined routing path are sent in a control message to all the devices of the communication system. Each of the devices then configures itself (step 320) according to the initial configuration defined by the initial interconnection scheme in the received control message, and stores the routing path it may belong to as an intermediary node, in order to manage the routing of data packet to linked devices.

In practice, step 320 comprises the configuration of antennas of the devices, for example by setting the desired direction for performing wireless communications with a given device and thus establishing a wireless communication link as indicated in the interconnection scheme of the control message. The transmission of data from the source device to the destination device can now begin.

One of the devices of the communication system 100 may encounter difficulty in communicating with one of the linked devices, for instance because of a link-cut due to a physical obstacle disturbing a wireless communication link, or because of an unplugged wire.

Such a problem may be detected either by a communication module in transmission mode for example when not receiving an acknowledgement in response to the sending of a packet of data, or by a communication module in reception mode for example when the reception of packets is interrupted before the last packet is received.

Once a link deficiency has been detected, it is checked (step 330) whether there is an alternative interconnection scheme as described above.

One may note that when a first link deficiency since the beginning of the transmission of data is detected, there is necessarily an alternative interconnection scheme since the initial interconnection scheme has been selected so that it has at least one alternative interconnection scheme.

Thus, if an alternative interconnection scheme is found, it is selected at step 340.

It may happen that several alternative interconnection schemes are found.

In such a case, the interconnection scheme having the largest number of selected communication links in common with the initial interconnection scheme may be selected.

Next, the selected alternative interconnection scheme is sent to the devices of the communication system in order to reconfigure the devices with the alternative configuration defined by the selected alternative interconnection scheme during a new step of configuration 320.

In some embodiments, during this new step of configuration, the control message comprising the selected alternative interconnection scheme is sent to all the wireless communication modules of the communication system.

In other embodiments, this control message is sent only to the wireless communication modules for which the corresponding wireless communication links are to be changed between the current interconnection scheme (here the initial interconnection scheme) and the selected alternative interconnection scheme to be applied.

In practice, the control message is sent over another channel more robust and with a lower rate than the links used for the transmission of data over the communication system. This is to make sure that the control message will be received by the corresponding devices despite the broken link.

Next, the method may continue with step 330, without re-computing the routing path and thus the routing scheme, since the alternative interconnection scheme has no new conflicts, in particular along the routing path, in comparison to the initial interconnection scheme.

It is thus possible to keep the same routing path (the same routing scheme) even if it was determined based on the initial interconnection scheme which is different from the alternative interconnection scheme, without risking the occurrence of new conflicts between the communication links used in concurrent transmissions.

Another advantage is that the computing time due to recalculation of the routing path (and thus of the routing scheme) and thus the interruption of data transmission due to the reconfiguration of devices are thus reduced.

If there is no alternative interconnection scheme, for example because all the alternative interconnection schemes have been used already for previous reconfigurations of the devices due to link deficiencies, a new interconnection scheme is selected, which is not an alternative interconnection scheme according to the meaning of the invention, i.e. from another group than the group of the initial interconnection scheme.

The new interconnection scheme may be selected based on the same criteria used to select the initial interconnection scheme at step 300. For instance, it may be selected from the group having the largest number of interconnection schemes, the group of the initial interconnection scheme being excluded.

In a variant, the new interconnection scheme may be selected from the group having interconnection schemes that group together different possible communication links (wired or wireless) for the largest number of pairs of devices, i.e., that have the best robustness R as defined above, the group of the initial interconnection scheme being excluded.

In some embodiments, once the group has been selected, the new interconnection scheme may be chosen so that it has the largest number of alternative interconnection schemes in the group with a maximum of links in common with the new interconnection scheme. Advantageously, the number of antennas to be reconfigured is reduced.

In any case, the new interconnection scheme has one or more alternative interconnection scheme(s), as defined above for the initial interconnection scheme.

The routing path may be out-of-date and new conflicts may arise between the links used for concurrent communications, and may thus disturb concurrent transmissions of data over the communication system. Consequently, a new routing path (i.e. a new routing scheme) is computed during a new step 310, based on the new interconnection scheme.

Next, the method may continue as if the initial interconnection scheme was the new interconnection scheme, with steps 320 and the following steps described above.

In particular, a new control message is sent to all the devices of the communication system so that they can reconfigure their antennas, if any, according to the new interconnection scheme, and so that concurrent and simultaneous transmissions of data may be performed using the new routing path (and new routing scheme) determined based on the new interconnection scheme.

Thus, the present invention relies on the selection of interconnection schemes in a way that the probability, in case of link deficiency, of finding another interconnection scheme with a similar behaviour in terms of conflicts, is increased.

In the examples used above to describe Figure 3, all the conflicting links (including the key pairs) are considered rather than the key pairs of conflicting links only. This approach advantageously separates the determination 300 of the initial interconnection scheme from the determination 310 of a corresponding routing path/scheme.

However, to increase the size of the groups from where the interconnection schemes (including the initial one) are selected, the process of Figure 3 may involve considering only the key pairs of conflicting links. As a consequence, a higher number of alternative interconnection schemes are available for a given initial interconnection scheme, thus reducing the risks to have to compute a new routing path in case of link deficiencies.

It is recalled that the key pairs of conflicting links are those pairs of conflicting links, one link of which being selected for a pair of intermediary devices of the routing path. They define key' conflicts that may occur along the routing path determined for a given interconnection scheme.

The embodiments considering the key pairs of conflicting links only require that the routing path is known earlier in the process.

The key pair approach may be applied to the two mechanisms for grouping interconnection schemes as described above. Thus a first type of grouping is performed by considering exactly the same key pairs of conflicting links between interconnection schemes as defined in their respective tables 500, while a second type of grouping is performed by considering less key pairs of conflicting links compared to a reference interconnection scheme (but all comprised in the reference configuration).

For example, step 300 of determining the initial interconnection scheme may include the determination of the routing path/scheme for each first interconnection scheme defining a new group (e.g. for each new interconnection scheme that cannot be added to an existing group when considering exactly the same key pairs between schemes, or for each reference interconnection scheme as defined above). Such determination can be performed in a similar way as described above for step 310, in which case the resulting routing path/scheme is associated with the group. Thus, when an initial interconnection scheme is selected from one group, step 310 only consists in retrieving the routing path/scheme associated with the group.

Although the present invention has been described hereinabove with reference to specific embodiments, the present invention is not limited to the specific embodiments, and modifications which lie within the scope of the present invention will be apparent to a person skilled in the art. Many further modifications and variations will suggest themselves to those versed in the art upon making reference to the foregoing illustrative embodiments, which are given by way of example only and which are not intended to limit the scope of the invention as determined by the appended claims. In particular different features from different embodiments may be interchanged, where appropriate.

Claims

CLAIMS1. A method of configuring devices of a communication system comprising a plurality of devices, wherein each device has one or more possible communication links to directly communicate with another device, the method comprising: selecting an initial interconnection scheme having at least one alternative interconnection scheme, the initial interconnection scheme defining an initial configuration comprising, for each pair of devices, a communication link selected from among said possible communication link or links between the devices of the pair; determining, based on the initial interconnection scheme, a routing path defining a route of intermediary devices to transmit data from a source device to a destination device; wherein all key pairs of conflicting links of an alternative configuration defined by the alternative interconnection scheme are also comprised in the initial configuration; a key pair of conflicting links is a pair of conflicting links, one of which being selected for a pair of intermediary devices of the routing path; and conflicting links are wireless communication links interfering with each other when data are simultaneously transmitted over these links; the method also comprising: configuring the plurality of devices according to the initial configuration; and in case a communication link of the initial configuration becomes defective, reconfiguring the plurality of devices according to the alternative configuration while keeping the same determined routing path to transmit data from the source device to the destination device.
2. The method of claim 1, also comprising a preliminary step of grouping interconnection schemes into groups, each group having a reference interconnection scheme and one or more other interconnection schemes, wherein all the pairs or key pairs of conflicting links of a configuration defined by each other interconnection scheme of a group are also comprised in a reference configuration defined by the reference interconnection scheme of the group, wherein the alternative interconnection scheme is from a group for which the initial interconnection scheme is the reference interconnection scheme.
3. The method of claim 1, also comprising a preliminary step of grouping interconnection schemes into groups, wherein all interconnection schemes of a given group define configurations comprising exactly the same pairs or key pairs of conflicting links, if any.
4. The method of claim 2 or 3, wherein the initial interconnection scheme is selected from a group comprising interconnection schemes defining configurations such that there are, in said group, different possible communication links for the largest number of pairs of devices.
5. The method of claim 2 or 3, wherein the initial interconnection scheme is selected from a group comprising interconnection schemes defining configurations such that there are, in said group, different possible communication links for the largest number of pairs of intermediary devices of the routing path.
6. The method of claim 3, wherein the initial interconnection scheme is selected from a group comprising the largest number of interconnection schemes.
7. The method of any one of claims 1 to 6, wherein the initial interconnection scheme has a plurality of alternative interconnection schemes, and the alternative interconnection scheme is the one, among the plurality of alternative interconnection schemes, that defines a configuration comprising the largest number of communication links in common with the initial configuration.
8. A configuration module for configuring devices of a communication system comprising a plurality of devices, wherein each device has one or more possible communication links to directly communicate with another device, the configuration module comprising instructions to implement the following steps: sending a first control message for configuring the plurality of devices according to an initial configuration defined by an initial interconnection scheme, the initial interconnection scheme being selected so that it has at least one alternative interconnection scheme, the initial configuration comprising, for each pair of devices, a communication link selected from among said possible communication link or links between the devices of the pair; the first control message also indicating a routing path defining a route of intermediary devices for transmitting data from a source device to a destination device; wherein all key pairs of conflicting links of an alternative configuration defined by the alternative interconnection scheme are also comprised in the initial configuration; a key pair of conflicting links is a pair of conflicting links, one of which being selected for a pair of intermediary devices of the routing path; and conflicting links are wireless communication links interfering with each other when data are simultaneously transmitted over these links; and in case a communication link of the initial configuration becomes defective, sending a second control message for reconfiguring at least one device of the plurality of devices according to the alternative configuration while keeping the same determined routing path to transmit data from the source device to the destination device.
9. A communication system comprising a plurality of devices wherein each device has one or more possible communication links to directly communicate with another device, the communication system comprising a configuration module according to claim 8.
1O.A communication system as hereinbefore described, with reference to, and as shown in, Figure 1 of the accompanying drawings.
11. A communication device as hereinbefore described, with reference to, and as shown in, Figure 2 of the accompanying drawings.
12. A configuration method as hereinbefore described, with reference to, and as shown in, Figure 3 of the accompanying drawings.