CN116056146A

Movatterモバイル変換

Info

Publication number: CN116056146A
Application number: CN202310203259.5A
Authority: CN
Inventors: 董雁适; 千应庆; 张婧; 樊玉书; 陈遵义
Original assignee: Zhikong Huzhou Intelligent System Co ltd; Zhikong Technology Huzhou Innovation Research Institute Co ltd
Current assignee: Zhikong Huzhou Intelligent System Co ltd; Zhikong Technology Huzhou Innovation Research Institute Co ltd
Priority date: 2023-03-06
Filing date: 2023-03-06
Publication date: 2023-05-02
Anticipated expiration: 2043-03-06
Also published as: CN116056146B

Abstract

The invention relates to the technical field of cache transmission, and provides a wireless positioning signal cache transmission method based on a hash array, which comprises the following steps: data acquisition interrupt thread: the reader-writer receives the tag signal and stores tag data at the tail of the interrupt data queue; data caching thread: sequentially reading the tag data in the interrupt data queue, storing the tag data in an idle position in the hash array when the tag does not store data in the hash array, otherwise updating the tag data in the same position in the hash array; data transmission thread: after the reader-writer receives the data transmission command of the positioning server, the tag data stored in the hash array are copied into the data transmission buffer area in sequence, data transmission is started, and the tag data in the data transmission buffer area are transmitted to the positioning server. When the reader-writer caches the tag signals based on the hash array, only the latest wireless signal of each tag is reserved, and memory occupation and bandwidth are reduced under the condition that the reader-writer resources are limited.

Description

Wireless positioning signal buffer memory transmission method and system based on hash array

Technical Field

The invention relates to the technical field of cache transmission, in particular to a wireless positioning signal cache transmission method and system based on a hash array.

Background

By using wireless communication technologies such as active RFID, bluetooth, wiFi, loRa, mobile phone base stations and the like, objects such as students, hospital instruments, maintenance equipment, trays, forklifts and the like can be positioned wirelessly. The most basic wireless positioning system comprises three devices, namely a tag, a reader and a positioning server. The tag can be worn or fixed on an object to be positioned, the reader-writer is arranged at all places in a scattered manner, and a communication link between the reader-writer and the positioning server is established.

The most currently used wireless location systems are based on wireless signal strength for location. The principle is as follows: the tag is provided with a wireless transceiver which can periodically transmit wireless positioning signals, and after the signals are received by surrounding readers, the signals are forwarded to a positioning server through a communication link, and receiving information such as wireless signal receiving intensity (RSSI), time difference of arrival (TODA, namely air transmission time) and angle of arrival (AOA) of the signals is added; the positioning server gathers all wireless signals read by a plurality of readers and writers of a tag in a time window, and then presumes the position of the tag according to positioning algorithms such as triangle distance positioning, RSSI fingerprint and the like. The RSSI value given by the wireless transceiver is converted into an 8-bit positive integer, and has approximate linear relation with the distance between the tag and the reader, and the triangle distance positioning based on the RSSI depends on the principle.

However, in the wireless positioning application scenarios such as student positioning in campus, asset positioning in hospital, tray in warehouse, forklift positioning, etc., the hardware cost of the reader-writer needs to be as low as possible, so that the low-cost communication interfaces such as MCU singlechip and 485 are generally adopted, and the calculation speed (or main frequency), the memory (i.e. SRAM) and the communication bandwidth are quite limited. However, in these scenarios, the reader/writer will often read 1000 tag signals on average, translating to a bandwidth of at least 32Kbps, within one second. The communication distance between the reader and the positioning server is generally tens of meters, the baud rate is less than 20Kbps, all tag signals cannot be transmitted, and buffering and data compression are required. However, if the buffering time is too long, excessive memory is required to be occupied, and the real-time positioning performance is also reduced. If the compression algorithm is too complex, it may result in insufficient computation or insufficient memory, and the tag signal may have to be discarded, resulting in increased or even missing positioning errors.

Disclosure of Invention

Aiming at the problems, the invention aims to provide a wireless positioning signal buffer transmission method and a wireless positioning signal buffer transmission system based on a hash array, which only reserve the latest wireless signal of each tag when a reader-writer buffers tag signals based on the hash array, and reduce memory occupation and bandwidth under the condition of limited reader-writer resources.

The above object of the present invention is achieved by the following technical solutions:

a wireless positioning signal buffer memory transmission method based on a hash array comprises the following concurrent execution threads:

data acquisition interrupt thread: the reader-writer receives a tag signal sent by a tag, and stores tag data corresponding to the tag signal at the tail of an interrupt data queue;

data caching thread: sequentially reading the tag data in the interrupt data queue, storing the tag data to an idle position in the hash array when the tag corresponding to the tag data does not store data in the hash array, otherwise, updating the tag data to the same position in the hash array;

data transmission thread: and after the reader-writer receives a data transmission command of the positioning server, copying the tag data stored in the hash array into a data transmission buffer area in sequence, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server.

Further, in the data acquisition interrupt thread, the reader-writer receives the tag signal sent by the tag, and stores the tag data corresponding to the tag signal to the tail of the interrupt data queue, specifically:

s11: after the wireless transceiver on the reader receives the new tag signal sent by the tag, notifying the microcontroller MCU on the reader through interruption;

s12: and the microcontroller MCU responds to the interrupt, reads the tag data from the wireless transceiver and stores the tag data at the tail of the interrupt data queue.

Further, before executing the data cache thread, the method further includes: the hash array is established specifically as follows:

obtaining the maximum record number of the label data to be cached, taking the minimum prime number which is larger than or equal to the maximum record number as the size of the hash array, and recording the size of the hash array as S;

in the initialization stage of the reader, marking all records in the hash array as idle;

the initial value of the transmission starting position T of the hash array is defined to be 0, and the initial value of the mutex variable M of the hash array is defined to be 0.

Further, in the data caching thread, sequentially reading the tag data in the interrupt data queue, when the tag corresponding to the tag data does not store data in the hash array, storing the tag data in an idle position in the hash array, otherwise, updating the tag data to the same position in the hash array, specifically:

s21: acquiring a piece of tag data from the head of the interrupt data queue, marking a tag number corresponding to the tag data as I, wherein I is a positive integer, and ending the data cache thread when the tag data in the interrupt data queue is completely fetched;

s22: calculating the position L of the tag number in the hash array, wherein L=I% S, wherein% is the remainder calculation, S is the size of the hash array, and a local variable c=0 is defined;

s23: when the position L is idle, storing the label mark I and the additional data into the position L, skipping to the step S21, and when the position L is not idle, skipping to the step S24;

s24: checking whether the tag number stored in the location L is I, if so, updating the additional data to the location I, and jumping to step S21, otherwise, c=c+1, l= (i+c)% S, and jumping to step S23.

Further, in the data cache thread, the hash array is prevented from being accessed by two threads simultaneously by the mutex variable M, specifically:

checking the value of the mutex M before executing step S23;

when m=1, waiting continuously for M to become 0;

when m=0, m=1 is set and step S23 is performed until the tag label I and additional data are saved to the location L or when the tag number stored in the location L has updated the additional data to the location I for I, m=0.

Further, in the data transmission thread, copying the tag data stored in the hash array into the data transmission buffer area in sequence, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server, specifically:

s31: setting t=t after the reader-writer receives the data transmission command of the positioning server;

s32, checking whether the tag data is stored in a position t in the hash array, if so, copying the tag data in the position t to the data transmission buffer area, and setting the position t to be free;

s33: t=t+1, if t > S, t=0 is set;

s34: when the data transmission buffer area has a residual space, and T is not equal to T, adjusting to step S32, otherwise jumping to step S35;

s35: and starting data transmission, transmitting the tag data in the data transmission buffer area to the positioning server, and ending the data transmission thread.

Further, in the data transmission thread, the hash array is prevented from being accessed by two threads simultaneously by the mutex variable M, specifically:

checking the value of the mutex M before executing step S32;

when m=1, waiting continuously for M to become 0;

when m=0, m=1 is set and step S32 is performed, and after step S32 is performed, m=0 is set.

A hash array-based wireless location signal buffer transmission system for performing the hash array-based wireless location signal buffer transmission method as described above, comprising:

the data acquisition module is used for executing a data acquisition interrupt thread, and when the reader-writer receives a tag signal sent by a tag, the tag data corresponding to the tag signal is stored at the tail of an interrupt data queue;

the data caching module is used for executing a data caching thread, sequentially reading the tag data in the interrupt data queue, storing the tag data to an idle position in the hash array when the tag corresponding to the tag data does not store data in the hash array, and otherwise, updating the tag data to the same position in the hash array;

and the data transmission module is used for executing a data transmission thread, copying the tag data stored in the hash array into a data transmission buffer area in sequence after the reader-writer receives a data transmission command of the positioning server, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server.

A computer device comprising a memory and one or more processors, the memory having stored therein computer code which, when executed by the one or more processors, causes the one or more processors to perform a method as described above.

A computer readable storage medium storing computer code which, when executed, performs a method as described above.

Compared with the prior art, the invention has the following beneficial effects:

(1) The wireless positioning signal buffer transmission method based on the hash array comprises the following threads of concurrent execution: data acquisition interrupt thread: the reader-writer receives a tag signal sent by a tag, and stores tag data corresponding to the tag signal at the tail of an interrupt data queue; data caching thread: sequentially reading the tag data in the interrupt data queue, storing the tag data to an idle position in the hash array when the tag corresponding to the tag data does not store data in the hash array, otherwise, updating the tag data to the same position in the hash array; data transmission thread: and after the reader-writer receives a data transmission command of the positioning server, copying the tag data stored in the hash array into a data transmission buffer area in sequence, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server. According to the technical scheme, when the reader-writer caches the tag signals based on the hash array, only the latest wireless signal of each tag is reserved. When a reader reads a tag signal, the reader needs to search whether the tag has a record in the hash array, if so, the old record needs to be deleted to store a new record, or the new record is directly covered with the new record to update the old record, so that the memory occupation and the bandwidth are reduced under the condition that the reader resource is limited.

(2) By caching the data with a hash array, the hash array has a lookup, insertion or update complexity of time complexity O (1).

Drawings

FIG. 1 is a schematic diagram of a hash array of the present invention;

FIG. 2 is a schematic diagram of a hash array linear probe of the present invention;

FIG. 3 is a schematic diagram of a wireless positioning signal buffer transmission method based on a hash array according to the present invention;

fig. 4 is a schematic diagram of a wireless positioning signal buffer transmission system based on a hash array according to the present invention.

Detailed Description

For the purposes of making the objects, technical solutions and advantages of the embodiments of the present application more clear, the technical solutions of the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application, and it is apparent that the described embodiments are some embodiments of the present application, but not all embodiments. All other embodiments, which can be made by one of ordinary skill in the art without undue burden from the present disclosure, are within the scope of the present disclosure.

As used herein, the singular forms "a", "an", "the" and "the" are intended to include the plural forms as well, unless expressly stated otherwise, as understood by those skilled in the art. It will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

The invention relates to a principle brief description of hash array:

as shown in fig. 1, the bottom layer of the Hash table is actually stored based on an array, when a key-value pair is inserted, the key-value pair is not directly inserted into the array, but the key (such as a 32-bit tag number) is subjected to Hash operation to obtain a Hash value, and then the Hash value is modulo the array capacity to obtain a position in the array and then inserted. If the specified key value matches the stored key, the key value pair is returned, and if not, it is indicated that there is no corresponding key value pair in the hash table. The advantage of this is that the time complexity O (1), in the worst case O (n), can be achieved in seek, insert, delete etc. operations, which are of course the most extreme cases, rarely encountered.

The process of storing the hash table can be divided into two major steps:

(1) Implementing a Hash function

The Hash function is very important, and a good Hash function is excellent in performance, and can enable values stored in the bottom array to be distributed more uniformly, so that collision is reduced. The collision is reduced because the process of taking the Hash actually maps the input keys (fields) into a very small space, so that the collision is unavoidable and what can be done is to reduce the probability of the Hash collision occurring. In particular implementations, the hash function algorithm may vary.

(2) Reasonable Hash conflict resolution

In addition to the Hash function itself, the underlying array capacity is also an important cause of impact to the occurrence of Hash collisions (collisions). It is clear that in extreme cases if the array capacity is 1, then a collision must occur, and if the array capacity is infinite, then the probability of collision is very low. Therefore, hash collisions also depend on the load factor. The load factor is the ratio of the number of stored key-value pairs to the array capacity, such as array capacity 100, where 90 key-value pairs are currently stored, and the load factor is 0.9. If the value of the load factor is too large, it is stated that the stored key value is close to the capacity, increasing the risk of collision, and if the value is too small, space is wasted.

Therefore, since collisions cannot be avoided, a mechanism for resolving Hash collisions is necessary. The following describes a method of handling conflicts: open addressing. The open addressing method solves the conflict by directly searching for the next empty address, and the empty address can be always found as long as the table at the bottom is large enough. This act of finding the next address is called probing.

Wherein, hash (key) is a hash function, m is a hash table length, d_i For delta sequences, i is the number of times a collision has occurred. There are various detection methods according to the difference of the incremental sequence extraction method, as shown in fig. 2, the simplest is linear detection. di=1, 2,3, (m-1), i.e. d_i =i, or other linear function. The table of stored addresses is probed one by one until a null cell is found, and the hash address is stored in the null cell.

First embodiment

As shown in fig. 3, the present embodiment provides a wireless positioning signal buffer transmission method based on a hash array, which is an invention based on data processing of a reader-writer. The reader-writer comprises three threads of data acquisition interrupt threads, data cache threads and data transmission threads which are executed concurrently. And meanwhile, data acquisition, caching and transmission are carried out, so that the data processing speed is increased. The process flow of each thread is described in detail below:

(1) Data acquisition interrupt thread:

the reader-writer receives a tag signal sent by a tag, stores tag data corresponding to the tag signal at the tail of an interrupt data queue, and specifically comprises the following steps:

s11: and after the wireless transceiver on the reader receives the new tag signal sent by the tag, notifying the microcontroller MCU on the reader through interruption. Wherein the wireless transceiver is typically a chip, or a module in a SOC (System on Chip) chip. The MCU is a microcontroller or a single chip microcomputer. The wireless transceiver is generally used in the tag and the reader, and the wireless transceiver mentioned in this step is a wireless transceiver on the reader.

S12: and the microcontroller MCU responds to the interrupt, reads the tag data from the wireless transceiver and stores the tag data at the tail of the interrupt data queue, and the data acquisition interrupt thread is finished. The length of the interrupt data queue is generally determined according to the real-time requirement of the reader-writer.

(2) Data caching threads

And sequentially reading the tag data in the interrupt data queue, storing the tag data to an idle position in the hash array when the tag corresponding to the tag data does not store data in the hash array, otherwise, updating the tag data to the same position in the hash array.

In the thread, hash data is adopted to buffer data, a hash array needs to be established before the data buffer thread is started, and the hash array established by the invention is explained below;

in order to reduce memory occupation and bandwidth, in the invention, when the reader-writer caches tag data, only the latest wireless signal of each tag is reserved. In other words, each time the reader/writer reads a tag signal, it is necessary to find whether the tag has a record in the memory, and if so, it is necessary to delete the old record, save the new record, or directly update and overwrite the old record with the new record. To quickly complete such a lookup-update operation and minimize the memory footprint of each record, the present invention uses a hash array with a lookup, insertion, or update complexity of time complexity O (1).

A hash array is a common array, and is composed of a series of elements, each element is a data structure, and is stored continuously in a memory area. Such as 5 bytes per element, the first 4 bytes representing the tag number, the last byte being the radio signal strength. In contrast, if the tag record is saved with the data structure of the unordered array, when tens of thousands of tags are already saved in the memory, the time taken for each search traversal is very long; if an ordered array is used, then a large number of records need to be copied in memory when a new tag needs to be inserted; the use of linked list, b+ tree, etc. data structures would result in a significant additional memory requirement and are not suitable.

And obtaining the maximum record number r of the label data to be cached, taking the minimum prime number which is larger than or equal to the maximum record number r as the size of the hash array for establishing the hash array, and recording the size of the hash array as S.

During the initialization phase of the reader, all records in the hash array are marked as idle (if tag number 0 is not used, the tag number field may be set to 0 to indicate idle); the initial value of the transmission starting position T of the hash array is defined to be 0, and the initial value of the mutex variable M of the hash array is defined to be 0. The mutex variable is used in the case of multithreading to avoid 2 threads accessing the same resource. For example, 1 thread corresponds to 1 person, 1 room corresponds to 1 resource, and the mutex corresponds to the lock operation of the lock of the room door. After any person enters the room, the door is back-locked (the mutual exclusion variable is 1), and before the door comes out, the door is opened (the mutual exclusion variable is 0). Thus, the situation that 2 persons enter the room at the same time does not occur. In this embodiment, the same resource refers to a hash array.

After the hash array setup is completed, the data cache thread may be executed. The method specifically comprises the following steps:

s21: and acquiring a piece of tag data from the head of the interrupt data queue, marking a tag number corresponding to the tag data as I, wherein I is a positive integer, and ending the data cache thread when the tag data in the interrupt data queue is completely fetched.

S22: and calculating the position L of the label number in the hash array, wherein L=I% S, wherein% is the remainder calculation, S is the size of the hash array, and a local variable c=0 is defined. Because a remainder of dividing a random number I by a prime number is a value between 0 and S-1 and is randomly distributed. The core principle of the hash array is to make the hash value (here, the remainder value) random as much as possible, so as to reduce the collision probability.

S23: and when the position L is idle, storing the tag label I and the additional data into the position L, skipping to the step S21, and when the position L is not idle, skipping to the step S24.

S24: checking whether the tag number stored in the location L is I, if so, updating the additional data to the location I, jumping to step S21, otherwise, c=c+1, l= (i+c)% S, jumping to step S23 (if a location already has data (collision is found), trying to find whether a location already has data, if so, continuing to add one).

Further, in the data cache thread, the hash array is prevented from being accessed by two threads simultaneously by the mutex variable M, specifically: checking the value of the mutex M before executing step S23; when m=1, waiting continuously for M to become 0; when m=0, m=1 is set and step S23 is performed until the tag label I and additional data are saved to the location L or when the tag number stored in the location L has updated the additional data to the location I for I, m=0.

(3) Data transfer thread

After the reader-writer receives a data transmission command of the positioning server, copying the tag data stored in the hash array into a data transmission buffer area in sequence, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server, wherein the method specifically comprises the following steps of:

s31: and setting t=T after the reader-writer receives the data transmission command of the positioning server.

S32, checking whether the tag data is stored in a position t in the hash array, if so, copying the tag data in the position t to the data transmission buffer area, and setting the position t to be free; wherein t refers to a position in the hash array, and the transmission buffer is another memory for storing data to be transmitted.

S33: t=t+1, and if t > S, t=0 is set.

S34: when the data transmission buffer area has a residual space, and T is not equal to T, the process goes to step S32, otherwise, the process goes to step S35. When the data transmission buffer area has a residual space, and the meaning that T is not equal to T is that the data transmission buffer area has the residual space, and one round of traversal of the hash array is not completed.

checking the value of the mutex M before executing step S32; when m=1, waiting continuously for M to become 0; when m=0, m=1 is set and step S32 is performed, and after step S32 is performed, m=0 is set.

Second embodiment

As shown in fig. 4, the present embodiment provides a hash array-based wireless positioning signal buffer transmission system for performing the hash array-based wireless positioning signal buffer transmission method as in the first embodiment, including:

the data acquisition module 1 is used for executing a data acquisition interrupt thread, and when the reader-writer receives a tag signal sent by a tag, the tag data corresponding to the tag signal is stored at the tail of an interrupt data queue;

the data caching module 2 is used for executing a data caching thread, sequentially reading the tag data in the interrupt data queue, storing the tag data to an idle position in the hash array when the tag corresponding to the tag data does not store data in the hash array, and otherwise, updating the tag data to the same position in the hash array;

and the data transmission module 3 is used for executing a data transmission thread, copying the tag data stored in the hash array into a data transmission buffer area in sequence after the reader-writer receives a data transmission command of the positioning server, starting data transmission, and transmitting the tag data in the data transmission buffer area to the positioning server.

A computer readable storage medium storing computer code which, when executed, performs a method as described above. Those of ordinary skill in the art will appreciate that all or part of the steps in the various methods of the above embodiments may be implemented by a program to instruct related hardware, the program may be stored in a computer readable storage medium, and the storage medium may include: read Only Memory (ROM), random access Memory (RAM, random Access Memory), magnetic or optical disk, and the like.

The above description is only a preferred embodiment of the present invention, and the protection scope of the present invention is not limited to the above examples, and all technical solutions belonging to the concept of the present invention belong to the protection scope of the present invention. It should be noted that modifications and adaptations to the present invention may occur to one skilled in the art without departing from the principles of the present invention and are intended to be within the scope of the present invention.

The technical features of the above-described embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above-described embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.

It should be noted that the above embodiments can be freely combined as needed. The foregoing is merely a preferred embodiment of the present invention and it should be noted that modifications and adaptations to those skilled in the art may be made without departing from the principles of the present invention, which are intended to be comprehended within the scope of the present invention.

Claims

1. A wireless positioning signal buffer memory transmission method based on a hash array is characterized by comprising the following threads of concurrent execution:

2. The hash array-based wireless positioning signal buffer transmission method according to claim 1, wherein in the data acquisition interrupt thread, the reader receives the tag signal sent by the tag, and stores the tag data corresponding to the tag signal at the tail of the interrupt data queue, specifically:

3. The hash array-based wireless location signal cache transmission method of claim 1, further comprising, prior to executing the data cache thread: the hash array is established specifically as follows:

4. The wireless positioning signal buffer transmission method based on a hash array according to claim 3, wherein in the data buffer thread, the tag data in the interrupt data queue is sequentially read, when the tag corresponding to the tag data does not store data in the hash array, the tag data is stored in an idle position in the hash array, otherwise, the tag data is updated to the same position in the hash array, specifically:

5. The wireless positioning signal buffer transmission method based on a hash array according to claim 4, wherein in the data buffer thread, the hash array is prevented from being accessed by two threads simultaneously by the mutex variable M, specifically:

checking the value of the mutex M before executing step S23;

when m=1, waiting continuously for M to become 0;

6. The wireless positioning signal buffer transmission method based on a hash array according to claim 3, wherein in the data transmission thread, the tag data stored in the hash array is copied into the data transmission buffer in sequence, and data transmission is started, and the tag data in the data transmission buffer is transmitted to the positioning server, specifically:

s33: t=t+1, if t > S, t=0 is set;

7. The wireless positioning signal buffer transmission method based on a hash array according to claim 6, wherein in the data transmission thread, the hash array is prevented from being accessed by two threads simultaneously by the mutex variable M, specifically:

checking the value of the mutex M before executing step S32;

when m=1, waiting continuously for M to become 0;

8. A hash array based wireless location signal buffer transmission system for performing the hash array based wireless location signal buffer transmission method of claims 1-7, comprising:

9. A computer device comprising a memory and one or more processors, the memory having stored therein computer code that, when executed by the one or more processors, causes the one or more processors to perform the method of any of claims 1-7.

10. A computer readable storage medium storing computer code which, when executed, performs the method of any one of claims 1 to 7.