CN102076079A - Double bounce time slot allocation method of randomly-deployed sensor node without identification (ID) - Google Patents

Abstract

Translated fromChinese

本发明公开了一种随机部署的无ID传感器节点两跳时隙分配方法，在初始随机部署环境下，对异步唤醒工作的无ID传感器节点首先进行时间同步，然后建立一个循环的竞争—判别的过程，各节点随机竞争当前时隙号，竞争失败的节点发布接收数据包的时间信息，竞争存留的节点收集该时间信息并与自身发送数据包的时间比较，判断自己是否在两跳内竞争成功以获取当前竞争的时隙号，由此实现了无ID情况下的两跳时隙分配。该方法能够保证网络中任何两跳内节点的分配时隙不同，为两跳内的节点建立独立的时隙信道，有效避免通信中的冲突问题。

The invention discloses a randomly deployed two-hop time slot allocation method for non-ID sensor nodes. In the initial random deployment environment, time synchronization is first performed on the non-ID sensor nodes that wake up asynchronously, and then a cycle of competition-discrimination is established. During the process, each node randomly competes for the current slot number, and the node that fails the competition releases the time information of receiving the data packet, and the remaining nodes collect the time information and compare it with the time when they send the data packet to judge whether they have successfully competed within two hops To obtain the currently contended time slot number, thereby realizing the two-hop time slot allocation in the case of no ID. The method can ensure that the allocated time slots of nodes in any two hops in the network are different, establish independent time slot channels for nodes in the two hops, and effectively avoid conflicts in communication.

Description

A kind of no ID sensor node double bounce slot allocation method of disposing at random

Technical field

The invention belongs to the wireless network communication technique field, be specifically related to a kind of no ID sensor node double bounce slot allocation method of disposing at random.

Background technology

In a lot of wireless sensor networks were used, a large amount of sensor nodes need be deployed in the monitored area at random.In the starting stage of finishing node deployment, each sensor node is understood seldom network environment information, for example the interstitial content of Bu Shuing, neighbor node number, network topology etc.In addition, these sensor nodes even may not have the ID address.This is because in actual applications, and the general purpose transducer node of a large amount of cheapnesss is provided with independent permanent ID, very trouble one by one.And, this permanent independent ID address is set, need long figure place to guarantee uniqueness, this obviously will cause bigger communication overhead to the sensor node of reality towards the simple data acquisition applications.In order to allow the no ID node of these initial random deployment set up into a wireless sensor network rapidly, obviously need to set up reliable communication link between the node, so that carry out certain interacting message.Common internodal communication link is divided into two kinds of forms: compete at random and time division multiplexing.The former be owing to must there be affirmation mechanism, thereby can't be suitable under no ID situation.The latter effectively avoids the conflict interference problem in the network service, thereby can finish validation of information under no ID situation, so become a kind of feasible link form owing to can set up independently time slot channel for the node in the double bounce.Yet, want in the node that does not have these initial no ID, to carry out the double bounce time slot allocation, must finish certain message between the node, this needs the foundation of link again conversely.So, time slot allocation and link establishment, both are the complementary relations of mutual restriction.Therefore, how in the no ID node of initial random deployment, to carry out the double bounce time slot allocation, set up time-multiplexed communication link, become a challenge.Existing wireless sensor network slot allocation method mainly contains as follows:

(1) based on the time slot allocation of communication link, see Ted Herman, Sebastien Tixeuil, " ADistributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks ", Lecture Notes in Computer Science, Vol.3121,2004, pp.45-58, this method is finished the double bounce time slot allocation in wireless sensor network, yet link exists between its hypothesis node, and node can free pass-along message in distribution, and this obviously is not suitable for the sensor node of initial random deployment.

(2) based on the time slot allocation of node ID, see Johannes Schneider and RogerWattenhofer, " Coloring unstructured wireless multi-hop networks ", inProceedings of PODC, Calgary, Alberta, Canada, Aug.2009, pp.210-219, the node that this method does not initially have a link carry out the double bounce even the time slot allocation of multi-hop more, yet its hypothesis node has had the ID of oneself, this information that makes that node can be received oneself in distribution is confirmed, thereby is not suitable for the sensor node of initial no ID.

Therefore, said method has supposed that perhaps node has distributed ID owing to supposed to have set up communication link between the node, therefore, is not suitable for being used for the no ID sensor node of disposing based at random.

Summary of the invention

The purpose of this invention is to provide a kind of no ID sensor node double bounce slot allocation method of disposing at random, can know nothing and not carry under the self ID situation deployed environment on every side, realize double bounce time slot allocation node at sensor node.

A kind of no ID sensor node double bounce slot allocation method of disposing at random, each node store identical timeslot number tabulation, and this method is specially:

(1) each node passes through broadcast data packet realization clock synchronization at random, and the initialization oneself state is the competition node;

(2) respectively compete node broadcast data packet at random, and write down the clock of each time broadcast data packet, packet carries first timeslot number information in the timeslot number tabulation of competing node self storage; Receive packet when certain competition node, then the clock of this packet received in record, and oneself state is updated to non-competing node, finally lasts till in neighbours' scope of any competition node not compete node;

(3) non-competing node is broadcasted the clock of receiving packet in step (2) at random, the competition node is received the clock of all non-competing node broadcasts in neighbours' scope, therefrom select minimum clock and oneself clock of each time broadcast data packet in step (2) relatively, if there be the clock identical with minimum clock, then obtain the timeslot number that carries in the packet of the corresponding broadcasting of this clock, and first timeslot number in the remaining knot removal timeslot number tabulation of not obtaining timeslot number, and upgrade oneself state for competing node, return step (2), successfully obtain timeslot number up to all nodes.

As optimization, all with Probability p=1/ Δ broadcasting, Δ is neighbours' number upper limit of node in described step (1)～(3).

The present invention is under initial random deployed environment, the asynchronous no ID sensor node that wakes work up is at first carried out time synchronized, set up the process of the competition-differentiation of a circulation then, each node is competed current time slots number at random, the node issue of competition failure receives the temporal information of packet, the node that retains of competition collect this temporal information and with the time ratio that self sends packet, judge oneself whether in double bounce, to compete successfully to obtain the timeslot number of current competition, realized the double bounce time slot allocation under the no ID situation thus.This method can guarantee the distribution time slot difference of any double bounce interior nodes in the network, sets up independently time slot channel for the node in the double bounce, the collision problem in effectively avoiding communicating by letter.

Description of drawings

Fig. 1 is the inventive method flow chart;

Fig. 2 is an example double bounce time slot allocation result schematic diagram of the present invention.

Embodiment

Below by embodiment the present invention is described in further detail, but following examples only are illustrative, protection scope of the present invention is not subjected to the restriction of these embodiment.

Fig. 1 is an algorithm flow chart of the present invention, specifically comprises following step:

1, establish and be limited to 1000 on the node deployment, current to 100 no ID nodes at 80*80m²Dispose at random in the zone, the node communication radius is that 12m disposes, and therefore disposing the posterior nodal point neighbours number upper limit is about 15, and each node is set up unified time slot number tabulation ψ, the timeslot number number is 15 * 4=60, the time slot position when each timeslot number represents that node carries out time-division multiplex communication.Wake up if node is asynchronous, local zone time is divided into equally spaced time slot, and send packet (Δ is neighbours' number upper limit of node, by the decision of node applied environment attribute) at each time slot at random with Probability p=1/ Δ ≈ 0.067, packet carries local clock.Here preferably with the broadcasting of Probability p=1/ Δ, in short time interval

Any node is all received the packet of at least one neighbor node broadcasting in (N is the node deployment number upper limit, by the decision of node hardware capabilities).If certain node is received the packet that other node sends, then the clock with local clock and packet indication compares, local clock is adjusted into wherein bigger clock, if after this this node receives the packet that other node sends again, then proceed comparison, with bigger renewal local clock; Corresponding broadcasting Probability p=1/ Δ the longlyest reaches at the node local clock

In the individual time slot (by every time slot 5ms, approximately half a minute), the time of all nodes will with the time synchronized of the node of waking up the earliest in the network, and current oneself state be set be the competition node, entered for the 2nd step this moment.

2, respectively competing node replacement local zone time is zero, and on each time slot with Probability p=0.067 broadcast data packet at random, carry first timeslot number among the ψ, compete the clock of actual each time transmission of nodes records self packet simultaneously; If certain competition node is received packet, then oneself state is changed into non-competing node, stop to send packet, and write down the clock when receiving packet; Rise to when the time of all nodes

During individual time slot, will not have other competition nodes in neighbours' scope of any competition node, change for the 3rd step this moment over to.

3, all node replacement local zone times are zero, and the competition node stop sends packet, and the clock when receiving packet in the step 2 of non-competing node with record is broadcasted at random with Probability p=0.067 on each time slot; When the local zone time of all nodes rises to

During individual time slot, the competition node will be received the clock of non-competing node broadcasts in all neighbours' scopes, at this moment, the competition node relatively should the period in all clocks, select minimum one again and the clock when the transmission packet of record in step 2 compare, if this minimum clock equals the clock of its certain transmission packet that once writes down, then this node obtains the timeslot number that this packet carries; Remaining all nodes that also do not become distribution of work timeslot number are first timeslot number of deletion from self sequential tabulation, and resets oneself state and be the competition node, enters for the 2nd step, and circulation according to this obtains timeslot number until all nodes.Figure 2 shows that the double bounce time slot allocation result schematic diagram of this example, the as can be seen from the figure timeslot number difference of any double bounce interior nodes in the network, the node in the double bounce has been set up independently time slot channel, the collision problem in can effectively avoiding communicating by letter.

The above; only for the preferable embodiment of the present invention, but protection scope of the present invention is not limited thereto, and anyly is familiar with those skilled in the art in the technical scope that the present invention discloses; the variation that can expect easily or replacement all should be encompassed within protection scope of the present invention.Therefore, protection scope of the present invention should be as the criterion with the protection range of claim.

Claims (2)

1. no ID sensor node double bounce slot allocation method of disposing at random, each node stores identical timeslot number tabulation, and this method is specially:

(1) each node passes through broadcast data packet realization clock synchronization at random, and the initialization oneself state is the competition node;

(2) respectively compete node broadcast data packet at random, and write down the clock of each time broadcast data packet, packet carries first timeslot number information in the timeslot number tabulation of competing node self storage; Receive packet when certain competition node, then the clock of this packet received in record, and oneself state is updated to non-competing node, finally lasts till in neighbours' scope of any competition node not compete node;

(3) non-competing node is broadcasted the clock of receiving packet in step (2) at random, the competition node is received the clock of all non-competing node broadcasts in neighbours' scope, therefrom select minimum clock and oneself clock of each time broadcast data packet in step (2) relatively, if there be the clock identical with minimum clock, then obtain the timeslot number that carries in the packet of the corresponding broadcasting of this clock, and first timeslot number in the remaining knot removal timeslot number tabulation of not obtaining timeslot number, and upgrade oneself state for competing node, return step (2), successfully obtain timeslot number up to all nodes.

2. the no ID sensor node double bounce slot allocation method of disposing at random according to claim 1 is characterized in that, all with Probability p=1/ Δ broadcasting, Δ is neighbours' number upper limit of node in described step (1)～(3).

Images