CN114025429B - Time-optimized multi-channel time slot reuse scheduling method - Google Patents
Time-optimized multi-channel time slot reuse scheduling method Download PDFInfo
- Publication number
- CN114025429B CN114025429B CN202111301278.9A CN202111301278A CN114025429B CN 114025429 B CN114025429 B CN 114025429B CN 202111301278 A CN202111301278 A CN 202111301278A CN 114025429 B CN114025429 B CN 114025429B
- Authority
- CN
- China
- Prior art keywords
- time slot
- node
- nodes
- time
- channel
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 41
- 238000006243 chemical reaction Methods 0.000 claims abstract description 3
- 108091006146 Channels Proteins 0.000 claims description 56
- 230000009466 transformation Effects 0.000 claims description 6
- 238000009826 distribution Methods 0.000 claims description 2
- 238000010845 search algorithm Methods 0.000 claims description 2
- 238000005265 energy consumption Methods 0.000 abstract description 22
- 238000005516 engineering process Methods 0.000 abstract description 4
- 230000005540 biological transmission Effects 0.000 description 39
- 238000004220 aggregation Methods 0.000 description 21
- 230000002776 aggregation Effects 0.000 description 21
- 230000000694 effects Effects 0.000 description 6
- 230000007423 decrease Effects 0.000 description 4
- 238000010586 diagram Methods 0.000 description 4
- 238000002474 experimental method Methods 0.000 description 4
- 238000004904 shortening Methods 0.000 description 4
- 238000004891 communication Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 230000007958 sleep Effects 0.000 description 3
- 230000009286 beneficial effect Effects 0.000 description 2
- 238000005070 sampling Methods 0.000 description 2
- 235000008694 Humulus lupulus Nutrition 0.000 description 1
- 108700026140 MAC combination Proteins 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000005059 dormancy Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 230000002452 interceptive effect Effects 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000000844 transformation Methods 0.000 description 1
- 230000002618 waking effect Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W72/00—Local resource management
- H04W72/04—Wireless resource allocation
- H04W72/044—Wireless resource allocation based on the type of the allocated resource
- H04W72/0446—Resources in time domain, e.g. slots or frames
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W72/00—Local resource management
- H04W72/50—Allocation or scheduling criteria for wireless resources
- H04W72/52—Allocation or scheduling criteria for wireless resources based on load
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
Time-optimized multi-channel time slot reuse scheduling method, each node pre-distributes time slot CSA according to conflict-free condition j p Formally assigned to the node; otherwise, the node will execute a collision-free time slot assignment algorithm to find consecutive time slots meeting the collision-free condition and assign to the node; s4: after all nodes complete time slot allocation, the algorithm executes time slot conversion, so that the time slot allocation of the wireless sensor network is adjusted to be that a scheduling frame starting from the sequence number 1 allocates continuous time slots for the nodes according to loads, the time slots are reused among the nodes as much as possible by utilizing a multi-channel technology, and when the number of available channels is more than or equal to 2, the energy consumption and the data convergence time of the nodes in the aspect of state switching are obviously reduced.
Description
Technical Field
The invention relates to the technical field of wireless sensor networks, in particular to a time-optimized multi-channel time slot reuse scheduling method.
Background
The wireless sensor network has low cost, flexible deployment and wide coverage range, and has wide application prospect in the fields of environment sensing, intrusion detection, battlefield monitoring and the like. After the sensor nodes are deployed, the nodes usually form a multi-hop data aggregation tree in a self-organizing mode, and the data aggregation is completed by one data aggregation node, namely Sink. The sensor nodes periodically collect sensing data and deliver the data to the Sink in a single-hop or multi-hop mode.
For most sensor networks deployed in unsupervised harsh environments, since the nodes use batteries with limited capacity to provide energy, most nodes cannot be battery replaced or charged, and reducing node energy consumption is an effective means to extend network life.
In a low-load, low-power network environment, the different operating states of the sensor nodes can produce significant energy consumption differences. Because of the multi-hop data transmission characteristic of the data aggregation tree, non-Sink and non-leaf nodes in the tree may need to receive and forward data amounts with unequal sizes from child nodes, and the child nodes have discontinuous transmission time, so that the nodes need to switch states for multiple times to complete data aggregation. Note that node state switching refers to a process of waking up a node from a sleep state, or switching a node from an active state to a sleep state.
Consider a sensor node Mica2 Monte whose energy consumption in various states is shown in Table 1. As can be seen from table 1, the state switching energy consumption of the node is the same as the energy of one data reception and occupies 50% of the transmission energy. Therefore, reducing the number of state switches of a node helps to increase node energy efficiency, thereby extending network life.
At present, the time slot scheduling method for data convergence application mainly optimizes transmission delay in a single-channel multi-hop environment, and node state switching times are not considered when the scheduling methods allocate time slots for nodes, and in the multi-hop transmission environment, the node switching times are obviously increased along with the increase of workload, so that energy consumption is increased. Under the condition of single channel, the time slot reuse among nodes is limited by the available channel number and the wireless interference model, so that the time slot continuity of the nodes can not be completely realized and the data convergence time of the whole network can not be optimized.
Disclosure of Invention
In order to solve the technical problems, the invention provides a time-optimized multi-channel time slot reuse scheduling method, which allocates continuous time slots for nodes according to loads, and realizes the time slots to be reused among the nodes as much as possible by utilizing a multi-channel technology, and when the number of available channels is more than or equal to 2, the energy consumption and the data aggregation time of the nodes in the aspect of state switching are obviously reduced.
In order to achieve the technical purpose, the adopted technical scheme is as follows: the time-optimized multi-channel time slot reuse scheduling method carries out time slot reuse scheduling on a wireless sensor network comprising 1 sink node and n sensor nodes, and specifically comprises the following steps:
s1: the time slot allocation of the nodes starts from sink nodes, a breadth-first search algorithm is adopted, continuous time slots are assigned for the nodes layer by layer from top to bottom, and the continuous time slots are pre-allocated for the nodes according to the workload of the nodes Andrespectively denoted as node s j The smallest time slot sequence number and the largest time slot sequence number in the allocated continuous time slots, when the algorithm allocates time slots for the nodes from top to bottom from sink, the first child node s thereof 1 CSA of (C) 1 r maxSN, which indicates that sink node is assigned the first slot number;
s2: after each node finishes time slot pre-allocation, it needs to verify whether the time slot allocation meets the conflict-free condition of the protocol interference model, where the conflict-free condition is that
(1) When two nodes use different channels, data can be transmitted without interference in the same time slot
(2) When the distance between two nodes is smaller than the interference distance, the two nodes cannot transmit data in the same time slot by using the same channel
S3: if the no-punch condition in step S2 is satisfiedBurst condition, pre-allocated slot CSA j p Assigning formally to the node; otherwise, the node will execute a collision-free time slot assignment algorithm to find consecutive time slots meeting the collision-free condition and assign to the node;
s4: when all nodes complete the time slot allocation, the algorithm will execute the time slot transformation, thereby adjusting the time slot allocation of the wireless sensor network to a schedule frame starting from sequence number 1.
The specific implementation method of the conflict-free time slot assignment algorithm in the step S3 comprises the following steps:
step S3.1, traversing an interference set IS, and constructing an allocated time slot set AS according to the time slots allocated by the nodes in the set;
step S3.2, traversing CSA j p And searches a set of time slots AS of a channel chx chx X is more than or equal to 1 and less than or equal to n if the time slot exists ch ，n ch Is the number of available channels; if so, the channel sequence number is incremented by 1 and the CSA is re-traversed j p In (c) is cycled through until from n ch One channel is found out from the channels to meet CSA j p Is the CSA j f The method comprises the steps of carrying out a first treatment on the surface of the If the CSA is not found to be satisfied j p Allocating a required channel, and executing step S3.3; otherwise, executing the step S3.4;
step S3.3, CSA is carried out j p Updated toTurning to step S3.2;
step S3.4, CSA to be found finally j f Channel chx assigned to node s i And record node s j According to CSA j f The load of the channel chx is updated.
The time slot conversion process in step S4 is as follows: because the adopted time slots are distributed layer by layer from top to bottom, the time slot sequence numbers gradually become smaller in the distribution process, and the minimum time slot sequence number obtained after all nodes distribute the time slots is set as minSN, the time slot sequence number of each node can be adjusted according to the formula (6), and the time slot sequence number of the scheduling frame SF is changed to be from 1.
In the method, in the process of the invention,representing allocation to nodes s i The smallest slot number of the slots, +.>Representing allocation to nodes s i The largest slot number of the slots of (a).
The invention has the beneficial effects that: the method reduces the energy consumption of the node in state node switching, adopts different channels to carry out data transmission, and when the number of the available channels is equal to 2, the same time slot can be repeatedly utilized under various network scales, thereby shortening the length of a scheduling frame SF and shortening the data aggregation time.
Drawings
FIG. 1 is a diagram of a protocol interference model;
FIG. 2 is a flow chart of the present invention;
fig. 3 is a network topology diagram of embodiment 1;
fig. 4 is a node slot allocation diagram of embodiment 1;
FIG. 5 is a graph showing the number of node state switches versus the number of slots when Sink is at (50, 100);
FIG. 6 is a graph showing the number of node state switches versus the number of slots when Sink is at (50, 50);
fig. 7 is a graph of node state switching times versus time slot number for different transmission distances when Sink is located at (50, 100);
fig. 8 is a graph of node state switching times versus time slot number for different transmission distances when Sink is located at (50, 50).
Detailed Description
1. System model and assumptions
The node set S of the wireless sensor network considered herein is composed of one sink node and n sensor nodes. Each sensor node has equal initial energy E init And transmits data to the neighbor nodes using constant energy, so that the nodes have the same wireless transmission distance d th The threshold may be calculated from an energy model of the node. Any pair of nodes S in the set of network nodes S, taking into account the reliability of the data transmission i And node s j Distance of communication d between i,j Should satisfy d i,j ≤d th 。
Looking at a wireless sensor network using TDMA protocols, the energy consumption of wireless sensor node activity generally consists of four parts: transmitting data, receiving data, node dormancy, and node state switching. Table 1 describes the energy consumption of each part of the Mica2Mote node.
TABLE 1 Mica2 Monte node energy consumption Condition
| Parameters (parameters) | Default value |
| Transmission energy consumption | 63 milliwatts |
| Receiving energy consumption | 30 milliwatts |
| Sleep energy consumption | 0.003 milliwatt |
| Node wakeup energy consumption | 30 milliwatts |
In order to reduce the energy overhead of the wireless channel listening activity while optimizing the data delay, TDMA is used herein as the MAC protocol. By dividing the node active time into equal-length time slots t slot And corresponding time slots are allocated to each node according to actual operation, so that a scheduling scheme of the whole network is formed. The time slots of the nodes are organized into schedule frames (ScheduleFrame, SF) of length L SF Indicating the number of slots contained in the SF. The SF is repeated continuously during each data convergence period. Obviously, the data convergence transmission delay can be reduced by shortening L SF And (5) optimizing.
1.1 energy problem
Table 2 describes the symbols used in the present method and their meanings. The energy consumption of this part is ignored considering that the energy consumption of the node to switch from the active state to the dormant state is much smaller than the cost of the opposite procedure.
Table 2 symbols and their meanings
Given a data convergence period, its schedule frame is SF, node s, according to the definition of Table 2 i The total energy consumption during the data convergence period can be calculated using equation (1).
In the formula (1), the components are as follows,and->All represent a state switch, and therefore, can get +.>
Similarly, in one data convergence period, node s i The total energy consumption to perform the state switch is calculated using equation (2):
in one data aggregation period, since each data packet must be aggregated to Sink, the energy of transmitting and receiving the data packet in equation (1) can be regarded as constant. Therefore, in order to minimizeObviously, the algorithm should be optimized +.>If and only if node s i The number of state switches of (a) satisfies->When (I)>Has the minimum value.
1.2 Wireless interference model
One major constraint when scheduling node activity is radio interference experienced by the node, which includes two types: the first is environmental background interference and the second is radio signal interference from other nodes that are active at the same time. The second type of algorithm is designed to avoid such wireless signal interference mainly in view of the fact that the second type is the main factor affecting the data transmission quality of the node. In particular, protocol interference models are employed herein to model the mutual interference of data transmission activities between nodes. Fig. 1 depicts the effective communication distance and interference distance of a node, where λ represents the interference distance in a multiple of the communication distance.
For node s i And s j Error-free data transmission from s within a time slot i Send to s j Is required to be as follows
And (3) is shown in the formula.
In the formula (3), S represents a node set, d i,k Representing node s i And node s k Is the Euclidean distance s k Representing node s i And s j Is a neighbor node of (a). Here, λ=2.
According to the protocol interference model, if the sender s during the data transmission process of the node i 、s j Or receiving end r i 、r j There is a case where transmission interference is considered to exist and data cannot be transmitted in parallel in the same slot.
(1)d si,sj ＜λd th I.e. s i 、s j In the interference range, at this time, node s i ，s j Data transmission cannot be performed in the same slot.
(2)d si,rj ＜λd th Or d sj,ri ＜λd th I.e. s i 、r j Or s j 、r i In the interference range, at this time, node s i Will interfere with r j ，s j Will interfere with r i Thus s i ，s j Data transmission cannot be performed in the same slot.
In summary, the time-to-energy optimization problem considered herein is described as follows: for a given data aggregation tree, the method optimizes the state switching energy of the nodes in the data aggregation period, and simultaneously optimizes the data aggregation time through time slot reuse. The formalization of the problem is described as follows, according to the symbol definitions in table 2:
wherein constraint 1 indicates that each node will faithfully forward its own generated (one data packet per data convergence period) and all received data packets; constraint 2 indicates that in the same time slot t, the node can only be in a transmitting or receiving state; constraint 3 indicates that two nodes utilize different channels (i.e) The data can be transmitted without interference in the same time slot t; constraint 4 indicates that when the distance between two nodes is smaller than the interference distance, the two nodes cannot use the same channel in the same time slot t (i.e. +.>) And transmitting the data.
2. Method design
The multi-channel time slot reuse scheduling method for time optimization, abbreviated as MCSRS algorithm, realizes the optimization of energy consumption and transmission delay by reducing the state switching times of nodes and realizing the parallel transmission of data by utilizing multiple channels. The MCSRS algorithm consists of two parts: (1) A continuous time slot allocation algorithm based on node load, wherein the algorithm is used for reducing the state switching times of the nodes; (2) The node time slot scheduling algorithm utilizes multi-channel parallel transmission, reduces the mutual interference of data transmission activities among nodes, shortens the length of SF and optimizes the data convergence delay.
The workload for a node is typically represented by the amount of data received and transmitted. For generalization, let the sampling frequency of the sensor node be η, and the data amount generated by each sampling be l, then node s i The amount of data transmitted and the amount of data received in the data convergence period can be calculated by equation (4).
Wherein n represents the node number of the sensor network, n c Representing node s i Is a number of child nodes. In this context, in order to simplify the problem, η has a value of 1, i.e. the node samples only once per data aggregation period. Therefore, the expression (4) can be simplified to the expression (5).
2.1 method description
The following diagram describes the workflow of the MCSRS algorithm. The time slot allocation of the nodes starts from sink nodes, and adopts Breadth First Search (BFS) algorithm to assign continuous time slots for the nodes layer by layer from top to bottom. After each node completes the pre-allocation of the time slots, it needs to be verified whether the time slot allocation meets the conflict-free condition (expressed by constraint 3, 4) of the protocol interference model. If the conflict-free condition is met, the preassigned time slot is formally allocated to the node; otherwise, the node will execute a collision-free slot assignment algorithm to find consecutive slots that meet the collision-free condition and assign to the node. When all nodes have completed slot allocation, the algorithm will perform a slot transformation to adjust the slot allocation for the entire network to a schedule frame starting with sequence number 1.
The algorithm inputs the number n of available channels for the route tree which is constructed completely ch . When there is a nodeWhen no time slot is allocated, the MCSRS algorithm is specifically executed as follows:
1. performing breadth-first search (BSF) algorithm to find node s waiting for allocation of time slots j ；
2. According to the workload of the node, preallocation of continuous time slots to the nodeAnd->Respectively denoted as node s j The smallest time slot sequence number and the largest time slot sequence number in the allocated continuous time slots. When the algorithm allocates a slot for a node from sink to top, its first child node s 1 Is->
3. According to the wireless interference model, when the neighbor node s i And s j Is less than 2d th Time s i Is s j Is a non-interfering node of (a); traversing all nodes in the network to construct node s j Interference set is=is j ∪{s i }(d si,sj <2d th ) The method comprises the steps of carrying out a first treatment on the surface of the 4. Traversing the interference set IS, and constructing an allocated time slot set AS (as= { AS) according to the time slots allocated by the nodes in the set ch1 ∪AS ch2 ∪...∪AS chn })；
5. Traversing CSA j p And searches for a channel chx (1. Ltoreq.x. Ltoreq.n) ch ) Is set of time slots AS chx Whether the time slot exists; if so, the channel sequence number is incremented by 1 and the CSA is re-traversed j p In (c) is cycled through until from n ch Finding one of the channels (e.g., chx) to satisfy CSA j p Is the CSA j f The method comprises the steps of carrying out a first treatment on the surface of the If the CSA is not found to be satisfied j p Allocating a required channel, and executing a step 6; otherwise, executing the step 7;
6. CSA is carried out j p Updated toTurning to step 5;
7. CSA to be found finally j f Channel chx assigned to node s j And record node s j According to CSA j f Updating the load of the channel chx;
8. when all node slot assignments are completed, slot transformations are performed. The first time slot sequence number allocated by sink node is maxSN, because of the scheme of time top-down layer-by-layer allocation and time slot sequence number decreasing, the time slot sequence number gradually becomes smaller in the allocation process, and the minimum time slot sequence number obtained after all nodes allocate time slots is minSN, so that the time slot sequence number of each node can be adjusted according to the formula (6), and the time slot sequence number of the scheduling frame SF is changed to be from 1.
In the above-mentioned method, the step of,and->Respectively denoted as node s j The smallest time slot sequence number and the largest time slot sequence number in the allocated continuous time slots.
3. Example analysis
This section describes a specific application case of the algorithm. Fig. 3 shows the network topology in a case study. The network consists of a sink and 10 sensor nodes. In one data aggregation period, each node generates a unit data packet and aggregates the unit data packet to the sink through a multi-hop path. During the aggregation process, the data is not fused.
Based on the above description, the MCSRS algorithm performs as follows:
the first step: and calculating the workload of each node in the network, wherein the workload of each node is calculated by the following formula.
W i ＝W c +W si ,0≤c≤n,1≤i≤n
Wherein W is c Representing node s i In total, to be sent to s i W is the data volume of (2) si Representing node s i The workload generated per cycle, herein a value of 1.
Thus, the work amount of each node in the network shown in fig. 3 is calculated as follows:
s1：W 1 ＝W 4 +W s1 ＝4；
s2：W 2 ＝W s2 ＝1；
s3:W 3 ＝W 5 +W 6 +W s3 ＝5；
s4:W 4 ＝W 7 +W 8 +W s4 ＝3；
s5:W 5 ＝W 9 +W s5 ＝2；
s6:W 6 ＝W 10 +W s6 ＝2；
s7:W 7 ＝W s7 ＝1；
s8:W 8 ＝W s8 ＝1；
s9:W 9 ＝W s9 ＝1；
s10:W 10 ＝W s10 ＝1；
and a second step of allocating continuous time slots for the nodes, wherein the continuous time slots meeting the conflict-free conditions are allocated for the nodes by utilizing a conflict-free time slot assignment algorithm. The specific process is as follows: firstly, constructing an interference set IS for each node; secondly, constructing an allocated time slot set AS according to an interference set IS corresponding to the node, wherein time slots in the set cannot be allocated to the node; finally, according to the available channels and AS, the conflict-free continuous time slot CSA which can be allocated by the node is found. Let Sink assign a time slot 50 as the last sequence number (maxSN) of the present network to a node and the available channels are 2 channels, the load of each channel is expressed as: load ch The initial value is:next, sink uses BFS algorithm to obtain a child node list { s1, s2, s3}, and then CSA allocated for s1, s2, s3 is as follows:
wherein,representing node s i Is->Minimum slot number,/, of (2)>Representing +.>Is a maximum slot number of (c). Because of->Thus, CSAs of nodes s1, s2, s3 all use channel 1, and can be:
the allocation procedure of consecutive time slots will now be specifically described by taking the node s4 as an example. Due to parent node s1 of s4Thus, it isMinimizing the number of node state switches, +.>Next, according to the protocol interference model employed herein, +.>
Since BFS is employed to search for child nodes, only nodes s1, s2, s3 are assigned CSA. The following formula can be obtained:
and because ofThus, finally +.>
The above process is continuously cycled, and finally, the conflict-free continuous time slot CSA allocated by each node in the network shown in fig. 3 is as follows:
the loading conditions for channel 1 and channel 2 are as follows:
load c1 ＝{36,42(reuse),43(reuse),37-38, 39-40,41-50}
load c2 ＝{38,44-46}
and a third step of: the slot transformation is performed such that the slot sequence number of the network scheduling frame SF starts from 1. In the second step, minsn=36, and therefore, for the time slot of the node, the time slot transformation can be made as follows.
Finally, the time slots allocated by the nodes are shown in fig. 4.
In the case, it can be seen that the proposed method can utilize the multi-channel technology to minimize the state switching times of the nodes, and meanwhile, because the nodes with wireless conflicts, such as s2, s3 and s4, adopt different channels to perform data transmission, the same time slot can be reused, thereby shortening the length of the scheduling frame SF and optimizing the data convergence time.
Currently, in the latest wireless sensor network standard ieee802.15.4, multichannel transmission is definitely supported, so that development of a data convergence transmission protocol using a multichannel technology has very important significance for improving transmission efficiency, reducing delay and improving energy efficiency.
4. Performance comparison
Matlab was used as the experimental platform, with the number of nodes increasing stepwise from 100 to 1000 in each set of experiments, with experimental areas 100m x 100m. TDMA, oneShotTDMA was chosen as the subject of the experiment. TDMA is a conventional time division multiplexing protocol, and uses single channel transmission, whereas oneshotdtdma combines multiple channels with TDMA, and optimizes the number of node state switches by arranging different channels for successive time slots of a node. To avoid performance differences due to random variations in network topology, all experimental results were derived from the performance averages of 100 random networks. All networks construct a routing tree using a minimum spanning tree algorithm.
Influence of sink position
The section examines the effect of Sink position change on algorithm performance. In these experiments, the effective transmission distance of the node was set to 20m, and the wireless interference distance of the interference model node used was set to 40m.
1) Performance of Sink at (50, 100)
Fig. 5 (a) shows the number of state switches at the completion of data aggregation. It can be seen from the figure that as the number of nodes increases from 100 to 1000, the number of state switches of the node also increases. Note that when the number of channels used ch=1, 2, the node state switching times using the MCSRS protocol are significantly higher than the TDMA and oneshotdtdma protocols. One possible reason is that the nodes have multiplexed time slots, resulting in a division of consecutive time slots into at least two parts, increasing the number of state switches of the node. When ch=2, consecutive slots can be allocated to two channels, which can reduce the number of state switches of the node. Therefore, the number of state switches of the MCSRS protocol significantly decreases with an increase in the number of available channels. However, when ch=3, 4, the number of state switches of the MCSRS protocol is comparable to oneschottdma already.
Fig. 5 (b) depicts the number of time slots required to complete data aggregation for all nodes. From the figures the following conclusions can be drawn: (1) The number of time slots required for data aggregation increases rapidly with the number of nodes; (2) When ch=1, compared with TDMA, the MCSRS protocol obviously reduces the number of slots, shortens the length of the scheduled frame, which is mainly beneficial to slot reuse among nodes; (3) When ch=2, the number of slots of MCSRS and oneshotdmas are both less than TDMA, indicating that multiple channels can reduce the number of node state switches and the number of slots simultaneously. In addition, the number of time slots of the MCSRS is smaller than oneshotTDMA, which further reuses the time slots under the premise of an interference model, thereby optimizing the data convergence time; (4) When ch=3, 4, the number of slots of the MCSRS is not much different from that of ch=2, indicating that more channels cannot optimize the data convergence time, but the node state switching times can be further reduced, because it can be seen from fig. 5 (a) that the node state switching times of the MCSRS protocol decrease with an increase in ch.
2) Performance of Sink at (50, 50)
When Sink is at (50, 50), the algorithm performance is shown in fig. 6 (a) and 6 (b). As can be seen from fig. 6 (a), the node state switching times increase with increasing node number, and the MCSRS protocol still generates the most state switching times when ch=1. However, the number of node state switches is reduced by at most about 10% compared to fig. 5 (a). Fig. 6 (b) shows the number of slots required for data aggregation. As can be seen, TDMA still requires the most time slots to complete data aggregation. Compared with fig. 5 (b), when ch=1, 2,3, the number of slots of MCSRS and oneshotdmas is significantly reduced, and the slot number difference of the schedule frame generated by MCSRS and oneshotdmas is reduced.
B. Influence of transmission distance
This section describes the effective transmission distance versus algorithm performance. In the experiment, the effective transmission distance of the node is 15m and 20m respectively, so the corresponding wireless interference distance is 30m and 40m.
Fig. 7 (a) depicts a case where the number of node state switches increases with an increase in the number of nodes for different transmission distances. From the figures it can be derived that: when the number of nodes is the same, increasing the transmission distance helps to reduce the number of node state switches, possibly because increasing the effective transmission distance will result in a decrease in the number of hops of the longest path from the leaf node to Sink in the routing tree, thereby allowing more nodes to be allocated to consecutive time slots. When the number of available channels ch=2, since the same slot can be reused in two channels, the number of node state switches is further reduced, and the conclusion can be confirmed from the graphs of oneshotdma and MCSRS.
Fig. 7 (b) shows the slot requirements for completing data aggregation under the same conditions. As can be seen from the figure, the number of slots decreases more significantly with increasing transmission distance. Meanwhile, MCSRS has a minimum slot number requirement that yields a significantly smaller number of slots than TDMA and oneshotdtdma.
Fig. 8 (a) and 8 (b) respectively describe the change of the node state switching times and the time slot number of the algorithm under different transmission distance conditions when Sink is located at (50, 50). As can be seen from the figure, compared with the network with Sink at (50, 100), the state switching times and the time slot number of the algorithm are reduced under the same transmission distance condition, which shows that the algorithm performance can be obviously improved by reducing the distance (measured by hop number) of the longest transmission path in the routing tree. As can be seen from fig. 8 (a), as the number of nodes increases, the difference between the MCSRS and the state switching times of TDMA and oneshotdtdma becomes significantly larger, which indicates that the slot reuse increases the node state switching times under the constraint of the interference model. Fig. 8 (b) shows that slot reuse significantly reduces the slot number requirements and reduces the data aggregation time. Specifically, under comparable network conditions, MCSRS uses only half the number of slots of TDMA, 2/3 of the number of multislots of oneshotdmas.
Combining fig. 5 to 8, MCSRS can significantly shorten the length of a scheduled frame at various network scales when the number of available channels is equal to 2. Its scheduling frame length is only 50% of TDMA, reduced by about 10% compared to oneshotdtdma. Therefore, MCSRS can significantly optimize the data convergence time.
In addition, the continuous time slot allocation based on the receiving end adopted by the MCSRS can reduce the state switching times of the node as much as possible, thereby reducing the energy consumption of the node. As can be seen from fig. 5 and 6, when the number of available channels is 3 or 4, the MCSRS significantly shortens the scheduling frame length compared to TDMA, and also reduces the number of node state switching times, thereby reducing the state switching energy consumption of the node.
Claims (3)
1. The time-optimized multi-channel time slot reuse scheduling method is characterized in that: the method comprises the steps of performing time slot reuse scheduling on a wireless sensor network comprising 1 sink node and n sensor nodes, wherein the specific steps comprise:
s1: the time slot allocation of the nodes starts from sink nodes, a breadth-first search algorithm is adopted, continuous time slots are assigned for the nodes layer by layer from top to bottom, and the continuous time slots are pre-allocated for the nodes according to the workload of the nodes And->Respectively denoted as node s j The smallest time slot sequence number and the largest time slot sequence number in the allocated continuous time slots, when the algorithm allocates time slots for the nodes from top to bottom from sink, the first child node s thereof 1 CSA of (C) 1 r=maxsn, which represents the first slot number allocated by sink node;
s2: after each node finishes time slot pre-allocation, whether the time slot allocation meets a conflict-free condition of a protocol interference model is required to be verified, wherein the conflict-free condition is that (1) when two nodes utilize different channels to transmit data in the same time slot without interference, (2) when the distance between the two nodes is smaller than the interference distance, the two nodes cannot transmit data in the same time slot by utilizing the same channel;
s3: if the condition in step S2 is satisfiedConflict-free, pre-allocated time slot CSA j p Assigning formally to the node; otherwise, the node will execute a collision-free time slot assignment algorithm to find consecutive time slots meeting the collision-free condition and assign to the node;
s4: when all nodes complete the time slot allocation, the algorithm will execute the time slot transformation, thereby adjusting the time slot allocation of the wireless sensor network to a schedule frame starting from sequence number 1.
2. The time-optimized multi-channel slot reuse scheduling method according to claim 1, characterized in that: the specific implementation method of the conflict-free time slot assignment algorithm in the step S3 comprises the following steps:
step S3.1, traversing an interference set IS, and constructing an allocated time slot set AS according to the time slots allocated by the nodes in the set;
step S3.2, traversing CSA j p And searches a set of time slots AS of a channel chx chx X is more than or equal to 1 and less than or equal to n if the time slot exists ch ，n ch Is the number of available channels; if so, the channel sequence number is incremented by 1 and the CSA is re-traversed j p In (c) is cycled through until from n ch One channel is found out from the channels to meet CSA j p Is the CSA j f The method comprises the steps of carrying out a first treatment on the surface of the If the CSA is not found to be satisfied j p Allocating a required channel, and executing step S3.3; otherwise, executing the step S3.4;
step S3.3, CSA is carried out j p Updated toTurning to step S3.2;
step S3.4, CSA to be found finally j f Channel chx assigned to node s j And record node s j According to CSA j f The load of the channel chx is updated.
3. The time-optimized multi-channel slot reuse scheduling method according to claim 1, characterized in that: the time slot conversion process in step S4 is as follows: because the adopted time slots are distributed layer by layer from top to bottom, the time slot sequence numbers gradually become smaller in the distribution process, and the minimum time slot sequence number obtained after all nodes distribute the time slots is set as minSN, the time slot sequence number of each node can be adjusted according to the formula (6), and the time slot sequence number of a scheduling frame SF is changed to be from 1;
in the method, in the process of the invention,representing allocation to nodes s i The smallest slot number of the slots, +.>Representing allocation to nodes s i The largest slot number of the slots of (a).
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111301278.9A CN114025429B (en) | 2021-11-04 | 2021-11-04 | Time-optimized multi-channel time slot reuse scheduling method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111301278.9A CN114025429B (en) | 2021-11-04 | 2021-11-04 | Time-optimized multi-channel time slot reuse scheduling method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114025429A CN114025429A (en) | 2022-02-08 |
| CN114025429B true CN114025429B (en) | 2024-04-16 |
Family
ID=80060988
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111301278.9A Active CN114025429B (en) | 2021-11-04 | 2021-11-04 | Time-optimized multi-channel time slot reuse scheduling method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114025429B (en) |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105072673A (en) * | 2015-07-13 | 2015-11-18 | 河南科技大学 | High-energy efficiency node scheduling method based on multi-channel TDMA |
| CN105898880A (en) * | 2016-04-08 | 2016-08-24 | 河南科技大学 | Distributed time slot distribution method used for enhancing network data delivery reliability |
| CN111093217A (en) * | 2019-12-30 | 2020-05-01 | 洛阳师范学院 | Lightweight interference measurement algorithm based on TDMA |
| CN111615203A (en) * | 2020-06-11 | 2020-09-01 | 北京印刷学院 | Task-driven joint channel time slot allocation method facing data center |
| CN111935824A (en) * | 2020-05-29 | 2020-11-13 | 洛阳师范学院 | Wireless resource allocation strategy updating method, device, equipment and storage medium |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7046639B2 (en) * | 2000-09-29 | 2006-05-16 | The Regents Of The University Of California | System and method for ad hoc network access employing the distributed election of a shared transmission schedule |
| EP4098061A4 (en) * | 2020-01-27 | 2024-01-17 | Trilliant Networks, Inc. | Method and system for multi-channel beaconing in a time slotted channel hopping network |
-
2021
- 2021-11-04 CN CN202111301278.9A patent/CN114025429B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105072673A (en) * | 2015-07-13 | 2015-11-18 | 河南科技大学 | High-energy efficiency node scheduling method based on multi-channel TDMA |
| CN105898880A (en) * | 2016-04-08 | 2016-08-24 | 河南科技大学 | Distributed time slot distribution method used for enhancing network data delivery reliability |
| CN111093217A (en) * | 2019-12-30 | 2020-05-01 | 洛阳师范学院 | Lightweight interference measurement algorithm based on TDMA |
| CN111935824A (en) * | 2020-05-29 | 2020-11-13 | 洛阳师范学院 | Wireless resource allocation strategy updating method, device, equipment and storage medium |
| CN111615203A (en) * | 2020-06-11 | 2020-09-01 | 北京印刷学院 | Task-driven joint channel time slot allocation method facing data center |
Non-Patent Citations (3)
| Title |
|---|
| Cooperation-based Scheduling Algorithm in Wireless Multimedia Sensor Networks;Bo Zeng;《IEEE》;20111010;全文 * |
| 基于多信道的能量高效传感器节点调度算法;张治学;《计算机工程》;20150915;第41卷(第9期);全文 * |
| 增强包投递的分布式时隙分配机制;曾波;王辉;;计算机工程与设计;20171116(11);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114025429A (en) | 2022-02-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Liu et al. | On the hybrid using of unicast-broadcast in wireless sensor networks | |
| Bahbahani et al. | A cooperative clustering protocol with duty cycling for energy harvesting enabled wireless sensor networks | |
| Liu et al. | A cooperative SWIPT scheme for wirelessly powered sensor networks | |
| CN109673045B (en) | Wireless sensor network time slot allocation multi-hop synchronous transmission system and method | |
| CN104507168A (en) | Distributed topology control method for cognitive Ad Hoc network | |
| Bhola et al. | A study on research issues and challenges in WSAN | |
| CN105554888A (en) | Link multi-rate-based multi-radio frequency multi-channel wireless Mesh network channel allocation algorithm | |
| Liu et al. | Energy-efficient capacity optimization in wireless networks | |
| CN106162798A (en) | The joint Power distribution of radio sensing network energy acquisition node cooperation transmission and relay selection method | |
| Hu et al. | An energy-efficient overlapping clustering protocol in WSNs | |
| Dang et al. | A hybrid multi-channel MAC protocol for wireless ad hoc networks | |
| Darabkh et al. | Impairments-aware time slot allocation model for energy-constrained multi-hop clustered IoT nodes considering TDMA and DSSS MAC protocols | |
| CN106658523B (en) | Recognize the distributed topology approach that K channel-connectivity is constructed in AdHoc network | |
| CN105072673B (en) | A kind of energy-efficient node scheduling method based on multichannel TDMA | |
| CN114025429B (en) | Time-optimized multi-channel time slot reuse scheduling method | |
| Gholami et al. | Adaptive and distributed TDMA scheduling protocol for wireless sensor networks | |
| Djidi et al. | The revenge of asynchronous protocols: Wake-up Radio-based Multi-hop Multi-channel MAC protocol for WSN | |
| Jung et al. | Distributed slot scheduling for QoS guarantee over TSCH-based IoT networks via adaptive parameterization | |
| Azad et al. | DCDS-MAC: A Dual-Channel Dual-Slot MAC Protocol for Delay Sensitive Wireless Sensor Network Applications. | |
| Yao et al. | Multicast scheduling algorithms for battery-free wireless sensor networks | |
| Lu et al. | A modified TDMA algorithm based on adaptive timeslot exchange in ad hoc network | |
| Gong et al. | A multi-channel cooperative MIMO MAC protocol for wireless sensor networks | |
| Lee et al. | Multi-channel TDMA link scheduling for wireless multi-hop sensor networks | |
| Pandey et al. | An energy efficient clustering-based load adaptive MAC (CLA-MAC) protocol for wireless sensor networks in IoT | |
| Adelani et al. | Balanced multi-channel data collection in wireless sensor networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |