CN103532860B - The neighbor discovering method of universal flexible - Google Patents

Abstract

The present invention relates to the Neighbor Discovery Protocol of a kind of universal flexible, described discovery agreement includes: setting the number of time slot in single loop and the number of cycles in the cycle according to demand, described number of time slot is prime number；Using first time slot in each circulation in each cycle as active time slot, and described active time slot is referred to as guarded time slot；Using the first interior time slot more than the first half of circulation in each cycle as active time slot, and described active time slot is referred to as gone on patrol time slot；Guard time slot and the Placement Strategy of patrol time slot are set, so that under arbitrary number of time slot and number of cycles, can ensure neighbor uni-cast within the corresponding time.Universal flexible of the present invention, can adjust dynamic need, can find to postpone minimum as a general framework in the case of symmetric duty ratio or asymmetric dutycycle.

Description

Universal flexible neighbor discovery method

Technical Field

The invention relates to a neighbor discovery protocol, in particular to a universal and flexible neighbor discovery method, specifically to a neighbor discovery protocol in wireless sensor network and mobile computing application, belonging to the technical field of wireless sensor network and mobile computing.

Background

The evolving manufacturing processes produce a variety of small, low cost, multifunctional devices. Such trends have spawned two broad types of applications: wireless Sensor Networks (WSNs) and Mobile Computing (MC). The wireless sensor network is composed of wireless sensing nodes with data collection, processing and transmission functions, and is beginning to be widely applied to environmental monitoring, smart home, traffic supervision, object tracking and the like. More computing-capable devices, such as smartphones and tablets, are meeting the demand for mobile computing applications. Such applications include mobile social networking and mobile entertainment, among others. It is predicted that by 2016, mobile social networking applications will have over 17 hundred million users.

Both types of applications use "neighbor discovery" as one of the most basic functions. For a wireless sensor network, sensing nodes need to discover nodes around the sensing nodes to maintain the connectivity of the network; for mobile computing applications, many applications are designed based on the interconnection between nearby devices. If the neighbor nodes cannot be discovered in time, the nodes are not aware of the nodes existing around the nodes or the opportunity of discovering the instant neighbor nodes is lost. This result will lead to a drastic drop in application performance and even overall network performance.

Typically, the nodes (sensing nodes, cell phones, tablets, etc.) are powered using batteries. Limited by the slow development of battery technology, it is difficult for nodes to support the wireless modules (such as WiFi, bluetooth, Zigbee, etc.) to be always on, so they usually need to turn on and off the wireless modules. Generally, the ratio of the time of the wireless module being opened by the node to the total time is called duty cycle (duty cycle). However, there is an opposing balance between duty cycle and discovery delay: in general, the lower the duty cycle, the higher the delay, and vice versa. Therefore, such a compromise strategy makes it extremely difficult to quickly find each other between neighboring nodes at low duty cycles, and in particular to provide a delay bound (deterministic) that guarantees the finding.

Existing deterministic neighbor discovery protocols (e.g., Disco, U-Connect, Searchlight, etc.) while providing such discovery guarantees, they are generally subject to several disadvantages as follows: 1) their parameter selection is very limited. The parameters of Disco and U-Connect must both be prime numbers, while Searchlight needs to limit its parameters to a power of 2 times a base value. 2) There may be redundant discovery opportunities within a given maximum delay bound. These redundant findings, while potentially reducing the average delay in the general case, do not reduce the maximum delay bound. Removing these redundant discovery opportunities may allow for a reduction in duty cycle without sacrificing maximum delay bounds. 3) They are generally not able to respond to dynamic changes in application requirements. Different applications have different preference for low delay at symmetrical duty cycles and asymmetrical duty cycles, and even for the same application, the preference may vary over time. Protocols such as U-Connect and Searchlight do not adjust accordingly to such dynamic requirements.

In addition, there is currently no research or work available to propose a generic framework for unifying analysis of existing protocols. Such a generic framework, if present, would serve as a platform for comparing existing protocols, measuring these protocols, which appear to be very different in design principles, with a uniform standard. Meanwhile, an optimal scheme can be explored, and the minimum discovery delay is achieved by selecting the optimal parameter configuration.

Disclosure of Invention

The invention aims to overcome the defects in the prior art and provide a universal and flexible neighbor discovery method which is universal and flexible, can adjust the dynamic requirements, can be used as a universal frame and can realize the minimum discovery delay under the condition of a symmetrical duty ratio or an asymmetrical duty ratio.

According to the technical scheme provided by the invention, the universal and flexible discovery method comprises the following steps:

setting the number of time slots in a single cycle and the number of cycles in a period according to requirements, wherein the number of the time slots is a prime number;

taking a first time slot in each cycle in each period as an active time slot, and calling the active time slot as a guard time slot;

taking more than the first half of time slots in the first cycle in each period as active time slots, and calling the active time slots as patrol time slots;

and setting a placement strategy of guard time slots and patrol time slots so that the neighbor discovery can be guaranteed in corresponding time under any time slot number and cycle number.

The strategy for setting the guard time slots and the patrol time slots comprises the steps of reserving the patrol time slots at odd positions, prolonging the lengths of all the active time slots, or placing the patrol time slots in any cycle, but keeping the positions of the patrol time slots in the cycle unchanged.

The invention has the advantages that: the method is universal and flexible, can adjust dynamic requirements, can be used as a universal frame, and can find the minimum delay under the condition of a symmetrical duty ratio or an asymmetrical duty ratio.

Drawings

Fig. 1 is an embodiment of slot scheduling of the present invention.

Fig. 2 is a schematic diagram of the present invention for ensuring discovery under a symmetric duty cycle.

Fig. 3 is an embodiment of the present invention in which neighbor discovery is guaranteed under asymmetric duty cycles and in which more than twice as many time slots are used in one cycle as in another.

Fig. 4 shows an embodiment of the present invention in which neighbor discovery cannot be guaranteed under asymmetric duty cycle and in which the number of slots in one cycle is not more than twice that of the other.

Fig. 5 is a diagram of the present invention as a general framework of a neighbor discovery protocol.

Fig. 6 is a simulation diagram of the relationship between the discovery delay and the discovery amount under the condition that the symmetric duty ratio is 5%.

Fig. 7 is a simulation diagram of the relationship between the discovery delay and the discovery amount under the conditions of the asymmetric duty ratio of 1% and 10% according to the invention.

Fig. 8 is a diagram illustrating the discovery delay and the discovery amount for a symmetrical duty cycle of 5% in a wireless sensor field experiment according to the present invention.

Fig. 9 is a schematic diagram of the relationship between the discovery delay and the discovery amount in the case of asymmetric duty cycles of 1% and 10% in the field experiment of the wireless sensor according to the present invention.

Detailed Description

The invention is further illustrated by the following specific figures and examples.

In order to be universal and flexible, adjust dynamic requirements, be used as a universal framework and discover the minimum delay under the condition of symmetrical duty ratio or asymmetrical duty ratio, the discovery protocol of the invention comprises the following steps:

setting the number of time slots in a single cycle and the number of cycles in a period according to requirements, wherein the number of the time slots is a prime number;

taking a first time slot in each cycle in each period as an active time slot, and calling the active time slot as a guard time slot;

taking more than the first half of time slots in the first cycle in each period as active time slots, and calling the active time slots as patrol time slots;

and setting a placement strategy of guard time slots and patrol time slots so that the neighbor discovery can be guaranteed in corresponding time under any time slot number and cycle number.

The strategy for setting the guard time slots and the patrol time slots comprises the steps of reserving the patrol time slots at odd positions, prolonging the lengths of all the active time slots, or placing the patrol time slots in any cycle, but keeping the positions of the patrol time slots in the cycle unchanged.

In the embodiment of the invention, in the process of delaying the lengths of all the active time slots, the time length of the active time slot is prolonged to be generally 20-30 ms.

Specifically, in the embodiment of the present invention, a discovery protocol is defined as Hello, and the design of the discovery protocol includes the following contents:

A. under the condition of giving the number c of time slots in a single cycle and the number n of cycles in a single cycle, designing a time slot placement strategy, so that the maximum delay of a neighbor discovery protocol is the time of one cycle under the condition of symmetrical duty ratio;

in particular, comprise

A1, taking the first time slot in each cycle as an active time slot, and calling the active time slot as a guard time slot;

a2, regarding slightly more than the first half of the time slots in the first cycle of each cycle as active time slots and regarding the active time slots as patrol time slots, so the duty cycle d of the discovery protocol Hello can be expressed as

Wherein,indicating a rounding operation, an example is shown in fig. 1 where the number of slots c is equal to 9 and the number of cycles n is 3, in fig. 1G indicates guard slots and P indicates patrol slots.

A3, verifying that in the case of symmetric duty cycle, the maximum delay of neighbor discovery is one cycle of time: in the case of a symmetric duty cycle, the number of slots c in the cycle of each node is the same, and therefore, the phase difference of guard slots between nodes is stable. In addition, in a period, the time slots of the first cycle, which are slightly more than the first half of the number of the time slots, are all active time slots, so that the guard time slot of one node always coincides with the patrol time slot of another node no matter what the phase difference of the guard time slots, and mutual discovery is achieved, and fig. 2 is a specific embodiment. Two node 1 and node 2 choices for the symmetrical duty cycle case of FIG. 2The parameters are identical, the phase difference of which is only possible in the interval 0, c). If the phase difference is less than c/2, then the guard time slot G of node 2 must overlap the active time slot (G or P) of node 1 over a period (comprising a number of cycles) because there is one guard time slot of node 2 in the first half of each cycle of node 1 and one cycle in each cycle of node 1, the first half of which is the active time slot. If the phase difference is greater than c/2, then the guard time slot G of node 1 must overlap the active time slot of node 2 within one cycle time. In summary, in the case of a symmetric duty cycle, the maximum delay L of neighbor discovery_sTime for one cycle:

L_s＝cn (2)

B. by limiting the number c of the time slots, the neighbor discovery can still be completed within a certain time under the condition of asymmetric duty ratio;

the step b specifically comprises the following steps:

b1, aiming at the asymmetric duty ratio caused by the fact that the number c of the time slots in the cycle is the same and the number n of the cycles in the cycle is different, the neighbor discovery can be guaranteed to be completed within a certain time without additional limitation; wherein the determined time is the larger of the cycle times between the two nodes. Since the number of time slots c in a cycle is equal, the verification of the observation can refer to step a 3.

B2, if the number of time slots c in the cycle is different, setting the number of time slots of the node 1 as c₁The number of time slots of node 2 is c₂(ii) a And one of them is more than twice as large as the other, e.g. c₁≥2c₂And the neighbor discovery can be ensured to be completed within a certain time without additional limitation. Wherein the determined time is a cycle time of a node having a larger number of slots. The conclusion can be verified as follows: c. C₁≥2c₂I.e. when it means that there are two guard slots for node 2 in each cycle of node 1 and there is one guard for node 2 in the first half of each cycle of node 1And (4) clearance. Since at least the first half of each cycle of node 1 is an active slot, the maximum discovery delay for nodes 1 and 2 is the cycle time for node 1, as shown in fig. 3.

B3, if the number of time slots c in the cycle is different, setting the number of time slots of the node 1 as c₁The number of time slots of node 2 is c₂And one of them is not more than twice as large as the other, e.g. c₂<c₁<2c₂The limit slot number c must be a prime number. Without this restriction, neighbor discovery cannot be guaranteed, and even the neighbor discovery may never result in mutual discovery between neighboring nodes, as shown in fig. 4. After the time slot number c is limited to prime number, the verification can be carried out according to the Chinese remainder theorem, and the verification is carried out at c₁c₂Within a time slot, the active time slots of two nodes overlap at least once, so that the maximum delay of neighbor discovery is c₁c₂And a time slot.

In summary, in order to ensure that neighbor discovery can be guaranteed under any asymmetric duty ratio, the number c of slots in a cycle is uniformly limited to be a prime number, so that the maximum delay L is ensured_asIs composed of

$L_{as}=\left\{\begin{array}{c}max\{c_1{n}_1,c_2{n}_2\}{c}_1=c_2\\ c_1{c}_2,c_1\&NotEqual;c_2\end{array}\right.---\left(3\right)$

Wherein n is₁、n₂The number of cycles for node 1 and the number of cycles for node 2, respectively.

C. The discovery protocol Hello can be used as a general framework of a neighbor discovery protocol to be analyzed, wherein the general protocol comprises existing discovery protocols such as Quorum, Disco, U-Connect and Serchright;

the step C specifically comprises the following steps:

the C1, Quorum protocol organizes the slots into an m x m square matrix (one cycle) and selects one of the rows and one of the columns as the active slot, however, transferring the selected row (column) to the first row (column) does not affect the maximum delay of the protocol at symmetric duty cycles. It thus corresponds to a redundant variant of the discovery protocol Hello, in the form of Hello (m, m);

c2, Disco selects two different prime numbers p and q, and takes as active time slots an integer multiple of each individual prime number, by organizing the time slots within one period thereof into a q × p matrix, it can be found that the first column is always an active time slot, while the mutual primeness of p and q itself is such that there is and always one active time slot on the other columns, by shifting these active time slots to the first row, Disco can be found to be also a redundant variant of the discovery protocol Hello, in the form of Hello (p, q), where p and q are unequal prime numbers.

C3, U-Connect selects a prime number w, organizes the slots in a cycle into a matrix of w x w, and selects the first column and the first row of slots slightly larger than the first half as active slots, which is easily verified to be a special form of the discovery protocol Hello, Hello (w, w), where w is a prime number.

C4, Searchlight organizes slots within a cycle intoMatrix (i.e. containing within one period)A cycles, each cycle comprising a slots), and selecting the first column and the second column inTraverse in one cycleOne slot is taken as the active slot. Using a similar approach as described above, Searchlight is also a special form of the discovery protocol Hello of the present invention, in the form of Hello (a,)。

in summary, the discovery protocol Hello integrates the four well-known neighbor discovery protocols, which are all the results or redundant variants of the discovery protocol Hello under some specific parameter combination, as shown in fig. 5, which is a general framework.

D. Respectively calculating optimal parameter combinations under the conditions of symmetrical duty cycles and asymmetrical duty cycles to enable maximum delay limits to be minimum under the respective corresponding conditions;

the step D comprises the following steps:

d1, for the symmetric duty cycle case, in combination with equation (1) and equation (2), a maximum delay expression with only one parameter can be obtained:

$L_s=\frac{c^2}{2(cd-1)}---\left(4\right)$

the first derivative is removed and zeroed out by equation (4), and the optimal parameters to minimize the maximum delay are obtained as:

$c=\frac{2}{d}---\left(5\right)$

d2, for asymmetric duty cycle case, in combination with equation (3), a minimum maximum delay expression can be obtainedIs composed of

$L_{as}^{*}=\min \{\underset{c_1\&NotEqual;c_2}{\min }{c}_1{c}_2,\underset{c_1=c_2}{\min }\max \{c_1{n}_1,c_2{n}_2\left\}\right\}---\left(6\right)$

To make c₁c₂At a minimum, each c_iThe minimum value that can be taken is slightly greater than 1/d_iSo that the minimum value of the product is close to 1/(d)₁d₂) (ii) a To minimize another term, d is not assumed₁<d₂Then c can be derived from equation (1)₁n₁>c₂n₂Then the term is equivalent to minc₁n₁. According to equation (5), the minimum value of this term isBoth are the smallest, so the minimum value of the maximum delay is 1/(d)₁d₂) The minimum value is at each c_iSlightly larger than 1/d_iIs obtained when the prime number is greater than the threshold value.

E. Two optimization schemes to eliminate and exploit redundancy discovery.

The step E specifically comprises the following steps:

e1, removing redundancy from misalignment with the time slots, where each time slot overlaps two time slots of another node, resulting in redundant discovery opportunities. This redundancy can be eliminated by striped probing, i.e. patrolling every other slot in the first cycle of each cycle. The method not only can keep the maximum delay unchanged, but also can effectively reduce the duty ratio.

E2, eliminating redundancy from repetitive patrol slots, patrol slots occurring every other slot may also cause multiple discoveries for some specific time phase difference, however, further deletion of any patrol slot may result in neighbor discovery not being completed within a specific time. Therefore, only how to efficiently utilize these redundancies can be considered. In the embodiment of the invention, a randomization scheme is selected: any patrol slot is placed in any cycle within a cycle, but its relative position within the cycle is kept unchanged. Such randomization disturbs the repetition of the original patrol time slots, so that the multiple discoveries are as far apart as possible, thereby achieving the purpose of reducing the average delay.

FIG. 6 is a graph of discovery delay versus discovery number at a symmetric duty cycle of 5%, where Hello is the initial design, Hello-S is the design after using streak detection, and Hello-SR is the design using streak detection and randomization. Fig. 7 shows the relationship between the discovery delay and the discovery amount when the asymmetric duty ratio is 1% and 10%, and fig. 8 shows the relationship between the discovery delay and the discovery amount when the symmetric duty ratio is 5% in the wireless sensor experiment according to the present invention. Fig. 9 shows the relationship between the observed delay and the observed amount for asymmetrical duty cycles of 1% and 10% in a wireless sensor experiment according to the present invention.

Claims (1)

1. A universal flexible neighbor discovery method, the discovery method comprising:

setting the number of time slots in a single cycle and the number of cycles in a period according to requirements, wherein the number of the time slots is a prime number;

taking a first time slot in each cycle in each period as an active time slot, and calling the active time slot as a guard time slot;

taking more than the first half of time slots in the first cycle in each period as active time slots, and calling the active time slots as patrol time slots;

setting a placement strategy of guard time slots and patrol time slots so that neighbor discovery can be guaranteed within corresponding time under any time slot number and cycle number;

the strategy for setting the guard time slots and the patrol time slots comprises the steps of reserving the patrol time slots at odd positions, prolonging the lengths of all the active time slots, or placing the patrol time slots in any cycle, but keeping the positions of the patrol time slots in the cycle unchanged.