A novel hybrid broadcast scheduling method for sensor networks

Abstract: Due to the shared nature and mutual interference of wireless channels used in sensor networks, data broadcasting between nodes can lead to resource conflicts. Broadcast scheduling aims to allocate a conflict-free transmission time slot to each node, with the goal of finding the optimal Time Division Multiple Access (TDMA) scheduling solution that minimizes frame length while maximizing channel utilization. This paper proposes a two-stage hybrid broadcast scheduling algorithm based on neural networks. In stage one, an improved vertex coloring algorithm is used to obtain the minimum number of time slots required for scheduling. In stage two, fuzzy Hopfield clustering is used to fuzzily cluster nodes into M classes. Nodes of the same class can be scheduled in the same time slot, while nodes of different classes must be scheduled in different time slots. The algorithm is used to schedule three test topologies. Experimental results show that this algorithm achieves shorter frame lengths and lower network latency than other algorithms, demonstrating the feasibility and effectiveness of the proposed algorithm.

Keywords: Wireless sensor networks; Broadcast scheduling problem; Hopfield neural network; Graph coloring

1 Introduction

Within the monitoring area, tiny nodes that are randomly distributed and integrate sensors, data processing units and wireless communication modules form a wireless sensor network (WSN) through self-organization ^[1] . Nodes in WSN often need to broadcast messages or data for synchronization mechanisms, topology control or route establishment and maintenance. Due to the sharing and openness of wireless links, it is easy to cause mutual conflicts during message transmission. If multiple adjacent nodes of a node broadcast messages to that node at the same time, mutual interference or conflict will inevitably occur and the broadcast messages cannot be correctly sent and received. Most WSN networks require the source node to retransmit at this time, which causes additional energy consumption of the node. Therefore, it is necessary to reasonably schedule the message broadcast of the node to extend the network lifetime ^[2] . Most WSNs use time division multiplexing (TDMA) as the wireless channel sharing and access method ^[3] . This paper studies the broadcast scheduling problem (BSP) of WSN network under TDMA, hoping to achieve message transmission between nodes without conflict under network topology stability and maximize channel utilization.

2. Broadcast scheduling problem

Let the WSN network be an undirected simple graph G = (V, E), where vertex V = {v i } represents a sensor node in the network, and edge E = {e ij } is a transmission link between nodes. If sensor nodes i ∈ V and j ∈ V, and i and j are within each other's sensing radius, then i and j are called one-hop adjacent nodes, i.e., there exists a wireless link eij ∈ E. If there is no one-hop adjacent node between i and j, but there exists an intermediate node k such that e ik  ∈ E and e kj  ∈ E, then nodes i and j are called two-hop adjacent nodes. For a sensor node to correctly send and receive data, it must satisfy the following constraints [3]: 1) A node cannot receive and send data simultaneously. That is, if e ij  ∈ E, then node i and node j must be allocated to transmit data in different time slots, which is called the first type of constraint; 2) A node cannot receive data sent by two or more adjacent nodes simultaneously. That is, if e ij  ∈ E and e kj  ∈ E, then nodes i and k must send data in different time slots to avoid a conflict at node j, which is called the second type of constraint. Define a binary matrix S = {s ij } to represent a transmission schedule, ρ to be the bandwidth utilization of the WSN, and S′ = {S 1 , S 2 , ...} to represent the set of interference-free feasible schedules. The optimal scheduling problem is described as follows: For a given topology WSN network, find the optimal schedule S opt  ∈ S′, which has the shortest frame length S opt and the largest channel bandwidth utilization ρ opt under the conditions of satisfying the first and second types of constraints.

3. A Two-Phase Scheduling Method Based on Neural Networks

Phase 3.1

For a given undirected graph with a topology, the first objective is to minimize the frame slot length, i.e., to complete the scheduling with the minimum number of slots M. The vertex coloring problem (VCP) is NP-complete, and current solutions are mainly heuristic algorithms. Although sequential coloring can only find a suboptimal solution, its complexity is minimal. The computational cost is 1-2 orders of magnitude lower than other optimal and suboptimal algorithms. Considering the limited energy and computational capabilities of sensor nodes, a new vertex coloring algorithm is designed here by combining the maximum saturation and maximum degree criteria. The algorithm includes the following three processing steps: 1) Determine the upper and lower bounds of the frame slot length. For a WSN network with N nodes, the optimal frame length range is Lm≤M≤N, where Lm＝maxdegi＋1, and degi is the degree of node i; 2) Perform initial slot allocation. Let the set of nodes to be initialized be G = {n _{_i}, i = 1, 2, ..., L_{_m} }, G consists of the node n _₁ with the maximum degree in the graph and the adjacent nodes n_{_i} that are l hops away from n_₁. Allocate time slot i to node n_{_i} ; 3) Improved sequential coloring algorithm. Algorithm input: Original WSN topology G = (V, E). Output: Node time slot scheduling matrix S = {S_{_ij}} _{N × M.}

Step 1: Network node topology sorting. Sort the nodes according to the decreasing degree rule and store them in a queue Q = {ni, i = 1, 2, ..., N} to obtain the maximum degree ΔG of the network nodes;

Step 2 : Determine the lower bound of the time slots. Set the initial number of time slots M = ΔG + 1, and the scheduling matrix S = {0} _{N × M} ;

Step 3: Node time slot initialization and scheduling. Without loss of generality, allocate the i-th time slot to node n_{_i} , thus obtaining the set of scheduled nodes G_c = { _{n i}, i = 1, 2, ..., M}. Let S _{_ii} = 1, and the counter P = M + 1.

Step 4 : Sort the unscheduled nodes. Sort the remaining _NLm vertices according to the maximum saturation criterion and store them as a queue.

Step 5 _{: Schedule} node nj in Q′. Search for time slots that satisfy the 2-hop constraint. Let Nc be the number of different time slots. Based on the value of Nc, perform the following processing: ① If _Nc > 1, assign the first available time slot to node nj , _Sij = 1; ② If _Nc = 1, assign the unique time slot to node _nj , _Sij = 1; ③ If _Nc = 0, then there is no free time slot to assign to node _nj , go to Step 7;

Step 6 : Determine if all nodes have been scheduled. If P = N, stop the algorithm; otherwise, set P = P + 1 and go to Step 5.

Step 7 adds a new time slot and reschedules. Let M = M + 1, then go to Step 5. The computational cost of sorting in Step 1 is O(|N|), and the computational cost of sorting in Step 4 is O(|N - Lm|^3), where N is the number of vertices in the network, and Lm is the maximum degree of a vertex plus 1. The computational cost of the entire algorithm is approximately O(|N|^ ₃ ).

3.2 Phase Two

In Phase 2, a fuzzy Hopfield neural network is used to perform fuzzy clustering on the WSN network nodes ^{[4, 5]} . The number of classifications is M obtained in Phase 1, and the input samples are the nodes to be scheduled. All nodes in the same class can be scheduled simultaneously in the same time slot; nodes in different classes must be scheduled in different time slots. Considering an N×M structure Hopfield network, whether node i transmits data in the j-th time slot is determined by the output Pij of the neuron at position (i,j) in the Hopfield. The optimization objective is designed using the constraints in Section 2, namely the Hopfield network energy function E. First, all data packets should be transmitted synchronously in one time slot; second, when node i transmits data in time slot j, all adjacent nodes of node i cannot be assigned to time slot j; finally, when node i transmits data, its two-hop adjacent nodes cannot be assigned to time slot j to transmit data. The magnitude of the energy function E reflects the difference between the current time slot scheduling and the optimal scheduling of the network. After considering all the above constraints, the energy function E designed in this paper is as follows:

Where: _ni represents the i-th node, d_{_ij} is the Euclidean distance between nodes i and j, and the weights w _₁ and w _₂ are positive and satisfy w _₁ + w_₂ = l. The values ​​of the weight coefficients affect the convergence of the network and need to be selected reasonably. _Vi is the i-th type of Euclidean center, i.e., ... The input of the neuron at position (i,j) is I_{_ij} = ( _ni - _vi )^² + ΔI_{_ij}, and the neuron output is Pi_ij . The external activation term ΔI_{_ij} is a constant. The Hopfield network optimization process is as follows:

Step 1: Initialize the output P _{_ij} of neurons (i,j) within the network.

Step 2: Update the fuzzy membership function and recalculate the class centers _vi ;

Step 3: Calculate the energy function using equation (1);

Step 4: Determine if the network has converged to a stable state. If |E(n+1)-E(n)|>ε (ε is the threshold), go to Step 2; otherwise, the network has converged and the algorithm terminates.

4. Experimental Results and Analysis

The scheduling performance of the TS-HNN algorithm was analyzed and compared with that of three methods: average annealing (MFA) ^[2] , Hopfield neural network based on genetic algorithm (HNN-GA) ^[4] , and noisy chaotic neural network (NC-NN) ^[5] . Test networks with three different topologies were used: Case 1 to Case 3 ^[6] . The data packets used in the experiment were of fixed length, and the time slot length was set to the transmission time required for each packet. Data packets were sent and received randomly between nodes according to a Poisson distribution. Each topology was run 50 times, and the average value was taken for comparison. Table 1 shows the minimum network delay η and frame length M obtained by the algorithm (TS-HNN) in this paper and the other three methods. When the number of nodes is small (Case 1) or the average degree is not high (Case 3), all four algorithms can find the optimal frame length M=8. For networks with a large number of nodes and complex structure (Case 2), TS-HNN can also find the suboptimal frame length. Moreover, TS-HNN has the lowest network delay in all three topologies. The scheduling results for Test Topology Case 1 are shown in Figure 1. Black squares represent nodes that can be scheduled in that time slot. Figure 2 details the variation of network latency with the packet service rate. As the service rate increases, the network latency also increases. When the number of nodes is small (Case 1), the latency differences between the four algorithms are not significant, as shown in Figure 2(a). When the number of nodes increases (Case 2), the network latency differences between the four algorithms increase significantly, as shown in Figure 2(b).

5. Conclusion

Scheduling is a classic constrained resource allocation problem. This paper takes sensor networks as the research background and proposes a two-stage broadcast scheduling algorithm based on graph coloring and neural networks. The basic idea of ​​the algorithm is to transform the solution of the broadcast scheduling problem into a two-stage objective optimization: the first stage uses the idea of ​​vertex coloring to search for the frame structure with the shortest number of time slots for a given topology WSN; the second stage uses a fuzzy Hopfield network to add additional collision-free transmission time slots for each node under the above frame structure, so as to enable as many nodes as possible to achieve parallel interference-free transmission within the original frame length, thereby maximizing channel utilization. Simulation experiments demonstrate the effectiveness of the proposed method.

References:

[1]PENG Y, SOONG BH, WANG L.Broadcast scheduling in packet radio networks using mixed tabu-greedy algorithm[J]. Electronics letters, 2004, 40 (6): 375-376.

[2]WANG G,ARISARIN.Optimal broadcast scheduling in packet radio networks using mean gield annealing[J].IEEE Journal on Selected Areas in Communications.1997,15(2):250-260.

[3]YEO J,LEE H.An efficient broadcast scheduling algorithm for tdmad-hoc networks[J]. Computer Operations Research, 2002, 29 (13): 1793-1806.

For details, please click: A Novel Hybrid Broadcast Scheduling Method for Sensor Networks