WO2019157627A1

WO2019157627A1 - Method and apparatus for detecting hidden node

Info

Publication number: WO2019157627A1
Application number: PCT/CN2018/076642
Authority: WO
Inventors: Erma Perenda; Haris Gacanin
Original assignee: Nokia Shanghai Bell Co Ltd; Nokia Solutions and Networks Oy
Current assignee: Nokia Shanghai Bell Co Ltd; Nokia Solutions and Networks Oy
Priority date: 2018-02-13
Filing date: 2018-02-13
Publication date: 2019-08-22
Anticipated expiration: 2020-08-13
Also published as: CN111656736B; CN111656736A

Abstract

According to an embodiment, a networking device (121) for detecting a hidden node (100) in a wireless mesh network (130), WMN, with a plurality of active nodes (100-102), is disclosed, the networking device (121) comprising a processing unit (120) configured to collect for a first (101) and second (102) active node of the active nodes (100-102) operating in an identical channel, operating parameters, and to calculate based on the operating parameters a respective channel utilization performance indicator for the first (101) and second (102) active node, and to calculate a difference between the respective channel utilization performance indicators, and when the difference exceeds a first predefined threshold, detecting the hidden node (100) as a third active node operating on the identical channel and hidden to the first (101) or second (102) active node (101).

Description

METHOD AND APPARATUS FOR DETECTING A HIDDEN NODE

Technical Field

The present invention generally relates to the field of detecting a hidden node in a wireless mesh network.

Background

A wireless mesh network, WMN, is a communication network comprising a plurality of nodes organized in a mesh topology. Each of these nodes wirelessly exchanges data with other nodes and/or with associated devices in the WMN. Because of the quick and easy deployment of WMNs, they are extensively installed in private and public environments, such as residential locations, enterprises and offices, especially when cabling is unavailable or undesired. However, when extending a WMN, each additional node therein decreases throughputs for end-users. To alleviate this problem, nodes may be equipped with multiple radios and different channels may then be assigned to different nodes. Nevertheless, in an unmanaged environment, for example in apartment buildings or even in offices comprising different companies, channels are shared by different competing nodes resulting in a hidden node problem in the WMN. Such a hidden node problem has a very deteriorating impact on the end-user′s quality of experience.

A hidden node problem occurs when a first node is within a transmission range of a second node, but outside the transmission range of a third node. The first node is then hidden with respect to the third node and vice versa. Both the first and the third node may actively transmit data towards the second node, since they cannot sense that the medium wherein data is transmitted is busy. As a result, collisions of data packets may occur at the second node resulting in high error rates. It is therefore important to detect a hidden node in a WMN in order to avoid such high error rates.

A way to detect a hidden node is by actively probing in the network by a so-called active hidden node detection mechanism as, for example, described in Techniques of detection of the hidden node in wireless Ad Hoc network, by Fatima, M. et. al., published in Proceedings of the World Congress on Engineering 2011 Vol II, WCE 2011, July 6-8, 2011, London, U.K. By means of this mechanism, if a certain node wants to detect potential hidden nodes in the network, it sends a detection request to all its one-hop neighbouring nodes. Next, these one-hop neighbouring nodes that receive the request, start a sequence of unicast probe packets to their neighbours for a time interval specified in the detection request. The detecting node then measures the traffic of its neighbours and based on received packets, a complete list of hidden nodes is established.

Hidden nodes may also be detected in a passive way by a request-to-send/clear-to-send mechanism. These are both based on sniffing or listening to all data transmissions on the medium and by detecting missing data packets in a data flow.

Another technique is disclosed in US20140036709A1 wherein a hidden node is detected based on analysis of reports received from a plurality of nodes. A hidden node is then detected if it is observed that a transmission at one node is not observed by another one.

Document US20170026819A1 discloses a method for out-of-band hidden node detection. This method comprises transmitting out-of-band signals and considering both nodes and associated devices. A node or an associated device transmits a first out-of-band signal and updates a first list of neighbouring devices based on the reception of a second out-of-band signal from the neighbouring devices. A node may then receive a second list of neighbouring devices from its associated devices. By comparing the first and the second list, the node can detect hidden nodes and hence change an operation mode before transmitting data packets.

Summary

The above-mentioned methods for detecting a hidden node are, however, either introducing additional signals in the network such as, for example, a detection request, or are retroactively detecting a hidden node. The former method impacts the network operation thereby interrupting a user service, while the latter method detects a hidden node only afterwards, such that a detection may be outdated.

It is therefore an object to disclose a device and system for detecting a hidden node in a WMN without interrupting a user service and simultaneously avoiding the risk that a detection is outdated.

This object is achieved, in a first aspect, by a networking device for detecting a hidden node in a WMN with a plurality of active nodes, the networking device comprising a processing unit configured to:

- collect for a first and second active node of the active nodes operating in an identical channel, operating parameters; and

- calculate based on the operating parameters a respective channel utilization performance indicator for the first and second active node; and

- calculate a difference between the respective channel utilization performance indicators; and

- when the difference exceeds a first predefined threshold, detecting the hidden node as a third active node operating on the identical channel and hidden to the first or second active node.

Firstly, the processing unit collects operating parameters of the active nodes in the WMN. These operating parameters are parameters that are available to the networking device, i.e. without interfering with the WMN operation. Thus, there is no request sent to the nodes, nor is there any change in a configuration of the nodes like, for example, switching them to a scanning mode. Moreover, since the aim is to detect a hidden node in the WMN, the collection is targeted to a pair of nodes, namely a first and second active node which are operating in an identical channel.

These operating parameters are, for example, a channel utilization parameter, an activity factor, a noise level, a received signal strength indicators, RSSI, level, an error rate and/or a retransmission rate.

Secondly, the processing unit calculates for both the first and second node a respective channel utilization performance parameter. The collected operating parameters are thus translated in performance parameters expressing for each of the nodes their performance with respect to the channel they use to send and receive data packets.

Thirdly, the processing unit of the networking device calculates a difference between the channel utilization performance indicators of the first and second node. Subsequently, in the fourth step, this difference is examined in order to detect the hidden node.

When the difference exceeds a first predefined threshold, the processing unit detects the hidden node as a third active node operating on the identical channel as the first and second node. The detected node is then hidden to either the first or second active node.

Several advantages are identified with regard to the prior art. Firstly, only active nodes are considered in the detection. Since inactive hidden nodes, although they are hidden, do not impact a user performance, it is redundant to take them into account. Secondly, by focusing on a pair of nodes, the WMN is described at the location of these nodes such that not the whole WMN needs to be taken into account. This reduces the complexity of subsequent calculations. Thirdly, since operating parameters are used to perform the calculations and associated detection, the WMN is not impacted and the WMN is described at the instant of the collection of the parameters. There is thus no need for any service interruption of the nodes, nor a channel switching which would cause a delay, thereby decreasing the total network capacity. In other words, compared to the prior art, the detection in this disclosure is performed with zero-cost. Finally, since only operating parameters are collected, the networking device is suitable to be implemented in the WMN in a fast and straightforward way.

According to an embodiment, an additional condition is examined when the difference does not exceed the first predefined threshold. In this latter occurrence, the processing unit performs additional calculations when the respective channel utilization performance indicators are similar, or, differently formulated, when the already calculated difference is approximately equal to zero. The difference is thus, for example, lower than an error margin. The processing unit then calculates for the first and/or second active node a respective error rate performance indicator. This latter calculation is again based on the collected operating parameters.

Next, when one of the respective error performance indicators exceeds a predefined error threshold, the processing unit likewise detects the third active node as the hidden node. This way, hidden nodes are detected when they are located at both sides of the first and the second node.

According to an embodiment, the channel utilization performance indicator is indicative for channel busy time during a predefined time period.

This way, the channel utilization performance indicators are calculated by solely observing the channel busy time, such that the indicators are calculated in a fast and straightforward manner. Furthermore, the networking device may be easily adapted to a WMN which is highly dynamic or not by simply adjusting the predefined time period.

According to an embodiment, the first and second nodes are manageable by the networking device.

This not only implies that the operating parameters are collected in an efficient way, but that, for example, a probability of introducing errors when collecting the parameters is reduced as well.

According to an embodiment, the networking device further comprises a knowledge base, KB, comprising channel utilization performance indicators, and the processing unit is further configured to update the KB after calculating the channel utilization performance indicators of each active node.

Besides storing the channel utilization performance indicators, the KB may then further be used to describe the WMN. Advantageously, the first predefined threshold may then dynamically be adapted in order to refine a detection, wherein the refinement is performed per pair of a first and second node.

According to a second aspect, the disclosure relates to a method for detecting a hidden node in a WMN, with a plurality of active nodes, the method comprising the steps of:

- collecting for a first and second active node of the active nodes operating in an identical channel, operating parameters; and

- calculating based on the operating parameters a respective channel utilization performance indicator for the first and second active node; and

- calculating a difference between the respective channel utilization performance indicators; and

- when the difference exceeds a first predefined threshold, detecting the hidden node as a third node operating on the identical channel and hidden to the first or second active node.

According to an embodiment, the method further comprises the steps of, when the difference does not exceed the first predefined threshold and when the respective channel utilization performance indicators are similar:

- calculating based on the operating parameters for the first and/or second active node a respective error rate performance indicator; and

- when one of the respective error rates exceeds a predefined error threshold, detecting the third active node as the hidden node.

According to a third aspect, the disclosure relates to a computer program product comprising computer-executable instructions for performing the method according to the second aspect when the program is run on a computer.

According to a fourth aspect, the disclosure relates to a computer readable storage medium comprising the computer program product according to the third aspect.

Brief Description of the Drawings

Fig. 1 illustrates a wireless mesh network comprising a networking device for detecting a hidden node according to an embodiment of the invention; and

Fig. 2 illustrates steps performed by the networking device for detecting a hidden node according to an embodiment of the invention; and

Fig. 3 illustrates steps performed for updating a knowledge base comprising channel utilization performance indicators calculated by the networking device according to an embodiment of the invention; and

Fig. 4 illustrates a suitable computing system for performing steps according to embodiments of the invention.

Detailed Description of Embodiment (s)

According to an embodiment, the invention relates to a networking device for detecting a hidden node in a wireless mesh network, WMN. Fig. 1 illustrates such a WMN 130 and such a networking device 121. Fig. 2 illustrates steps performed by the networking device 121 for detecting a hidden node.

The WMN 130 illustrated in Fig. 1 comprises four nodes 100-103, from which only three nodes 100-102 are active. Each active node sends and receives data packets within its respective range. This is illustrated by the ranges 110-112, each corresponding to an active node. In particular, range 110 relates to node 100, range 111 relates to node 101 and range 112 relates to 102. Since node 103 is not active in this exemplary illustration, there is no related range drawn up.

The active nodes 100-102 within the WMN 130 are all operating in a same channel. This channel is, for example, within the 2.4GHz or 5GHz frequency band.

In the representation of Fig. 1 the ranges are presented as circles, but it should be clear that a range of a node in real-life situation may differ from a circular shape and depends on, for example, obstacles such as walls and ceilings in the location wherein the nodes are operating.

The

nodes

100 and 102 are within the range 111 of node 101, while node 100 is outside the range 112 of node 102 and accordingly node 102 is outside the range 110 of node 100. Consequently, node 102 is a hidden node with respect to node 100, while the same reasoning accounts from the point of view of node 102, namely that node 100 is a hidden node with respect to node 102.

The networking device 121 detects these hidden

nodes

100 and 102 in the WMN 130. For this, the networking device 121 comprises a processing unit 120 and according to an embodiment a knowledge base, KB, 122 as well.

In the illustration of Fig. 1, the nodes 100-103 are manageable nodes, i.e. manageable by the networking device 121. This is illustrated by, for example, connection 123, which is a connection between the networking device 121 and the node 101. This way, the networking device 121 may collect data from the nodes and may further change settings of the nodes, for example, a switching of operating channels.

Alternatively, the networking device 121 may comprises receive units or radio receivers in order to collect data from the nodes 100-102 in the WMN 130.

In a first step 200, the processing unit 120 collects operating parameters from the active nodes 100-102. These operating parameters are parameters which are collected without interfering in the WMN 130. These parameters are, for example, a channel utilization parameter, an activity factor, a noise level, a received signal strength indicators, RSSI, level, an error rate and/or a retransmission rate, or any other parameter suitable to describe the operation of the active nodes 100-102. Since the operating parameters are collected 200 without interfering in the WMN 130, they are collected 200 at zero-cost. The collection 200 of the parameters is performed periodically at a predefined time interval, for example, every few seconds.

The collected 200 operating parameters are in a next step 201 transformed to channel utilization performance indicators. These channel utilization performance indicators identify the network state and based on these channel utilization performance indicators, hidden nodes are detected.

A channel utilization performance indicator is, for example, based on a channel busy time and calculated as:

wherein

is the channel utilization performance indicator of node x operating in channel h, wherein node x corresponds to node 100. Thus, when node y corresponds to node 101, the channel utilization performance indicator of node 101 corresponds to

since they are both operating in the same channelh as already highlighted.

For each of the active nodes 100-102 in the WMN 130 a channel utilization performance indicator may be calculated 201. Next, the KB of the networking device 121 is updated 202 with the calculated 201 channel utilization performance indicators.

Next, the processing unit 120 verifies 203 if a difference between channel utilization performance indicators of two adjacent nodes, for example nodes 100 and 101, exceeds a first predefined threshold u _hn, thr. In other words, the following condition is verified 203:

thus, if the absolute value of the difference exceeds the threshold.

When the difference exceeds is the threshold a hidden node is detected, in this exemplary illustration thus node 102 which is hidden with respect to node 100.

Through the verification 203 of the difference and when the difference exceeds the first predefined threshold, a node is detected next to either node 100 or node 101. When, however, on both sides of the adjacent nodes 100 and 101 a hidden node would be present, thus two hidden nodes, one that is within the range 110 of node 100 but not within that of node 101, and one that is within the range 111 of node 101 but not within that of node 100, and both nodes have similar data traffic, the respective channel utilization performance indicators

and

will be approximately have the same values.

Hence, the processing unit 120 utilizes this given when the condition verified in step 203 does not exceeds the first predefined threshold u _hn, thr. Thus, when the difference between the utilization performance indicators

and

is approximately zero and additionally when an error rate of sent packages at either node 100 or node 101 is higher than a predefined error threshold, a hidden node is detected as well, i.e. the following condition is verified 205:

since a hidden node introduces high errors.

When a hidden node is detected, a reasoning stage 204 is triggered by the processing unit 120. This may, for example, be a notification to a user of the hidden node 102 and a proposal of steps to be taken, such as, for example, a switching of channels of one of the nodes 100-102.

The steps performed by the processing unit 120 may also be illustrated according to Fig. 3 wherein steps are illustrated performed for updating the KB 122. In a first step the data is collected 200, which corresponds to the same step illustrated in Fig. 2. Next, the operating parameters are send 310 and subsequently interpreted in a perception stage 300, in other words translated to channel utilization performance indicators. These calculated performance indicators are send 311 to be used in an intermediate learning stage 301, which on its behalf updates312 the KB 122.

In a reasoning stage 302, which is either based on data received from the perception stage 300, either from the KB 122 itself, it is determined when a hidden node is detected or not. Next, when so, a detection is send 313 to a decision stage 303. In the decision stage 303 an optimization stage 304 is triggered in order to remedy the hidden node problem. The optimization stage 304 further exchanges 314 data with the KB such that in subsequent perception 300 and/or reasoning 302 stages, the KB 122 is further optimized.

Fig. 4 shows details of the networking device 121 according to a further embodiment of the invention. Networking device 121 is suitable for performing the steps according to the above embodiments. Networking device 121 may also be incorporated in or used as a node. Networking device 121 may in general be formed as a suitable general purpose computer and comprise a bus 410, a processor 402, a local memory 404, one or more optional input interfaces 414, one or more optional output interfaces 416, a communication interface 412, a storage element interface 406 and one or more storage elements 408. Bus 410 may comprise one or more conductors that permit communication among the components of the networking device 121. Processor 402 may include any type of conventional processor or microprocessor that interprets and executes programming instructions. Local memory 404 may include a random access memory (RAM) or another type of dynamic storage device that stores information and instructions for execution by processor 402 and/or a read only memory (ROM) or another type of static storage device that stores static information and instructions for use by processor 402. Input interface 414 may comprise one or more conventional mechanisms that permit an operator to input information to the networking device 121, such as a keyboard 420, a mouse 430, a pen, voice recognition and/or biometric mechanisms, etc. Output interface 416 may comprise one or more conventional mechanisms that output information to the operator, such as a display 440, etc. Communication interface 412 may comprise any transceiver-like mechanism such as for example one or more Ethernet interfaces that enables networking device 121 to communicate with other devices and/or systems, for example with a node 100-103. The communication interface 412 of networking device 121 may be connected to such networking device by means of a local area network (LAN) or a wide area network (WAN) such as for example the internet. Storage element interface 406 may comprise a storage interface such as for example a Serial Advanced Technology Attachment (SATA) interface or a Small Computer System Interface (SCSI) for connecting bus 410 to one or more storage elements 408, such as one or more local disks, for example SATA disk drives, and control the reading and writing of data to and/or from these storage elements 408. Although the storage elements 408 above is described as a local disk, in general any other suitable computer-readable media such as a removable magnetic disk, optical storage media such as a CD or DVD, -ROM disk, solid state drives, flash memory cards, ... could be used. The networking device 121 described above can also run as a virtual machine above the physical hardware.

Although the present invention has been illustrated by reference to specific embodiments, it will be apparent to those skilled in the art that the invention is not limited to the details of the foregoing illustrative embodiments, and that the present invention may be embodied with various changes and modifications without departing from the scope thereof. The present embodiments are therefore to be considered in all respects as illustrative and not restrictive, the scope of the invention being indicated by the appended claims rather than by the foregoing description, and all changes which come within the scope of the claims are therefore intended to be embraced therein.

It will furthermore be understood by the reader of this patent application that the words "comprising" or "comprise" do not exclude other elements or steps, that the words "a" or "an" do not exclude a plurality, and that a single element, such as a computer system, a processor, or another integrated unit may fulfil the functions of several means recited in the claims. Any reference signs in the claims shall not be construed as limiting the respective claims concerned. The terms "first" , "second" , third", "a" , "b" , "c" , and the like, when used in the description or in the claims are introduced to distinguish between similar elements or steps and are not necessarily describing a sequential or chronological order. Similarly, the terms "top" , "bottom" , "over" , "under" , and the like are introduced for descriptive purposes and not necessarily to denote relative positions. It is to be understood that the terms so used are interchangeable under appropriate circumstances and embodiments of the invention are capable of operating according to the present invention in other sequences, or in orientations different from the one (s) described or illustrated above.

Claims

A networking device (121) for detecting a hidden node (100) in a wireless mesh network (130) , WMN, with a plurality of active nodes (100-102) , the networking device (121) comprising a processing unit (120) configured to:

- collect for a first (101) and second (102) active node of the active nodes (100-102) operating in an identical channel, operating parameters; and

- calculate based on the operating parameters a respective channel utilization performance indicator for the first (101) and second (102) active node; and

- calculate a difference between the respective channel utilization performance indicators; and

- when the difference exceeds a first predefined threshold, detecting the hidden node (100) as a third active node operating on the identical channel and hidden to the first (101) or second (102) active node (101) .
The networking device (121) according to claim 1, wherein the processing unit (120) is further configured to, when the difference does not exceed the first predefined threshold and when the respective channel utilization performance indicators are similar:

- calculate based on the operating parameters for the first (101) and/or second (102) active node a respective error rate performance indicator; and

- when one of the respective error rate performance indicators exceeds a predefined error threshold, detecting the third active node as the hidden node (100) .
The networking device (121) according to claim 2, wherein the channel utilization performance indicator is indicative for channel busy time during a predefined time period.
The networking device according to claim 3, wherein the respective channel utilization performance indicators are similar when the difference is lower than an error margin.
The networking device (121) according to claim 4, wherein the first (101) and second (102) nodes are manageable by the networking device (121) .
The networking device (121) according to claim 5, wherein the operating parameters comprise at least one of the group of:

- a channel utilization parameter; and

- an activity factor; and

- a noise level; and

- received signal strength indicators, RSSI, level; and

- an error rate; and

- a retransmission rate.
The networking device (121) according to claim 6, further comprising a knowledge base (122) comprising channel utilization performance indicators; and wherein the processing unit is further configured to update the knowledge base (122) after calculating the channel utilization performance indicators of each active node (100-102) .
A method for detecting a hidden node (100) in a wireless mesh network (130) , WMN, with a plurality of active nodes (100-102) , the method comprising the steps of:

- collecting for a first (101) and second (102) active node of the active nodes (100-102) operating in an identical channel, operating parameters; and

- calculating based on the operating parameters a respective channel utilization performance indicator for the first (101) and second (102) active node; and

- calculating a difference between the respective channel utilization performance indicators; and

- when the difference exceeds a first predefined threshold, detecting the hidden node (100) as a third active node operating on the identical channel and hidden to the first (101) or second (102) active node (101) .
The method according to claim 8, further comprising the steps of, when the difference does not exceed the first predefined threshold and when the respective channel utilization performance indicators are similar:

- calculating based on the operating parameters for the first (101) and/or second (102) active node a respective error rate performance indicator; and

- when one of the respective error rate performance indicators exceeds a predefined error threshold, detecting the third active node as the hidden node (100) .
A computer program product comprising computer-executable instructions for performing the method according to claim 8 or 9 when the program is run on a computer.
A computer readable storage medium comprising the computer program product according to claim 10.