KR100970386B1 - Timing scheduling method and device between sensor nodes in wireless sensor network - Google Patents

Abstract

The timing scheduling method between sensor nodes in a wireless sensor network according to the present invention classifies a plurality of sensor nodes in a cluster into a plurality of groups, allocates each time slot to each of the classified groups, and assigns the time slots to the allocated time slots. By performing data communication accordingly, collision between sensor nodes can be prevented, and the sensor node can operate in a sleep mode during a period not corresponding to its time slot, thereby minimizing power consumption of the sensor node. .

Description

Timing and apparatus for scheduling timing between sensor nodes of the Wireless Sensor Network}

The present invention proposes a series of such methods in which a wireless sensor network system classifies sensor nodes into groups and assigns time slots to the groups. An object of the present invention is to prevent collisions between sensor nodes by allowing each sensor node to communicate with each other by timing scheduling.

The use of directional antennas in wireless networks has been widely discussed in the art. However, most of the discussion has focused on using directional antennas with ad hoc wireless networks. The problem with this approach is power consumption. CSMA-based MAC protocols, such as IEEE 802.11, are not practical for wireless sensor networks because of their high power consumption. This is because the nodes must be active most of the time for sensing the carrier. Furthermore, the use of directional antennas in ad hoc wireless networks introduces new communication problems such as deafness and directional hidden terminals.

In the existing omnidirectional environment, Directional Hidden Terminal has A, B, and C nodes side by side, AB and BC are at a distance that can communicate with each other, and AC is at a distance that cannot communicate with each other. If C thinks it can communicate with B and sends data to B at the same time, B means that a collision has occurred and neither is received. Deafness means that when node A is looking at a certain direction using a directional antenna, node B facing A in the other direction can communicate with A until A resets the antenna in direction B. It means no state.

These problems are more influential as the number of nodes increases, as in wireless sensor networks. In order to avoid contention between nodes, a time schedule MAC has been presented. The use of the time schedule MAC increases network life and eliminates contention between nodes. However, calculating a time schedule in a special case where there are a large number of nodes, such as in a wireless sensor network, is a complex and expensive task. In summary, the use of directional antennas in wireless sensor networks using existing channel approaches presents problems with high power consumption, high contention rate and complex schedule calculation.

The technical problem to be solved by the present invention is to classify a plurality of sensor nodes in a cluster into a plurality of groups, to perform data communication according to each assigned time slot, the timing between sensor nodes in a wireless sensor network A scheduling method and apparatus.

In order to achieve the above object, a timing scheduling method between sensor nodes in a wireless sensor network according to the present invention comprises the steps of: classifying a plurality of sensor nodes in a cluster into a plurality of groups; Assigning each time slot to each of the classified groups; And performing data communication according to the allocated time slot.

The classifying the plurality of sensor nodes into the plurality of groups may include collecting neighbor relationship information of neighboring nodes neighboring the sensor nodes; And specifying the group of sensor nodes according to the shortest path tree using the collected neighbor relationship information.

The step of assigning each time slot to each of the classified groups allocates each time slot in consideration of the neighbor relationship information of neighboring nodes neighboring the sensor nodes and the collision relationship of each neighbor node according to the neighbor relationship information. Characterized in that.

The step of performing data communication according to the allocated time slot is characterized in that the sensor nodes are switched to the sleep mode in a period not corresponding to their time slot.

In order to achieve the above object, the computer-readable recording medium according to the present invention comprises the steps of: classifying a plurality of sensor nodes in a cluster into a plurality of groups; Assigning each time slot to each of the classified groups; And a program for executing the step of performing data communication in accordance with the allocated time slot.

 In order to achieve the above object, a timing scheduling apparatus between sensor nodes in a wireless sensor network according to the present invention includes a plurality of sensor nodes in a cluster; And a cluster head node for classifying the plurality of sensor nodes into a plurality of groups and allocating respective time slots to the classified groups, wherein the sensor nodes and the cluster head node are allocated according to the allocated time slots. It is characterized in that to perform data communication between.

The plurality of sensor nodes each include a multi-domain antenna for receiving signals in all directions and transmitting signals to a specific area and a transceiver for controlling communication.

The cluster head node collects neighbor relationship information of neighboring nodes adjacent to the sensor nodes, and designates a group of the sensor nodes according to the shortest path tree using the collected neighbor relationship information.

The cluster head node allocates each time slot in consideration of the neighbor relationship information of neighbor nodes neighboring the sensor nodes and the collision relationship of each neighbor node according to the neighbor relationship information.

The sensor nodes may be switched to a sleep mode in a period not corresponding to their time slot.

The method and apparatus for scheduling timing between sensor nodes in a wireless sensor network according to the present invention classify sensor nodes into a plurality of groups and assign a time slot of only the group to each classified group. By allowing each of the sensor nodes to communicate with each other by a series of timing scheduling, it is possible to prevent collisions between the sensor nodes, to minimize the power consumption of the sensor nodes, and to maintain the life of the sensor node for a long time.

Hereinafter, a timing scheduling method between sensor nodes in a wireless sensor network according to the present invention will be described in detail with reference to the accompanying drawings.

In wireless sensor network (WSN) applications under consideration, the wireless sensor network architecture is hierarchical and consists of clusters of sensors with one cluster head for each cluster. Data collected by sensor nodes in one cluster is forwarded to the cluster head via a number of hops. The downstream traffic generated towards the cluster head is then directed to an upper-tier gateway node, ultimately to a single network location such as a command & control center. In addition, messages generated at this central location must be forwarded to sensor nodes in the opposite direction. Since the network is divided into a number of disjoint clusters, each case of the protocol is executed in each cluster. In the present invention, the Sectored Antenna-Based Medium Access Control (SAMA) protocol will be described below with respect to one cluster.

Because of the importance of data, reliability of message delivery is a top priority for network operation. To meet this condition, the packet loss rate should be minimized. Since the wireless communication medium is shared, packet collisions due to simultaneous packet transmission should also be avoided. In addition, communication using directional antennas of wireless sensor networks has major problems to be solved, such as Directional Hidden Terminal and Deafness, in addition to limited resources. Therefore, SAMAC has three goals. First, high packet forwarding rates are achieved by minimizing channel contention and packet collisions in a shared wireless communication medium. Second, by utilizing the spatial recycling capabilities of the directional antenna, the throughput characteristics of the sensor network are improved. Third, the life of the sensor battery is extended by minimizing power consumption. The SAMAC protocol can be described as a combination of time division multiple access (TDMA) and four-way signal handshake via packet exchange, ie channel contention using the RTS-CTS-DATA-ACK sequence as in IEEE 802.11. This mechanism is based on dividing the protocol operating time into individual time slots in TDMA fashion. During each time slot, one or more node groups can communicate without affecting other pairs. Pairs that are potentially contended are scheduled to communicate in different time slots. The SAMAC protocol allows the sensors to communicate effectively in certain time slots. At other times, the sensors operate in sleep mode to save power, turning off their antennas to minimize power consumption. Sensor antennas are turned on during the time slot in which the sensor is scheduled to communicate. To this end, all nodes need a time schedule, respectively. The calculation of time schedules is performed by a resource-rich cluster head and then distributed to sensors in one cluster. In order to perform a schedule calculation, the cluster head needs complete neighborhood relation information obtained from all the sensors in that cluster.

In the wireless sensor network system, the present invention classifies sensor nodes into a plurality of groups, and assigns a time slot of the group to each of these classified groups. Scheduling allows each sensor node to communicate with each other. To this end, each of the sensor nodes comprises a multi-zone antenna that receives signals in all directions and transmits signals to a particular sector and a transceiver that controls communication. In the multi-domain antenna, the angular transmission total area includes an omnidirectional 360 degree full area. Information transmission is carried out by selecting an area. In reception, the active area immediately receives the information without delay and passes it to the higher layers in the communication stack. The time slot assignment takes into account neighbor relations between sensor nodes and conflict relations between each sector of neighbor nodes. In addition, the sensor node is switched to the sleep mode in a period not corresponding to its time slot.

1 is a flowchart of an embodiment for explaining a timing scheduling method between sensor nodes in a wireless sensor network according to the present invention.

First, a plurality of sensor nodes in a cluster are classified into a plurality of groups (step 10). Sensor nodes do not have any preloaded neighbor relationship information. Thus, each node sends its information to the cluster head node to all neighbor nodes when network operation begins.

FIG. 2 is a flowchart of an exemplary embodiment for explaining a step of classifying a plurality of sensor nodes in a cluster of FIG. 1 into a plurality of groups.

Collecting neighbor relationship information of neighbor nodes neighboring the sensor nodes (step 20). If two nodes can receive each other's packets in a single transmission over a radio link, they are neighbors. Thus, the neighbor relationship between two nodes having a multi-zone antenna includes the IDs of the individual zones through which these nodes can communicate. For example, if node A sends and receives packets through area 2 and node B uses area 4 to communicate with node A, node-area pairs (A, 2) and (B, 4) are neighbors to each other. Corresponds to After neighbor relationships are discovered by each sensor node, these relationships are passed to the cluster head node. The SAMAC protocol collects neighbor information at the cluster head node at the beginning of network operation.

After the twentieth step, the group of sensor nodes is designated according to the shortest path tree using the collected neighbor relationship information (step 22).

The SAMAC protocol forms a group of nodes to divide sensor nodes in a cluster into smaller sets called groups that can be assigned to a single time slot. There is exactly one parent node in the SAMAC group, and all other sensors are child nodes.

Group formation in a cluster is performed by cluster head nodes using neighbor relationships. The group forming process starts at the cluster head and proceeds to the leaf nodes. First, each area of the cluster head node is associated with a different group. Members of these groups are child nodes of the cluster head node in the corresponding area. Second, the areas of child nodes of the cluster head node are considered to form a new group. For example, assuming child node A of the cluster head node, if node A has child nodes on the shortest path tree, then nodes in that area together with node A are considered to be a single group.

3 is a diagram illustrating a process of designating a group for node A. Because region A of node A is already included in the group, other regions can be used to form another additional group. By repeating from the parent node to its child nodes in the shortest path tree, this process continues toward the lip node until all nodes are considered.

After step 10, each time slot is allocated to each classified group (step 12). After the groups in the cluster and the members of each group have been determined, a time slot can be assigned to each group. Before assigning time slots to each group, the cluster head node identifies each group pair for possible common node collisions and common interface conflicts using neighbor relationships.

Neighbor information collected at the cluster head node is used to determine potentially competing radio links in case of simultaneous transmission. These competing radio links are called collisions.

4 shows different types of possible collisions.

In Fig. 4A, sensors A and B are neighboring nodes. Likewise, sensors C and D are neighboring nodes. Thus, to enable communication between nodes A and B, these nodes must be scheduled in the same time slots across regions 2 and 4, respectively. However, the transmission from area 2 of node A is received in area 3 of node D. Thus, if the communication between nodes C and D and the communication between nodes A and B are scheduled in the same time slot, a packet collision can occur between these two transmissions. Therefore, these two transmission pairs should be scheduled in different timeslots if possible. This type of collision is called a common interface collision. On the other hand, another type of collision, called common node collision, is shown in Figs. 4B and 4C. In Figure 4 (b) there are two communication node pairs, A and B and A and C. Nodes B and C communicate with node A on another area of node A. Node A cannot communicate with Nodes B and C at the same time since one node is not capable of simultaneous transmission over more than one area due to hardware limitations. Thus, these two communication pairs must be scheduled in different time slots. In Figure 4 (c), nodes B and C communicate with node A on the same area of node A. In this case, collisions between nodes can be avoided using contention based access mechanisms.

In the schedule assignment of the SAMAC protocol, each group is assigned one or more time periods in which sensor nodes in the group can send packets to each other. In order to avoid group collisions with each other due to allocation of the same time period, time period assignment is considered so that no packet collision occurs in the schedule calculation. Conflicts between nodes in the same group are handled by contention based access control as described above. Allocating a time period to each group is performed by a coloring algorithm starting from the furthest group to the cluster head. The steps of this algorithm can be described as follows. First, the hop distance from the parent node of each group to the cluster head node is determined. This hop distance value indicates the group distance to the cluster head node. The groups are then sorted in descending order according to the distance to the cluster head node. If two groups have the same distance value, the group with more nodes is considered first. The list of groups is then sequentially scanned until a first group without an assigned schedule is found. These groups are assigned colors representing time periods in the multi-hop paths of the groups defined by the shortest path tree. Colors are represented by integers. The selected group is assigned a time period that is preferentially available in the time period set. This time period is not available if there is a conflict with other groups assigned to the same time period. If there is a conflict, the color index is incremented and a new time period is checked for possible allocations. If the color index is increased and the maximum color index is reached, then the maximum color index is assigned to that group. After the time period is assigned to a leaf group, the algorithm is repeated group by group. For each group, the available color indices are assigned in ascending order, starting with the most recently assigned color value. If a time period is found that does not conflict with the previous allocation, this time period is used for allocation. Otherwise, the maximum color index is exceeded and the color index returns to the first time period in the time period set, and all time periods are attempted until the time period of the lip group is reached. In this case, the maximum color index is increased and a new color is assigned to the group. When all groups on this group branch are assigned a color and the cluster head node is reached, the next group is selected as the first group in the list of unassigned groups. This new group corresponds to the group with the hop distance to the next largest cluster head. The color assignment algorithm ends when all groups are scheduled for color assignment.

Fig. 5 (a) shows time slot allocation, and Fig. 5 (b) shows the regions used in each active time slot. X means the node is not active in the time slot.

After the twelfth step, data communication is performed according to the allocated time slot (step 14). At the beginning of network operation, the sensor node is operated in BASIC mode. In BASIC mode, the node does not have any schedule information and there is no differentiation between regions. In BASIC mode, nodes collect information about their neighbors and pass this information to the cluster head. After calculating the time schedule, the cluster head node fills the SCHEDULE packet and distributes the schedule information to its cluster. The SCHEDULE packet includes information on active time slot allocation of all nodes in the cluster. Upon receipt of the SCHEDULE packet, the sensor node extracts the schedule information, delivers the SCHEDULE packet to its neighbors, initializes its configuration, and enters the ADVANCE mode. Eventually, every node in the cluster receives a SCHEDULE packet. Sensor nodes that do not receive SCHEDULE packets cannot participate in the SAMAC protocol and data transfer within the cluster.

While in ADVANCE mode, for each time slot, sensor nodes either turn off their antennas to save power (sleep mode) or keep them in order to engage in communication events. The determination to sleep mode is made by the sensor's time schedule received from the SCHEDULE packet. Exemplary schedule information of Node A is shown in Table 1.

Activation Time slot Active area True 0 2 True One One True 2 3 False 3 X

In this table, a super frame consists of four time slots. In slot 3, node A is not active, and thus does not have a specified area number in SLEEP mode. According to this schedule, when a sensor node is activated, it can communicate through only one of its regions in a given time slot. For example, in Table 1, node A may communicate with neighbors on the third region in time slot 2. Thus, Node A may send a packet on the channel and deliver the received packet to the protocol stack on the third region in timeslot 2. However, Node A cannot send packets to other areas. In addition, packets received from other areas are stored at the physical layer and are not forwarded to SAMAC until SAMAC needs to process these packets.

6 illustrates a timeslot structure in SAMAC. At the beginning of each time slot, nodes check their schedule information to determine if they are active in the time slot. If a node is active in a timeslot, it can participate in communication events. This event participation may be data transmission (TX) or data reception (RX). There is a certain amount of time, called MIN AWAKE TIME, allocated to determine if there is communication with other nodes that need to be processed.

7 is a diagram for explaining a sleep mode mechanism. If this node has no data to transmit and there is no data reception during this MIN AWAKE TIME time, the node decides to enter the SLEEP mode as shown in FIG. In this state, all antennas are turned off to save power. Thus, there is no interaction with the channel until the node turns on its antenna. On the other hand, if there is a communication event (TX / RX), this event is processed immediately.

At the end of each communication (TX / RX) period, the nodes wait for another MIN AWAKE TIME to determine whether there is a new transmit / receive that needs to be performed. If there is no traffic for MIN AWAKE TIME, the node immediately enters the SLEEP mode as shown in FIG. 7 (b), otherwise the traffic is processed.

In FIG. 6, MIN AWAKE TIME means the maximum period of time during which a node can be active in one time slot. After MIN AWAKE TIME from the slot start time, the node enters the sleep mode regardless of its state as shown in FIG. MIN AWAKE TIME is a configuration parameter and represents a duty cycle in ADVANCE mode.

If a node has a packet that must be sent in an active slot, the communication channel must be reserved using a four-way RTS / CTS / DATA / ACK handshake with the recipient node. This signal change mechanism is used to eliminate all conflicts between nodes in the same group. Before transmitting the RTS packet to initiate this process, the node needs to back off from channel access for a certain amount of time.

During the backoff, if the node detects that the channel is busy, the node stops the backoff and waits for the channel to become idle again. Once the channel is free, the node can continue its backoff period. Once the backoff period is complete, the node starts communicating using the RTS / CTS / DATA / ACK order. If the node needs to sleep at MIN AWAKE TIME, the backoff counter is aborted to save the remaining backoff period to be used for the same slot time in the next super frame.

SAMAC has a separate backoff value for each active slot time. For example, when a node has the remaining backoff time at the end of timeslot 1, this value will be used in timeslot 1 of the next superframe. This is necessary because communication activity in different areas of the mode may be different. Thus, SAMAC uses the conventional backoff procedure with the RTS / CTS / DATA / ACK frame order in separate timeslots and stores the backoff state for use in the same time slot of the next superframe. Because each time slot is associated with a different area of the node, SAMAC effectively distinguishes between different traffic in different areas. SAMAC handles two traffic directions. Traffic to the cluster head is called upstream traffic. Meanwhile, traffic from the cluster head is called downstream traffic. SAMAC handles upstream and downstream traffic differently in the backoff procedure. Since the upstream traffic propagates from the sensor to the cluster head and carries urgent data, the backoff window for transmitting the upstream RTS frame is smaller than the backoff window of the downstream traffic. After each failure of the channel reservation due to an incomplete backoff period, the backoff window increases linearly until the upper limit is reached.

Packets that need to be sent using SAMAC are stored inside an internal SAMAC column. SAMAC has a separate column for each time slot. Once the packet arrives at the MAC layer, the next hop is determined. If the packet is an upstream packet, the next hop is the parent of the current node. Thus, the node finds a slot time at which it can communicate with its parent and insert a packet into a designated slot row. Packet insertion is performed at the end of the row and packets are POPed from the end of the row. If a packet cannot be transmitted in the time slot and does not exceed the retransmission limit, it is pushed to the top of the row and processed in the next superframe. 9 illustrates internal SAMAC columns.

Meanwhile, the above-described timing scheduling method between sensor nodes in the wireless sensor network of the present invention may be implemented by computer-readable codes / instructions / programs. Classifying the plurality of sensor nodes in the cluster into a plurality of groups; Assigning each time slot to each of the classified groups; And a computer readable recording medium having recorded thereon a program for executing data communication according to the allocated time slots.

For example, it may be implemented in a general-purpose digital computer for operating the code / instructions / program using a computer-readable recording medium. The computer-readable recording medium may include a magnetic storage medium (eg, ROM, floppy disk, hard disk, magnetic tape, etc.), an optical reading medium (eg, CD-ROM, DVD, etc.) and a carrier wave (eg Storage media, such as through the Internet). In addition, embodiments of the present invention may be implemented as a medium (s) containing computer readable code, such that a plurality of computer systems connected through a network may be distributed and processed. Functional programs, codes and code segments for realizing the present invention can be easily inferred by programmers in the art to which the present invention belongs.

The timing scheduling method between the sensor nodes in the wireless sensor network of the present invention has been described with reference to the embodiment shown in the drawings for clarity, but this is merely illustrative, and those skilled in the art may It will be understood that various modifications and equivalent other embodiments are possible. Therefore, the true technical protection scope of the present invention will be defined by the appended claims.

1 is a flowchart of an embodiment for explaining a timing scheduling method between sensor nodes in a wireless sensor network according to the present invention.

FIG. 2 is a flowchart of an exemplary embodiment for explaining a step of classifying a plurality of sensor nodes in a cluster of FIG. 1 into a plurality of groups.

3 is a diagram illustrating a process of designating a group for node A.

4 shows different types of possible collisions.

5 is a diagram illustrating time slot allocation.

6 illustrates a time slot structure in SAMAC.

7 is a diagram for explaining a sleep mode mechanism.

8 is a diagram for explaining entering a sleep mode after a MIN AWAKE TIME time.

9 illustrates internal SAMAC columns.

Claims (9)

Classifying the plurality of sensor nodes in the cluster into a plurality of groups; Allocating each time slot in consideration of collision relations of neighboring nodes according to neighbor relation information of neighboring nodes neighboring the sensor nodes for each of the classified groups; And And performing data communication in accordance with the allocated time slot. The method of claim 1, wherein classifying the sensor nodes into the plurality of groups comprises: Collecting neighbor relationship information of neighbor nodes neighboring the sensor nodes; And Designating a group of the sensor nodes according to the shortest path tree using the collected neighbor relationship information. delete The method of claim 1, wherein performing data communication according to the allocated time slot And the sensor nodes transition to a sleep mode in a period not corresponding to their time slot. Multiple sensor nodes in the cluster; And The sensor nodes are classified into a plurality of groups, and each time slot is considered in consideration of collision relations of neighbor nodes according to neighbor relation information of neighbor nodes adjacent to the sensor nodes and the neighbor relation information for each classified group. Includes a cluster head node that assigns And data communication between the sensor nodes and the cluster head node according to the allocated time slot. The method of claim 5, wherein the sensor nodes 2. A timing scheduling apparatus between sensor nodes in a wireless sensor network, comprising: a multi-domain antenna for receiving signals in all directions and transmitting signals to a specific area and a transceiver for controlling communication. The method of claim 5, wherein the cluster head node Sensor node in the wireless sensor network, characterized in that for collecting the neighbor relationship information of neighboring nodes neighboring the sensor nodes, and using the collected neighbor relationship information, the group of the sensor nodes according to the shortest path tree. Timing scheduling device between. delete The method of claim 5, And the sensor nodes transition to a sleep mode in a period not corresponding to their time slot.

Images