RU2829497C1 - Method of organizing wireless peer-to-peer self-organizing networks - Google Patents

Abstract

FIELD: communication.

SUBSTANCE: method includes the following steps: obtaining a data packet, extracting key information from the packet and searching for this information in the list of key information of previously received packets, wherein: if there is a record on a packet with the same key information in the list, then this packet is considered to be duplicated and is deleted; if the data packet is not in the list of received packets, it is added, and the counter of the number of received duplicate data packets is set equal to 1; if the data packet is present in the list of received packets, the counter of the received duplicate data packets is increased by 1; if the counter of the number of received duplicate data packets and the counter of the number of transmitted copies of this packet does not exceed a certain predetermined number, then the data packet is transmitted over the air, wherein the data packet transmission counter is increased; if any of these counters exceeds a certain number, then this data packet is removed from the transmission queue; when receiving a data packet over the air, matching of a network feature and a matching of a channel feature are checked.

EFFECT: reduced number of transmitted data packets.

1 cl, 7 dwg

Description

Technical field. The invention relates to the field of communications and can be used in the construction of a wireless self-organizing peer-to-peer mobile network (mobile ad hoc network - MANET) for transmitting data in the form of digital information.

Mobile peer-to-peer networks are self-organizing. In this case, network subscribers communicate with each other via one or several wireless channels. The structure of the network topology can change quickly. Unlike other types of networks, such as trunking, cellular or satellite, MANET networks do not imply the presence of any stationary infrastructure. The network is formed dynamically in real time and depending on the relative position of subscribers. In this case, the number of subscribers can increase or decrease depending on the radio visibility zone, the inclusion of new devices or their deactivation.

MANET networks are attractive because they do not require preliminary planning and configuration. They also do not require a connection to a stationary infrastructure (base stations, communication centers). Together, this allows for easier use and reduced deployment time. However, networks of this type face the problem of signal transmission through numerous obstacles and an almost continuously changing topology.

State of the art. A routing method for wireless mobile self-organizing data transmission networks is known according to the Russian Federation patent for invention 2486703, IPC H04W 40/30. The technical result of the invention consists in reducing the time for searching for an optimal route. Updating entries in routing tables in each of the network nodes occurs by exchanging information about the network topology contained in service packets. Service packets that do not require fragmentation are transmitted over low-speed first-level communication channels characterized by the first metric, and user packets are transmitted over high-speed second-level communication channels characterized by the second metric. Information about network node communication updates is transmitted by service packets of the first type, and after establishing a new connection with a node that is not part of the network, or between two nodes belonging to different networks, information from the communication table is transmitted by service packets of the second type. The lifetime of service packets depends on the network topology known to the network node, and the time intervals between the sending of service packets are directly proportional to the total number of connections between network nodes.

Also known is a hybrid zero overhead anycast routing (ZOEF) for mobile ad hoc networks according to US Patent US11646962, IPC H04L45/00; H04W40/24; H04W84/18, which discloses a system and method for hybrid anycast (unicast, multicast and anycast) routing in a mobile ad hoc network (MANET). In embodiments, each MANET communication node may implement on-demand routing functions, whereby the node does not establish and maintain routes to destination nodes unless there is active communication, discovering routes by flooding data packets along the way. Each communication node may select proactive routing functions or transition from them to proactive routing functions. Proactive nodes first establish routes to clusters of other proactive nodes by flooding and receiving acknowledgments from other proactive nodes. Each cluster of proactive nodes maintains routes within the cluster and establishes communication routes outside the cluster by flooding and relaying routing state messages through cluster head nodes and gateway nodes. A single MANET can support clusters of proactive nodes in a network of on-demand nodes and dynamic transitions between proactive and on-demand status.

The prototype for the claimed invention is US patent US2013070637, IPC H04L12/28; H04L45/17, in which a network element is configured for non-stop routing (NSR) with open shortest path first (OSPF) with reliable flooding. An active OSPF instance decides to flood a link-state advertisement (LSA). The LSA is synchronized with the standby OSPF instance, including storing the LSA with a status indicating that flooding is expected. The active OSPF instance attempts to reliably flood the LSA to a set of neighboring network elements in the LSA flooding area. If LSA flooding is complete, the active OSPF instance forces the standby OSPF instance to change the LSA state to indicate that flooding is complete. If the standby OSPF instance becomes the currently active OSPF instance before LSA flooding is complete, the new active OSPF instance attempts to reliably flood the LSA.

The above solutions have a number of disadvantages, such as the presence of service traffic, limited speed of topology changes, required significant computing resources, limited number of subscribers, limited physical size of the network segment, time for redistribution of roles when changing the topology, and others.

This invention is aimed at eliminating the shortcomings of existing analogues and prototypes, as well as solving the set problems.

One of the tasks that must be solved is network management. The network assumes that each subscriber can transmit data to any other, wherever they are. When solving this problem by building a signal propagation route, it is necessary that each subscriber knows their neighbors, at a minimum, and, at a maximum, knows all subscribers and the network topology. This requires significant service traffic to determine the network topology and distribute its configuration to all nodes. And the faster the network topology changes, the more traffic is required. In addition, processing this information requires significant resources, which grow exponentially with the increase in the number of subscribers. All this leads to a limitation on the number of subscribers and the speed of topology change. Exceeding these restrictions leads to the network going out of working order.

Another task is to organize a data transmission channel. Since all nodes operate on a single channel, it is necessary to divide it between all subscribers in some way. In this case, subscribers are most likely out of line of sight of each other and it is necessary to organize traffic retransmission through other subscribers. To solve this problem, time division is usually used to access the channel. This requires additional service traffic to distribute time intervals. Additionally, network synchronization is required, which leads to a limitation on the physical size of the network due to the speed of light and the delays in information propagation introduced by this.

The proposed algorithm solves the problem of routing in MANET-type networks, does not require significant computing resources and allows organizing a multi-level network structure. At the same time, the distribution of unnecessary information is regulated.

To implement the algorithm, it is necessary to introduce two features: a network number feature and a channel number feature. All network subscribers behave in the same way and work according to the following algorithm:

1. If a subscriber has formed a packet for transmission, then he assigns it network and channel attributes in accordance with his settings;

2. When receiving a data packet over the air, the match between the network attribute and the channel attribute is checked;

3. If the network attribute does not match, the packet is excluded from further processing and deleted.

4. If it matches, then it is relayed;

5. If the channel number flag does not match, the packet is excluded from further processing;

6. If it matches, it is processed in accordance with the received data.

This algorithm of operation ensures data retransmission within the zone with the same network number attribute and does not allow this data to spread beyond this zone. If the channel number matches, the received data is additionally processed.

Thus, even in overlapping zones, traffic can be limited. Which leads to the release of radio airtime on one side and the delivery of necessary information in its zone.

Additionally, you can configure the reception of packets with several different network attributes. In this case, subscribers located in intersecting zones will retransmit and process packets from both zones.

Using the joint reception of packets with different network number attributes, it is possible to organize data transmission channels that will be distributed across all network segments, for example, notification channels. At the same time, local channels belonging to any zone will not be distributed in other zones and, accordingly, will not load the air.

In MANET type networks there is a problem of looping of transmitted information, as a result of which the network cyclically transmits the same data, which is no longer relevant, repeatedly. As a result, this leads to loss of network capacity, its overload and exit from the working state.

The proposed algorithm solves this problem. At the same time, it is possible to adjust the "depth" of protection against looping depending on the network structure and the information transmitted in it. The algorithm is easy to implement and does not require significant computing resources.

The algorithm consists of the following steps:

1. Receiving a packet from some information source, such as a transceiver;

2. Extraction from this packet of key information that clearly defines the uniqueness of this packet, for example, the source of information, cyclic number, hash sum;

3. This key information is searched for in the list of key information of previously received packets;

4. If the search does not yield results, then the key information of this package is added to the list and the package is transferred for further processing;

5. If the list contains a record of a package with the same key information, then this package is considered “duplicate” and is deleted and, accordingly, is not transferred for further processing;

6. The number of entries in this list can be used to regulate the "depth" of loop protection. This value depends on the capabilities of the computing device and the possible number of receptions of "duplicate" packets over a period of time.

7. In this case, the search in the list must begin with the last added entry, since the probability of receiving a “duplicate” package decreases over time and this will speed up the search and removal of such packages.

In MANET type networks, with a sufficiently large number of subscribers in the radio visibility zone, there is a huge redundancy, since all network nodes repeat received data packets. To eliminate this problem, the following algorithm can be used:

1. When receiving any data packet, after selecting the key information of this packet, it is searched for in the list of received packets;

2. If it is not in the list, it is added and the counter for the number of received duplicate packets is set to 1;

3. If such a packet is present in the list, the counter of received duplicate packets is increased by 1;

4. Before the start of transmission of this packet, the counter of the number of received duplicate packets and the counter of the number of transmitted copies of this packet are analyzed;

5. If the counter of the number of received duplicate packets and the counter of the number of transmitted copies of this packet does not exceed a certain specified number, then the packet is transmitted on the air. At the same time, the counter of transmission of this packet is increased;

6. If any of these counters exceeds a certain number, then this packet is removed from the transmission queue;

7. If the packet was generated by this device, it is placed in the transmission queue with the counters of the number of received and transmitted copies of this packet reset.

By adjusting the limits of these counters, it is possible to control the excess amount of data on the air, for example:

• If the number of received packets is set to 3, then if the number of devices in the environment that have transmitted copies of this packet is greater than or equal to 3, then when the turn comes for transmission by this device, the packet will not be transmitted. Since 3 copies of this packet have already been received.

• If the number of copies to transmit is set to 2, then if a packet is generated by this device, after the first copy is transmitted, the second copy of this packet will be sent.

• If both of these numbers are specified, then after the transmission of the first copy and before the transmission of the second copy, 3 duplicates of this packet will be received, then there will be no retransmission. If no duplicate packets are received, this means that the first copy of the packet was not received by anyone for some reason and a retransmission will occur.

Thus, with a large number of identical devices, there is no need for a large number of repetitions, which frees up airtime. On the other hand, if there are few devices or a packet has been lost, it is duplicated, which increases the probability of packet delivery.

Brief description of the drawings. The invention is explained by the following drawings, which show diagrams and algorithms for implementing the claimed method:

Fig. 1 - packet processing algorithm.

Fig. 2 - Operation of several independent network segments in one radio coverage area.

Fig. 3 - Operation of several independent network segments in one radio coverage area with partial logical overlap.

Fig. 4 - Algorithm for preventing looping.

Fig. 5 - Algorithm for counting duplicate data packets.

Fig. 6. - Algorithm for transmitting a data packet.

Fig. 7. - Structural diagram of a typical device having a wireless communication line.

Implementation of the invention. Figure 1 describes the algorithm for processing a packet. During the start of the algorithm 100, all tables and records are reset, as well as the working variables and pointers are configured, and the device operation configuration is loaded, i.e. the numbers of networks and channels with which the device operates. Block 110 waits for the receipt of a data packet from some source, for example, from a wireless communication line, a wired communication line, or an internal source. After receiving the packet, the network number attribute of the received packet is checked against the list of networks permitted for processing 120. If this network number of the packet is not on the list of networks permitted for processing, then this packet is permanently deleted 121. If the network number of the packet is on the list of networks permitted for processing, then a copy of this packet is made and it is transmitted to the relay block 130, in which the further distribution of this packet is determined. Next, the channel flag of the packet is checked against the list of channels permitted for further processing 140. If the channel flag of the packet is not in the list of those permitted for further processing, then the packet is deleted 141. If the channel flag of the packet is present in the list of packets permitted for reception, then it is transferred to the packet content processing and analysis block 150, where further processing of the packet occurs.

Figure 2 shows the operation of several independent network segments in one radio visibility zone. The figure shows the radio visibility zones of network segment #1–210, #2–220, #3–230. Subscribers located exclusively in their own radio visibility zones #1–211, 212, 213, #2–221, 223, #3–232. And subscribers in the intersecting zones #1 and #2–222, #1 and #3–214, #2 and #3–231, 224, 233. The connections organized in each radio visibility zone are also shown. Subscribers located in the joint radio visibility zones 222, 214, 231, 224, 233 work exclusively in their network segments.

Figure 3 shows the operation of several independent network segments in one radio visibility zone with partial logical overlap. The figure shows radio visibility zones of network segment #1–310, #2–320, #3–330. Subscribers located exclusively in their own radio visibility zones #1–311, 312, 313, #2–321, 323, #3–332. And subscribers in intersecting zones #1 and #2–322, #1 and #3–314, #2 and #3–331, 324, 333. The connections organized in each radio visibility zone are also shown. Subscribers located in joint radio visibility zones 322, 314 work jointly with network segments #1 and #2. At the same time, subscribers 331, 333, 324 work exclusively with their segments.

Figure 4 describes the algorithm for preventing loops. During the start of the algorithm 400, 410, all tables and records are reset, working variables and pointers are configured. Block 420 waits for a data packet to arrive from some source, such as a wireless link, a wired link, or an internal source. Next, the key information is extracted from the data packet 430. The key information of the received packet is searched for in the list of previously received packets 440. If such key information is found 450, then this data packet is permanently deleted 451. If such key information is not in the list of previously received packets, then it is added to this list 460. In this case, the oldest element in the list is cleared. After this, the data packet is transmitted for further processing 470.

Figure 5 shows the algorithm for counting duplicate data packets. During the start of the algorithm 500, all tables and records are reset, working variables and pointers are configured. Block 510 waits for a data packet to arrive from some source, such as a wireless link, a wired link, or an internal source. Next, the key information is extracted from the data packet 520. The key information of the received packet is searched for in the list of key information of previously received packets 530. If the key information is present in the list of key information of previously received packets, then the counter of such duplicate packets received is increased by 1,541. If such key information was not present, then this key information is added to the list of key information and the value of the counter of duplicate packets received is set to 1,550.

Figure 6 shows the algorithm for transmitting a data packet. During the start of the algorithm 600, all tables and records are reset, working variables and pointers are configured. Block 610 waits until it is time to transmit a data packet in any direction, for example, in a wireless communication line or a wired communication line. Then, the number of received duplicates of this packet is checked 620. If the number of received duplicates exceeds a certain predetermined value, then the packet is deleted 631. If the number of received duplicates does not exceed this value, then the number of sent duplicates of the packet is checked 630. If this number exceeds a predetermined value, then the packet is deleted 631. If this number does not exceed a specified value, then the packet is sent for transmission 640. If the transmission has taken place, then the number of sent duplicates of the packet is increased by 1,650.

Figure 7 describes the structural diagram of a typical device having a wireless communication line. The central processor 720 is engaged in processing incoming information, its analysis and distribution among modules. The interface unit 710 is intended, for example, for converting a speech signal from analog to digital and back or (and) receiving and sending data over a wired communication line. The receiving transmitter 730 is intended for receiving and sending data over the air. The indicating and controlling organs 740 are necessary for indicating the operating modes and controlling them.

The operation of the typical device shown in Fig. 7 begins after it is activated by some means, such as power supply. After the initial loading of the processor 720, the necessary blocks 710, 730, 740 are configured according to their tasks. Then variables, pointers, etc. are prepared. Network parameters and necessary devices are loaded. After this, the device is ready for operation.

As examples, we will give specific forms of implementation of the claimed invention:

Let's give an example of the device transmitting, for example, a voice packet. From the controls 740 comes a command to transmit audio information (the PTT key is pressed). The processor 720, having received the command to begin transmitting audio data, issues a command to the interface unit 710 to begin converting the audio into digital form. Unit 710, as the audio is encoded into digital form, periodically sends it to the processor 720. The processor, having collected the required amount of encoded audio, forms a data packet, which contains:

- Your unique identifier;

- Package serial number;

- Network number;

- Channel number;

- Identifier of the transmitted data;

- Data.

After the packet is formed, it is transferred to the transmission queue with the required values of the number of transmission repetitions and the number of duplicate packets received. As new encoded audio data arrives, new packets are formed, which are also sent to the transmission queue.

Next, block 610, in accordance with its algorithm for selecting the transmission time, looks through the queue for transmission. If there is a packet there, then, in accordance with the algorithm of Fig. 6, in block 640 the packet is transmitted to the wireless receiving transmitter 730.

When the control unit 740 sends a command to stop transmitting audio information to the processor 720, it will issue a command to the interface unit 710 to stop converting audio into digital form. At the same time, the processor 720, having received the remaining data, also forms a packet and sends it to the queue for transmission.

After all packets from the queue have been transmitted according to Figure 6, the queue will be cleared.

Let us give an example of receiving a device, for example, a sound packet. From the transmitter 730, a data packet is received by the processor 720. In the processor, after receiving the data packet 420 according to Figure 4, the key information about the packet is extracted, namely:

- Unique identifier of the processor that generated the packet;

- Package serial number;

- Identifier of the transmitted data.

According to this information, a search is performed in the list of received packets 450. If such a packet has already been, then block 541 increases the counter of received duplicate packets. Then block 451 deletes the packet. If such a packet has not yet been, then block 550 adds key information about the packet to the list of received packets. Then block 470 begins processing the information in the packet according to figure 1. If the network attribute does not match the attributes of the permitted networks 120, then the data packet is deleted. If it does match, then its copy is sent to the transmission queue, which is processed according to figure 6. Then the attribute of the channel number of the received packet is checked against the list of channels permitted for processing. If such a channel is not on the list, then the packet is deleted. After this, block 150 analyzes the contents of the packet.

In our case, the packet contains coded speech information. Processor 720 transmits the received data to block 710 for playback. After the data from the transmitter 730 stops arriving, the sound playback will also stop. Processor 720, when receiving simultaneous sound information from different devices, can, by analyzing the channel number indicator, leave playback only from this channel or switch to playback of a higher priority channel. Or, if the interface block 710 allows it, play several channels in parallel.

Let us give an example of information distribution within one network segment. Let us consider segment 210 and information distribution in it. Let us assume that device 211 has started transmitting digitized audio. Having formed a packet with the attributes of its unique number, packet sequence number, network attribute 1, the packet is sent to the transmission queue, after which it is transmitted over the air. This packet is received by devices 212 and 213. Since such a packet has not yet existed and the network attribute number matches the list of networks received by these stations, each station will place a copy of this packet in its transmission queue. According to its transmission algorithm, each station will broadcast this packet in due time. Let us assume that device 212 will be the first to broadcast this packet. Stations 211 and 213 will receive this data packet. Since such a packet has already been received by device 213 or sent by device 211, then, according to the algorithm, it will be deleted. Later, in due course, this packet will be transmitted by device 213. It will be received by stations 211, 212 and 214. Devices 211 and 212 will remove this packet from processing since it has already been processed. Device 214, having received this packet and determined that it is new, will place it in the transmission queue. After the packet has been transmitted by device 214, it will be received by device 213. Since the packet has already been, it will also be removed.

Thus, the information will be distributed throughout the entire network segment regardless of its size. At the same time, after delivery to all devices, it will be removed from further broadcasting. Also, device 222, although it is in the signal reception zone of segment 210, will not process and transmit this packet, since it is configured to work in segment 220 with network indicator number 2.

Let us give an example of information distribution within one network segment on different channels. Let us consider segment 210. In this case, devices 211 and 214 are configured to receive and transmit on channel number 1, and devices 212 and 213 on channel number 2. Let us assume that device 211 has started transmitting encoded audio information. Then the transmitted packets will have the channel number indicator 1. According to the information distribution within one network segment, this packet will be distributed to all devices. Device 214 will reproduce this information because it is configured to receive channel 1, and devices 212 and 213 will not, because they are configured to receive channel 2. Thus, within one segment, it is possible to distribute information intended for devices with different channel settings, but with the same network indicator. In this case, if the wireless channel bandwidth allows, it is possible to receive and transmit several channels simultaneously.

Let us give an example of information distribution in several independent network segments in one radio visibility zone with partial logical overlap. Let us consider segments 310, 320 and 330 in Figure 3. Devices 311, 312, 313, 314 belong to segment 310, devices 321, 322, 323, 324 belong to segment 320, devices 331, 332, 333 belong to segment 330. In segments 310, 320 and 330, they are configured respectively for network features 1, 2 and 3, respectively. In this case, the device 314 is additionally configured with the network flag 2, and the device 322 is additionally configured with the network flag 1. In this form, the information distributed over the segment 310 on the first channel will be additionally distributed by the device 322. And accordingly, the information distributed over the segment 320 on the second channel will be additionally distributed by the device 314. In this case, the radio visibility zone of the segment 310 and 320 increases accordingly. Also, with the corresponding settings of the channel number flags in the devices 314 and 322, the device can operate both in the segment 310 and in the segment 320. The segment 330 will remain isolated from the data transmitted in the segments 310 and 320. This in turn leads to the release of unnecessary data from the air and accordingly increases the throughput of the segment 330.

Let us give an example of regulating redundancy in a network. Let us consider segment 210 and the distribution of information in it with various settings for the duplicate packet reception counters and the number of packet retransmissions. Devices 211, 212, 213 and 214 belong to segment 210 and are configured for one network flag 1. Devices 211 and 214 are configured to send 2 identical packets if they have not received 2 duplicated packets of the same type. Devices 212 and 213 are configured to send one packet regardless of the number of duplicate packets received. When device 211 initiates the transmission of a packet, devices 212 and 213 will receive it. They, in turn, will repeat these packets. And if device 211 manages to receive this packet from devices 212 and 213, it will not resend its packet. In this case, device 214 will receive only one packet from device 213 and in this case will resend this packet. When device 214 initiates transmission of a packet, only device 213 will receive it. Accordingly, device 214 will receive only one duplicate packet from device 213 and will send a second identical packet at the time of transmission. Device 211 may have time to receive identical packets from devices 212 and 213 before its transmission time. In this case, device 211 will not send a copy of the packet at all. Thus, in a network segment with a high density of devices, it is possible to reduce airtime occupancy by reducing the number of repeated transmissions of identical packets. At the same time, in a network segment with a low density of devices, it is possible to configure repeated transmission of a data packet to increase the probability of data delivery for all devices in the network segment.

Let us give an example of regulating the priority of the probability of data transmission in the network. The probability of data delivery can be regulated. Let us consider figure 6. In block 640, several attempts are used to transmit a packet, which can be successful or unsuccessful. In case of failure of transmission, the number of attempts to transmit the packet decreases. When this number reaches zero, the packet is removed from the transmission queue. Thus, the device is freed from the packet that could not be transmitted and is ready to transmit the next one. By increasing the number of attempts to transmit a packet, the probability of the device issuing a packet increases, which accordingly leads to an increase in the probability of delivering the packet to all devices on the network.

Let's give an example of regulating the priority of data delivery time in the network. In a simple case, packets are transmitted strictly in the sequence of their arrival in the transmission queue. If in block 130 a copy of a packet is placed at the beginning of the transmission queue depending on some features, then this packet will be transmitted first. Thus, packets with features of increased priority will be distributed across the network faster than other packets.

The examples provided represent one of the embodiments of the present invention and cannot narrow the claimed scope of legal protection.

Claims (17)

A method for organizing wireless peer-to-peer self-organizing networks that includes the transmission of data packets containing the following steps: 1) receiving a data packet containing a network attribute, a channel attribute and key information; 2) extracting key information from the packet and searching for this information in the list of key information of previously received packets, while: - if the information is not found, it is added to the list of key information of this package and the package is transferred for further processing; - if the list contains a record of a package with the same key information, then this package is considered duplicated and is deleted, and accordingly is not transferred for further processing; - if a data packet is not in the list of received packets, it is added and the counter for the number of received duplicate data packets is set to 1; - if the data packet is present in the list of received packets, the counter of received duplicate data packets is increased by 1; - before the start of the transmission of a data packet, the counter of the number of received duplicate packets and the counter of the number of transmitted copies of this packet are analyzed, while: - if the counter of the number of received duplicate data packets and the counter of the number of transmitted copies of this packet does not exceed a certain specified number, then the data packet is transmitted over the air, and the counter of data packet transmission is increased; - if any of these counters exceeds a certain number, then this data packet is removed from the transmission queue; 3) when receiving a data packet over the air, the match of the network attribute is checked, and: - if the network attribute matches, the packet is transmitted for retransmission; - if the network attribute does not match, the packet is permanently deleted; 4) checking the match of the channel attribute, while: - if the channel attribute matches, the packet is processed in accordance with the received data; - if the channel attribute does not match, the packet is excluded from further processing; characterized in that the search for key information in the list must begin with the last added entry; if a data packet was generated by a device, it is placed in a transmission queue with zeroed counters for the number of copies of such a data packet received and transmitted.