Radio station location estimating apparatus and method

The present invention relates to a radio station position estimation device and method for estimating the position of a radio station existing outside the area of its own station.

Recent advances in wireless communications and personal computing have prompted the study of ad hoc wireless networks envisioned as fast-deployable, infrastructure-free networks in which each node radio station functions as a mobile router with a wireless transceiver. Generally, in an ad hoc radio network, all node radio stations are equipped with omnidirectional antennas. However, ad hoc wireless networks that use omnidirectional antennas use RTS / CTS-based floor allocation methods that waste most of their network capacity on securing wireless media over large areas. As a result, many node radio stations in the vicinity of transmitters and receivers are forced to remain idle waiting for the end of data communication between transmitters and receivers.

To alleviate this problem, researchers have proposed the use of directional antennas that direct transmit and receive beams only to receive and transmit node radio stations (eg, Patent Documents 1 and 2, Non-Patent Document 1). And 2). This greatly reduces radio interference, which improves the use of wireless media, all network throughput. In addition, the use of directional antennas saves power because it allows directional access to nearby node radio stations with less power than omnidirectional antennas.

For example, in Non-Patent Document 1, the position estimation protocol (hereinafter referred to as a conventional example) needs to have the ability of position calculation based on multi-hop, and the directional antenna system and DOA (hereinafter referred to as DOA). Direction Of Arrival We are proposing a position detection protocol that uses an estimation algorithm. Further, in Non-Patent Document 1, the position detection protocol using a plurality of directional antenna systems is even more accurate than a similar protocol using an omnidirectional antenna, which particularly uses a distance-based trigonometry technique. We have confirmed that we can obtain good results. Here, we propose a switchable beam antenna system having a plurality of reference node radio stations and a switching beam or omnidirectional antenna system having a mobile node radio station.

<patcit num="1"><text>Japanese Unexamined Patent Publication No. 2001-024431.</text></patcit><patcit num="2"><text>Japanese Unexamined Patent Publication No. 2001-244983.</text></patcit><nplcit num="1"><text>T. Ohira et al., "Electronically Steerable Passive Array Radiator (ESPAR) Antennas for Low-cost Adaptive Beamforming", IEEE International Conference on Phased Array Systems, Dana Point, California, USA, May 2000.</text></nplcit><nplcit num="2"><text>K. Gyoda et al., "Beam and Null Steering Capability of ESPAR Antennas", Proceedings of the IEEE AP-S International Symposium, July 2000.</text></nplcit><nplcit num="3"><text>Jeongkeum Lee et al., "Location sensing protocol utilizing directional antenna systems in millimeter-wave broadband ad hoc networks", Technical Report of Seoul National University, Korea, SNU-CSE-MMLAB-LSDA, Version 1, September 2003.</text></nplcit>

<p> However, in the position estimation protocol according to the conventional example, the effectiveness is not actually confirmed by using the directional antenna, and the position estimation method of the radio station outside the area in multi-hop is not described at all. There was a problem.</p><p> An object of the present invention is to solve the above problems, and in the position estimation of a radio station outside the area in multi-hop, the position estimation of the radio station can be performed with higher accuracy and more reliably than in the conventional example. Moreover, it is an object of the present invention to provide the radio station position estimation apparatus and method which are simple in structure.</p>

<p> The radio station position estimation device according to the first invention is a radio station position estimation device that includes a plurality of radio stations and estimates the positions of radio stations at a plurality of hop positions in a radio network that performs wireless communication between the radio stations. In, each of the above radio stations sweeps while switching the radiation beam pattern over all directions at a predetermined angle, and transmits a predetermined radio beacon signal including the position information of the transmission source radio station and the radiation beam pattern information thereof. Then, the radio station that has received the radio beacon signal measures the signal strength of the radio beacon signal for each of the radiation beam patterns, and creates a first table including the signal strength of each measured radiation beam pattern. And stores it in the storage device, searches for information on the radiation beam pattern having the maximum signal strength based on the first table, creates a second table, stores it in the storage device, and stores it in the storage device. The above-mentioned second table creation process is repeated for each nearby radio station, a second table for each radio station in the vicinity of the radio station is created and stored in the above storage device, and then the above-mentioned creation is performed. The radio signal including the second table is returned to the source radio station, and the radio station position estimation device is used. When the position coordinates of the first and second radio stations among the plurality of radio stations are known, the position coordinates of the first and second radio stations and the first and second radio stations Based on the second table stored in the storage device, the position coordinates of the third radio station among the plurality of radio stations in the transmission area of the first and second radio stations are calculated. The transmission area of the second and third radio stations based on the position coordinates of the second and third radio stations and the second table stored in the storage device of the second and third radio stations. It is characterized in that it is provided with a control means for calculating the position coordinates of the fourth radio station among the plurality of radio stations in the room.</p><p> In the radio station position estimation device, the control means has at least one pair of each of the first, second, and third radio stations before calculating the position coordinates of the third radio station. Each of the first, second, and third radio stations described above detects each radiation beam pattern that points in the direction of each other, and based on each of the detected radiation beam patterns. After calculating each synchronized radiation beam pattern corresponding to each radiation beam pattern, creating a third table showing the relationship of each of the calculated radiation beam patterns and storing it in the storage device, the created third table is created. Based on the table of 3, calculate the position coordinates of the above third radio station, Before calculating the position coordinates of the fourth radio station, each radiation beam pattern pointing in the positional direction of each other is detected between the pair of radio stations of the third and fourth radio stations, and the detection is detected. Based on each radiation beam pattern, each of the synchronized radiation beam patterns corresponding to each radiation beam pattern of one of the third and fourth radio stations is calculated, and each of the calculated radiations is calculated. After creating a fourth table showing the relationship between beam patterns and storing it in the storage device, calculate the position coordinates of the fourth radio station based on the created third and fourth tables. It is characterized by.</p><p> Further, the radio station position estimation method according to the second invention includes a plurality of radio stations and estimates the position of the radio station at a plurality of hop positions in a radio network in which radio communication is performed between the radio stations. In the estimation method, each of the above radio stations sweeps while switching the radiation beam pattern over all directions at a predetermined angle, and a predetermined radio beacon signal including the position information of the transmission source radio station and the radiation beam pattern information thereof. The radio station that has received the radio beacon signal measures the signal strength of the radio beacon signal for each of the radiation beam patterns, and displays a first table including the signal strength of each measured radiation beam pattern. Create and store in the storage device, search for information on the radiation beam pattern with the maximum signal strength based on the first table, create a second table, store in the storage device, and store the radio. The process of creating the second table above is repeated for each radio station in the vicinity of the station, a second table is created for each radio station in the vicinity of the radio station, stored in the storage device, and then created. The radio signal including the second table is returned to the source radio station, and the radio station position estimation method is When the position coordinates of the first and second radio stations among the plurality of radio stations are known, the position coordinates of the first and second radio stations and the first and second radio stations Based on the second table stored in the storage device, the position coordinates of the third radio station among the plurality of radio stations in the transmission area of the first and second radio stations are calculated. The transmission area of the second and third radio stations based on the position coordinates of the second and third radio stations and the second table stored in the storage device of the second and third radio stations. It is characterized by including a control step of calculating the position coordinates of the fourth radio station among the plurality of radio stations in the above.</p><p> In the radio station position estimation method, the control step performs at least one pair of radio stations of the first, second, and third radio stations before calculating the position coordinates of the third radio station. Each of the first, second, and third radio stations described above detects each radiation beam pattern that points in the direction of each other, and based on each of the detected radiation beam patterns. After calculating each synchronized radiation beam pattern corresponding to each radiation beam pattern, creating a third table showing the relationship of each of the calculated radiation beam patterns and storing it in the storage device, the created third table is created. The step of calculating the position coordinates of the third radio station based on the table of 3 and Before calculating the position coordinates of the fourth radio station, each radiation beam pattern pointing in the positional direction of each other is detected between the pair of radio stations of the third and fourth radio stations, and the detection is detected. Based on each radiation beam pattern, each of the synchronized radiation beam patterns corresponding to each radiation beam pattern of one of the third and fourth radio stations is calculated, and each of the calculated radiations is calculated. A step of creating a fourth table showing the relationship between beam patterns and storing it in the storage device, and then calculating the position coordinates of the fourth radio station based on the created third and fourth tables. It is characterized by including and.</p>

<p> Therefore, according to the radio station position estimation device and method according to the present invention, when the position coordinates of the first and second radio stations among the plurality of radio stations are known, the first and second radio stations are described. A plurality of the above-mentioned plurality within the transmission area of the above-mentioned first and second radio stations based on each position coordinate of the radio station and the second table stored in the storage device of the above-mentioned first and second radio stations. The position coordinates of the third radio station among the radio stations are calculated, and the position coordinates of the second and third radio stations and the second stored in the storage devices of the second and third radio stations are stored. By calculating the position coordinates of the fourth radio station among the plurality of radio stations in the transmission area of the second and third radio stations based on the table, the area outside the area in multihop In the position estimation of the radio station, the configuration is simple as compared with the conventional example, and the position estimation of the radio station can be performed with high accuracy and surely.</p><p> Further, before calculating the position coordinates of the radio stations, each pair of radio stations detects each radiation beam pattern facing each other's positional direction, and based on each of the detected radiation beam patterns, the above Since each synchronized radiation beam pattern corresponding to each radiation beam pattern of one radio station was calculated and the third and fourth tables showing the relationship of each of the calculated radiation beam patterns were created, it is multi-hop. In the position estimation of the radio station outside the area, the position estimation of the radio station can be performed with higher accuracy and more reliably than in the conventional example.</p>

Hereinafter, embodiments according to the present invention will be described with reference to the drawings. The same reference numerals are given to the same components.

In this embodiment, another advantage of the directional antenna in estimating the approximate position of the node radio station is explored without using any additional hardware such as GPS (Global Positioning System). Set up a test device for an ad hoc radio network that uses a directional antenna to demonstrate the effectiveness of the directional tracking in the vicinity of each node radio station and the subsequent position estimation method for each node radio station's two reference node radio stations. To do. This proximity tracking and location estimation method not only helps in the implementation of directional routing protocols such as directional MAC and location-assisted routing, but also allows each node radio station to approximate the location of other node radio stations in the network. It also helps in applications related to location-based services that need to know.

In order to fully utilize the capabilities of the directional antenna, each node radio station needs to know in advance information about neighboring node radio stations (node radio station ID, direction, link quality, etc.). Whenever a source node radio station and a destination node radio station are communicating, all node radio stations in the vicinity of the source and destination node radio stations have ongoing data communication between the source and destination. The communication direction must be recognized so that new communication can be started in another direction without interfering with it. In other words, in order to implement a valid MAC and routing protocol in this radio communication system, a node radio station must know how to set its transmission direction for transmitting packets to its neighbor node radio stations. Therefore, it is indispensable for each node radio station to have a mechanism for tracking the position of its neighboring node radio station.

In this embodiment, it has been shown that position tracking and position estimation require the use of multiple beacons and complex observations of position data. This limits the applicability of our mechanism in the case of high mobility, but in semi-static cases (where mobility is rare or only a few node radio stations move), this method works well. Operate. Application areas include sensor networks for remote environmental monitoring (forests, mines, areas prone to natural disasters, etc.) or regional networks in remote areas (eg, remote area geodetic surveys or hiking and trekking).

FIG. 1 shows a plurality of radio stations 1-1 to 1-9 (collectively, reference numeral 1) showing a configuration of an ad hoc radio network having a radio station position estimation function according to an embodiment of the present invention. It is a plan layout view, and FIG. 2 is a block diagram showing the configuration of each radio station 1 of FIG.

In the radio communication system of this embodiment, as shown in FIG. 1, a plurality of radio stations 1 are scattered in a plane, and each radio station 1 has the gain, transmission power, and reception sensitivity of the variable beam antenna 101, respectively. It has a predetermined service area determined by parameters such as, and can perform packet communication within this service area. When performing packet communication with radio station 1 outside the service area, radio station 1 within the service area Is used as a relay station to relay packet data, thereby transmitting packet data to a desired destination radio station 1. That is, each radio station 1 has a router function for routing packets, and operates as a source radio station, a relay station, or a destination radio station.

The wireless communication system of this embodiment is applied to a packet communication system of an ad hoc wireless network such as a wireless LAN, and has an omni-pattern which is an omnidirectional radiation pattern and a predetermined position in a horizontal plane centered on the own station. A variable beam antenna 101 capable of selectively switching between a sector beam pattern in which the sector-shaped main beam can be selectively changed for each azimuth angle and an exclusive sector pattern in which a null point can be formed for each azimuth angle. The Neighbor Link-State Table (hereinafter referred to as the NLS table) and the Angle and Signal strength Table (hereinafter referred to as the AS table) are stored in the database memory 154. However, based on these tables, it is characterized in that the packet signal routing process and the radio station position estimation process are executed while controlling the radiation pattern of the variable beam antenna 101.

In this embodiment, a node radio station N_AIs a beacon signal (node radio station N_AIncludes location information and radiation pattern number. ), For example, 12 directional patterns every 30 degrees (radiation pattern numbers are 0 to 11) are sequentially switched and swept, whereas the node radio station N_AEach neighboring node radio station N_B(One or more) is received in an omnidirectional pattern and includes, for example, the NLS table (radiation pattern number, azimuth, signal intensity) shown in FIG. 5 by measuring the signal intensity for each radiation pattern number. ) Is created and stored in the database memory 154.

After creating the NLS table, each neighboring node radio station N_BSearches for the azimuth having the maximum signal strength based on the NLS table, and uses the searched azimuth as the node radio station N that transmitted the beacon signal._AThe detected azimuth angle and its signal strength level are stored in the AS table. Multiple node radio stations N in the radio communication system_ABy repeating periodically so that they do not overlap each other in time, each neighboring node radio station N_BIn, for example, as shown in Fig. 6, an AS table can be created, and each neighboring node radio station N_BIs a node radio station N_AThe information of the AS table is transmitted in an omnidirectional pattern. In response to this, node radio station N_AReceives the AS table and stores it in the database memory 154. After the above processing is repeated in each node radio station, the radio station position estimation processing described in detail later is executed.

Next, the device configuration of each radio station 1 will be described with reference to FIG. In FIG. 2, the radio station 1 has a variable beam antenna 101, a directivity control unit 103 for controlling its directivity, a circulator 102, and a data packet transmission / reception unit having a data packet transmission unit 140 and a data packet reception unit 130. It includes 104, a packet monitor unit 105, a line control unit 106, and an upper layer processing device 107.

The packet-format communication transmission signal data generated by the upper layer processing device 107 that processes the data to be transmitted and received is input to the modulator 143 via the transmission buffer memory 142, and the modulator 143 has a predetermined radio frequency. The carrier signal is spectrally spread-modulated according to the input communication transmission signal data using the spread code for a predetermined communication channel generated by the spread code generator 160 in the CDMA system, and the modulated transmission signal is transmitted at high frequency. Output to machine 144. The high-frequency transmitter 144 executes processing such as amplification on the input transmission signal, and then transmits the input signal from the variable beam antenna 101 to the other radio station 1 via the circulator 102. On the other hand, the packet-type communication channel reception signal received by the variable beam antenna 101 is input to the high-frequency receiver 131 via the circulator 102, and the high-frequency receiver 131 amplifies low noise with respect to the input received signal. After executing the process of, output to the demodulator 132. The demodulator 132 demodulates the input received signal by spectral despreading using the communication channel spreading code generated by the spreading code generator 160 in the CDMA system, and receives the demodulated received signal data in the reception buffer. It is output to the upper layer processing device 107 via the memory 133, and is also output to the traffic monitor unit 105 for the traffic monitor.

In the present embodiment, the variable beam antenna 101, which is a directional antenna, is connected to a plurality of antenna elements and a control unit 103 that controls their directivity, and (a) an omni pattern, which is an omnidirectional radiation pattern, and ( b) For example, as shown in FIG. 3, a sector beam pattern in which the sector-shaped main beam can be selectively changed for each predetermined azimuth angle in the horizontal plane centered on the own station, and (c) for each of the above azimuth angles. It is an antenna that can selectively switch between an exclusive sector pattern that can form a null point and an exclusive sector pattern that can form a null point by electrical control. The variable beam antenna 101 may be, for example, a known phased array antenna device, or an electronically controlled waveguide array antenna device (Electronically) disclosed in Patent Documents 1 and Non-Patent Documents 1 and 2. It may be a variable beam antenna (Steerable Passive Array Radiator Array Antenna MFP).

The traffic monitor unit 105 includes a search engine 152, an update engine 153, a database memory 154, and a clock circuit 155, executes routing and communication processing described later, and has a radio station 1 with another radio station 1. By determining the communication channel to be used in packet communication and sending the spread code designation data corresponding to the determined communication channel to the spread code generator 160 via the line control unit 106, the spread code generator 160 is concerned. The transmission timing control unit is controlled so that the spread code corresponding to the specified data is generated, and the specified data of the time slot corresponding to the determined communication channel is sent to the transmission timing control unit 141 via the line control unit 106. The 141 controls the writing and reading of the communication channel transmission signal data by the transmission buffer memory 142 so that the communication channel transmission signal is transmitted in the corresponding time slot. The clock circuit 155 clocks the current date and time and outputs the information to the management control unit 151 as needed.

The search engine 152 of the traffic monitor unit 105 searches for data in the database memory 154 under the control of the management control unit 151, and returns the searched data to the management control unit 151. Further, the update engine 153 updates the data in the database memory 154 under the control of the management control unit 151. Further, the database memory 154 stores an AS table, an NLS table, and a known routing table (not shown).

In the present embodiment, the effective transmission beam width of the sector beam pattern that changes the directivity of the antenna radiation pattern so as to maximize the gain in the direction of a single communication partner is set to 30 °, and the variable beam antenna 101 Can selectively change the azimuth every 30 °. The change angle of the beam width and the azimuth angle may be 60 ° or another angle. Further, the packet data used in the packet communication system of the present embodiment has the format shown in FIG. That is, the packet data includes the ID of the destination radio station, the packet type (tone, ANL table, RTS (Request To Send), CTS (Clear To Send), DATA, etc.), the ID of the own station, and the data (upper layer). Including data etc.) and. Further, as shown in FIG. 6, the AS table stored in the database memory 154 stores information on the azimuth angle and signal strength level for each adjacent node radio station in the service area of the own station, and controls packet transmission / reception. Created and updated by processing.

Next, the MAC communication protocol used in this embodiment will be described below. In the wireless communication network according to the present embodiment, it is assumed that a set of wireless stations 1 that perform wireless communication with each other move around in a two-dimensional closed space and share a common wireless communication channel. Each radio station 1 comprises a variable beam antenna 101 having, for example, an electronically controlled waveguide array antenna device having the four radiation patterns described above. Each radio station 1 can perform either transmission or reception at one time, but one radio station 1 cannot transmit or receive a plurality of transmissions.

In the MAC protocol standard of IEEE802.11, highly reliable data communication is guaranteed by using the RTS / CTS / DATA / ACK access control method, but in the method of this embodiment, this access control method is used as a base. , As will be described later with reference to FIGS. 7 and 8, a packet signal including an ANL table and other data is transmitted and received using a control signal using a tone signal + a packet signal. Therefore, data communication is performed periodically between the ANL table generation and update phases. In addition, a training sequence is added to each frame to allow transmission and reception antennas to control its beam and null and transition to adaptive control mode.

The MAC protocol invented by the inventors in this embodiment is basically a "receiver-oriented, rotating sector-based directional MAC protocol", which also functions as a position tracking mechanism. In this case, each node radio station waits in omnidirectional detection mode while idle. It enters a "rotating sector receive mode" each time it detects any signal that exceeds the threshold. In the "rotating sector reception mode", the node radio station n sequentially rotates its directional antenna in all directions, for example, at intervals of 30 degrees, and covers the entire 360-degree space in the form of sequential directional reception in each direction. The signal received in each direction is detected. After one revolution, this determines what may be the best signal receiving direction by the maximum signal strength received. The beam is then set in that direction and the signal is received.

Here, in order to enable the receiver to decode the received signal, each control packet has a duration of the tone signal (in our simulation, the time it takes to rotate the receiver's rotating receive beam 360 degrees. In this case, it is transmitted with a leading tone signal having a duration such that it is slightly shorter than 200 microseconds). The purpose of transmitting this tone signal prior to any control packet signal is to allow the receiver to track what may be the best direction to receive the signal. When this sets the beam in that direction, the purpose of the tone signal is served, followed by the control packet signal.

In the framework according to the present embodiment proposed by the present inventors, the following four types of broadcast (omnidirectional) control packets are used for medium access control. (1) Packet signal including ANL table (ANL packet signal), (2) Packet signal including RTS (transmission request) signal, and (3) Packet signal including CTS (transmission possible) signal.

In addition, the control packet ACK signal is also a directional control packet. The packet signal containing the data is directed and transmitted after the RTS / CTS handshake is performed. As described above, the ANL packet signal and the GLS packet signal are periodic signals, and are transmitted from each node radio station at a predetermined transmission cycle (transmission interval). At each periodic interval, for example, each node radio station m broadcasts an ANL packet to its neighbor node radio station, if its radio medium (radio channel) is free. As pointed out earlier, ANL packets are transmitted with a leading tone signal that helps the receiver detect what may be the best way to receive the signal. Each receiver then sets its beam in that direction, receives the packet, and decodes it (see Figure 7).

Further, the node radio station n checks the radio medium (radio channel) every time it wants to start data communication with the node radio station j, and issues an omnidirectional RTS signal if the radio medium is free. And send. When the destination radio station j receives the RTS signal, it issues and transmits an omnidirectional CTS signal. The purpose of RTS / CTS in this case is not to prohibit transmission or reception of node radio stations n and j by adjacent node radio stations (as in the case of using an omni-antenna), but of node radio stations n and j. The purpose is to inform the neighboring node radio station that the neighboring node radio station j is about to receive a data packet from the node radio station n. It also identifies the approximate duration of communication. All adjacent node radio stations of node radio stations n and j are their Directional Network Allocation. Vector (DNAV)) is set in the direction of node radio stations n and j to track communication between node radio stations n and j. Therefore, the node radio stations existing adjacent to the node radio stations n and j can communicate in the other direction "without interfering with the communication between the node radio station n and the node radio station j". You can start. The source radio station and the destination radio station wait for an acknowledgment signal and a data packet signal, respectively, in the directional reception mode.

Next, the details of the wireless communication system for the ad hoc wireless network using the wireless station 1 of FIG. 1 will be described below.

As the variable beam antenna 101 in FIG. 1, as described above, an electronically controlled waveguide array antenna device is preferably used. A typical adaptive array antenna is usually a digital beam forming antenna. Electronically controlled waveguide array antenna devices, on the other hand, rely on high frequency beam formation, which significantly reduces circuit complexity. The electronically controlled waveguide array antenna device consists of a central excitation element connected to the radio transmitter / receiver of the source radio station, and a plurality of non-excitation elements provided on a predetermined radius around the excitation element and surrounded by a circular shape. It is configured to include excitation elements (typically 4 to 6). A variable reactance element is connected to each non-exciting element, and by adjusting the reactance value thereof, each non-exciting element forms a radiation pattern of the array antenna device into a different shape. The electronically controlled waveguide array antenna device is characterized by beam direction control, multiple beam formation at the same frequency, movable (360-degree sweep scanning is possible) beam and null steering control. The advantage of using the electronically controlled waveguide array antenna device as a generalized switching beam antenna is that it can be continuously tracked with a small number of antenna elements and can have a variable number of beam patterns. It is in. Since the electronically controlled waveguide array antenna device becomes a small antenna with low cost and low power consumption, the reduction of power consumption of the node radio station which is the user terminal is promoted, and all the advantages of the beam antenna for switching are derived. Becomes possible.

Next, the location tracking of the radio station and the discovery of the nearby node radio station in the radio system according to the present embodiment will be described below.

First, a method of creating an NLS table will be described. In order to effectively communicate with a nearby node radio station using a directional antenna, the node radio station has a node in its vicinity to set the radiation beam of that antenna to communicate with its neighbor node radio station. You need to know the exact direction of each of the radio stations. Each node radio station periodically performs this directional position tracking. Normally, each node radio station waits in an omnidirectional reception mode while idle. In starting the position tracking, for example, a node radio station of Nn broadcasts 12 directional beacon signals in sequence using the 12 directional beam patterns. Each beacon signal includes a node radio station ID (including its two-dimensional position information) and a corresponding transmission direction (such as a radiation pattern number). This is done in all directions, sequentially at 30 degree intervals, covering a 360 degree span. A nearby node radio station (for example, Ni) in the vicinity of the node radio station Nn waiting in the omnidirectional reception mode receives each directional broadcast packet and transfers the received signal strength from the node radio station Nn to the node radio station. Record as detected by node radio station Ni in each direction to Ni (SIGNAL^α_ni, α = {0,30,60, ..., 330}). The NLS table for the node radio station Nn in the node radio station Ni is generated in this way and stored in the database memory 154. FIG. 4 shows an example of a typical NLS table in the node radio station Ni.

Similarly, all node radio stations transmit periodic directional beacon signals, for example each node radio station, which is node radio station Ni, has an NLS table for all its neighboring node radio stations in the format shown in Figure 4. Generate and update periodically.

Next, a method of creating an AS table will be described. After creating the NLS table, the node radio station Ni has the beam pattern of the node radio station Nn when it receives the signal having the maximum signal strength from the node radio station Nn and the corresponding signal strength value received from the node radio station Nn. And calculate. The node radio station Ni then transmits this information to the node radio station Nn in an omnidirectional pattern. Upon receiving this, the node radio station Nn records this information in its AS table. Similarly, the node radio station Nn receives similar information from all its neighboring node radio stations and updates its AS table. Therefore, the AS table in any node radio station Nn is basically the best possible direction to access the node radio station in the vicinity of the node radio station Nn and each node radio station in the vicinity of the node radio station Nn, and the corresponding best direction. Includes the signal strength detected by each neighboring node radio station in. This neighborhood information for constructing the AS table will periodically arrive at any node radio station Nn. If the node radio station Nn does not receive the direction information from any of the neighboring node radio stations for a predetermined time, the input corresponding to the neighboring node radio station is deleted from the AS table.

Next, the radio station position estimation process will be described below.

Here, a simple estimation mechanism of the position of a node radio station in an ad hoc radio network will be described. In the mechanism proposed in this embodiment, the node radio station applies a simple triangulation technique based on the geometric characteristics of a triangle to calculate its unique position. The triangulation argument refers to either a distance measurement or an angle measurement. Distance measurements can be used to calculate a position from distance measurements from multiple reference positions, and angle measurements use angle measurements for multiple reference positions instead of distance measurements to determine the position of an object. calculate. In two-dimensional space, the position of an object can be uniquely identified if there are two angle measurements and the positions of two reference node radio stations. Therefore, the proposed position estimation technique provides the best signal angle of arrival from a well-positioned reference node radio station pair to a node radio station. Arival: AOA) is used. Any node radio station can obtain the best signal arrival angle (AOA) measurement from a nearby reference node radio station in its NLS table via a location tracking / neighborhood discovery process. Therefore, a node radio station within the range (transmission area) of a reference node radio station pair is determined from the best signal arrival angle (AOA) from each reference node radio station and the coordinates provided by these two reference node radio stations. Unique coordinates can be calculated. Therefore, under the framework of the proposal, it is possible to find the coordinates of node radio stations within the range of the specified reference node radio station pair.

However, a problem arises when the node radio stations are separated from both reference node radio stations by a plurality of hops. In such cases, the measurement of the signal arrival angle (AOA) from both reference node radio stations is not available, so in this case the position of that node radio station cannot be estimated by the method described above. Therefore, in the position estimation mechanism proposed by the present inventors, a multi-hop extension in which a node radio station in the vicinity of one hop of a reference node radio station pair (primary reference node radio station) voluntarily becomes a secondary reference node radio station is developed. is suggesting. As a result, the node radio station, which is then two hops away from the primary reference node radio station, uses this secondary reference node radio station to calculate its position by the procedure described above. Similarly, a neighboring node radio station 3 hops away from the primary reference node radio station uses these second hop node radio stations as its reference node radio station. In this way, it is possible to gradually estimate the locations of all node radio stations in the network.

In order to accurately determine the position of the two-hop node radio station, it is necessary to synchronize the alignment between the antenna of the secondary reference node radio station and the primary reference node radio station. The synchronization of the alignment between the antenna and the reference node radio station necessarily refers to the alignment of the 0th beam pattern of the antenna with that of the reference node radio station. Otherwise, the coordinate frame used by the one-hop neighborhood node radio station at the primary reference point will be different from that used by the two-hop neighborhood node radio station. Therefore, synchronization of antenna orientation is essential to implement a common reference frame for position estimation. Gradual antenna synchronization between the primary reference node radio station and the secondary reference node radio station (and between the secondary and tertiary reference node radio stations, etc.) is a common reference for all node radio stations in the network. Build up the frame.

The following description first describes the basic mechanism for calculating the coordinates of a node radio station in relation to the primary reference position pair, and then the antenna and reference, which is a crucial task in calculating the position of a remote node radio station. The synchronization process with the node radio station will be described in detail. Finally, the position estimation process of the node radio station separated from the primary reference node radio station by multiple hops is shown.

First, the position estimation processing procedure by the node radio station using the reference node radio station pair will be described.

&lt;Step 1&gt; First, select two node radio stations as the two primary reference node radio stations (these location information is known). Here, for example, as shown in FIG. 13, both 0th beam patterns are aligned across the X-axis, one node radio station is placed at (0,0), and the other node radio station is (x0). , 0). In the proposed case, the coordinates of the node radio station are calculated based on these two reference coordinate sets and the corresponding angle of arrival of the best signal from these reference node radio stations to that node radio station. Information on the best beam pattern that allows a nearby node radio station to access a node radio station is available from the NLS table held by each node radio station. From this beam pattern, the corresponding angle of arrival can be obtained. For example, the arrival angle of radiation pattern number 0 is 0, radiation pattern number 1 is 30 °, and radiation pattern number 2 is 60. The same applies to the following. ). Therefore, the best signal arrival angle from a reference node radio station to a node radio station can be deciphered from the corresponding beam pattern stored in the MGLS table of that node radio station. This method was used in the proposed coordinate calculation process.

&lt;Step 2&gt; Each reference node radio station periodically transmits its coordinates via a directional beacon, so other node radio stations located in the vicinity of either or both of the reference node radio stations transmit this information. You can collect and calculate your own coordinates.

&lt;Step 3&gt; If a node radio station (for example, P in FIG. 9) can manage to collect the coordinates of two reference node radio stations R1 and R2 (this is because this node radio station can manage to collect the coordinates of the reference node radio stations R1 and R2). It is possible only if it is within the transmission range of both of them. That is, it is assumed that the position coordinates of the neighboring node radio stations R1 and R2 are known.) The node radio station is available to the node radio station. Immediately calculate its own coordinates (p, q) using one of the following four parameters. (a) Coordinates (x1, y1) of reference node radio station R1 which is (0,0) in this case, (b) Coordinates (x2, y2) of neighboring node radio station R2 which is (x0,0) in this case. ), (C) Signal arrival angle from reference node radio station R1 (α) and (d) Signal arrival angle from reference node radio station R2 (β). Here, the coordinates of the node radio station P can be easily calculated using the following process.

In FIG. 9, the general formula for the line PR1 and the line PR2 is expressed by the following formula.

[Number 1]

(y-y1) = tanα (x-x1) (1) [Number 2]

(y-y2) = tanβ (x-x2) (2)

Here, the node radio station P (p, q) is the intersection of line PR1 and line PR2. Therefore, by substituting (p, q) for (x, y) in the above equations (1) and (2), the following equation is obtained.

[Number 3]

p = ((y2-y1) + x1tanα-x2tanβ) / (tanα-tanβ) (3) [Number 4]

q = ((x1-x2) tanαtanβ + (y2tanα-y1tanβ)) / (tanα-tanβ) (4)

&lt;Step 4&gt; Node radio stations separated from the primary reference node radio station by 2 hops have their coordinates calculated from the above parameters because there is no direct link between these reference node radio stations and this node radio station. Cannot be calculated. Therefore, in this case, a node radio station separated by two hops must use a node radio station such as P as its reference node radio station and calculate its coordinates. Therefore, in this case, P operates as a secondary reference node radio station. However, before that, a secondary reference node radio station such as P synchronizes its antenna with the primary reference node radio station so that it can share a common reference frame and other in connection with this same reference frame. It must be possible to help remote node radio stations calculate their location. Therefore, after synchronizing the antennas, the node radio station P can voluntarily become the secondary reference node radio station.

Further, antenna synchronization by the non-primary reference node radio station will be described below.

An electronically controlled waveguide as a directional antenna model with 12 predetermined radiation beam patterns identified by 0 to 11 beam patterns counterclockwise as a possible solution to this problem. It is shown while considering the array antenna device. The reference node radio station R1 aligns its 0th beam eastward, for example the 0th beam of another node radio station, which is P, is set at an angle of 120 ° with respect to the 0th beam of this R1. It shall be (Fig. 10). In this case, the beam pattern in which R1 accesses P is, for example, 5. Therefore, ideally, in a common reference frame, the node radio station P should access the reference node radio station R1 with its reverse beam pattern 11 (= 5 + 6).

However, the initial alignment of the 0th beam of node radio station P is 120 ° counterclockwise with respect to that of reference node radio station R1. Therefore, according to node radio station P, the best beam pattern to access reference node radio station R1 is recorded in its AS table as radiation pattern number 7 instead of radiation pattern number 11 (Fig. 11). This discrepancy in beam patterns occurs due to the different initial alignments of the antennas at node radio station P and reference node radio station R1.

Therefore, the best beam pattern from the reference node radio station R1 (or R2) is extracted by the node radio station P from the beacon transmitted by the reference node radio station R1 (or R2) according to the alignment of both antennas. However, the original alignment of node radio station P may differ from the alignment of node radio station R1 (or R2). Therefore, the node radio station P must map its beam pattern according to the alignment of the reference node radio station R1 (or R2) and synchronize its reference frame with the primary reference node radio station. However, this does not mean that the node radio station P must guarantee a similar physical antenna alignment as in the case of the reference node radio station R1. Therefore, the node radio station P can send a beacon indicating a synchronized beam pattern rather than the original alignment of the beam pattern from that point onward, so that the current beam pattern (or radiation pattern number) can be transmitted through some mechanism. ) Must be mapped to the synchronized beam pattern. In other words, node radio station P renames its beam pattern without physically changing the orientation of its antenna. This renaming is done using the mapping table in FIG. Therefore, instead of physically aligning the antennas of the node radio stations, the mapping table logically aligns its original beam pattern to a common reference frame.

Next, a method of forming the mapping table after synchronization will be described below.

&lt;Step 11&gt; For example, the node radio station P is first discovering a beam pattern (radiation pattern number) for obtaining a beacon signal having the maximum signal strength from a nearby reference node radio station R1. This is the best beam pattern for reference node radio station R1 to access node radio station P. This information is obtained from the NLS table of node radio station P, and this is referred to as px.

&lt;Step 12&gt; The reference node radio station R1 then derives the inverse pattern of the pattern px. This can be done as follows. Since the electronically controlled waveguide array antenna device has 12 beam patterns, it can be derived by the following equation.

[Number 5]

If 0 px 5, the reverse beam pattern of the pattern px = px + 6. (5) [Number 6]

If 6 px 11, the reverse beam pattern of the pattern px = px-6. (6)

&lt;Step 13&gt; Next, the node radio station P examines its AS table to find the best beam pattern recording for accessing the reference node radio station R1. Let this be py.

&lt;Step 14&gt; Next, the node radio station P associates the reverse beam pattern with py to form a mapping table including the radiation pattern number after synchronization as shown below. &lt;Step 14a&gt; The node radio station P first determines the calculated value of the reverse beam pattern (calculated using step 12, from the node radio station P to the reference node radio station R1) and the reference described in its AS table. Find the difference obtained from the best beam pattern (py) to access the node radio station R1. This difference is called an offset. &lt;Step 14b&gt; Next, the node radio station P adds this offset value for each beam pattern to obtain the corresponding post-synchronization beam pattern as shown below. &lt;Step 14b1&gt; If the resulting value is 11 or less, store this result value in the mapping table as the synchronized beam pattern of the corresponding pattern. &lt;Step 14b2&gt; However, if the resulting value is above 11, the actual post-synchronization beam pattern for the corresponding pattern will be (resulting value-12).

When the above mapping table creation procedure is applied to the example shown in Fig. 10, it becomes as follows. In FIG. 10, the beam pattern Pp0 of the node radio station P indicates the direction of the radiation pattern number 0, and the beam pattern Pp3 of the node radio station P indicates the direction of the radiation pattern number 3. Further, the beam pattern R1p0 of the node radio station R1 indicates the direction of the radiation pattern number 0, and the beam pattern R1p3 of the node radio station R1 indicates the direction of the radiation pattern number 3.

(1) The node radio station P receives a signal having the maximum signal strength with, for example, radiation pattern number 5 from the reference node radio station R1. In FIG. 10, the best beam pattern (R1-P) = 5 is shown. (2) Next, the node radio station P calculates the radiation pattern number opposite to the radiation pattern number 5 as 5 + 6 = 11. (3) Next, the node radio station P discovers that the radiation pattern number of the best beam pattern for accessing the reference node radio station R1 from its AS table is 7. (4) The offset (the difference between the calculated reverse beam pattern (P-R1) and the best beam pattern (P-R1) listed in the AS table) is (11-7 = 4). (5) Now, the node radio station P creates a post-synchronization mapping table as shown in FIG. 11 and stores it in the database memory 152 according to the rule described in step 14b above.

Therefore, after creating the mapping table and calculating the self-coordinates, any node radio station (eg P) is of a node radio station physically distal to the fixed reference node radio stations R1 and R2. It is possible to act like a secondary reference node radio station for.

Further, a method of estimating the position of the node radio station separated from the reference node radio station by a plurality of hops will be described below.

A node radio station (eg Q) that is separated from the primary reference node radio stations R1 and R2 by multiple hops (eg 2 hops) has a direct link between the reference node radio stations R1 and R2 and the node radio station Q. Therefore, it is not possible to calculate its coordinates directly using the process described above. In this case, the node radio station Q must use a node radio station such as the node radio stations P and S shown in FIG. 12 as its reference node radio station and calculate its coordinates. Therefore, the node radio stations P and S in this case operate as secondary reference node radio stations. However, before that, a secondary reference node radio station such as node radio station P synchronizes its antenna with the primary reference node radio station using the method described above (a radiation pattern synchronization method using a mapping table). It must be able to share a common reference frame and help other remote node radio stations, such as Q, to calculate their position in relation to this same reference frame. Therefore, after the post-synchronization mapping table is formed in the node radio station P (an example is shown in FIG. 11), the node radio station P can voluntarily become a secondary reference node radio station. The node radio station Q then uses the positions of two nearby secondary reference node radio stations, such as the node radio stations P, S, and the corresponding angle of arrival (AOA) of the signals from them, as described in detail above. The coordinates can be calculated using the above equations (3) and (4).

In FIG. 13, the position of the node radio station P is estimated from the two reference node radio stations A and B by the radio station position estimation function of the ad hoc radio network of FIG. 1, and then from the second reference node radio stations P and B. It is a top view for demonstrating the method of estimating the position of a node radio station Q. In FIG. 13, it is assumed that the node radio stations A, B, and P are in these transmission areas, but the node radio station Q is outside the transmission area from the node radio station A. In FIG. 13, after calculating the position coordinates of the node radio station P from the node radio stations A and B whose respective position coordinates are known, the position coordinates of the node radio station Q are calculated from the node radio stations P and B. Here, before the calculation of the position coordinates of the node radio station P, the mapping tables are synchronized in the node radio stations A, B, and P, and the position coordinates of the node radio station P are calculated, for example, in the node radio station P. In addition, before calculating the position coordinates of the node radio station Q, the mapping tables are synchronized in the node radio stations B, P, Q (at least the node radio stations P, Q) to calculate the position coordinates of the node radio station Q. For example, it needs to be performed at the node radio station Q.

As described above, in the present embodiment, mapping is performed when the position of a node radio station of a plurality of hops is estimated by using the position tracking and position estimation method of the node radio station in an ad hoc radio network using a directional antenna. Since the tables are synchronized, the position of the node radio station can be estimated with higher accuracy than in the conventional example.

As described in detail above, according to the radio station position estimation device and method according to the present invention, when the position coordinates of the first and second radio stations among the plurality of radio stations are known, the first And within the transmission area of the first and second radio stations based on the respective position coordinates of the first and second radio stations and the second table stored in the storage devices of the first and second radio stations. , The position coordinates of the third radio station among the plurality of radio stations are calculated and stored in the storage devices of the second and third radio stations and the storage devices of the second and third radio stations. By calculating the position coordinates of the fourth radio station among the plurality of radio stations in the transmission area of the second and third radio stations based on the second table, in multi-hop. In the position estimation of the radio station outside the area, the configuration is simple as compared with the conventional example, and the position estimation of the radio station can be performed with high accuracy and surely.

Further, before calculating the position coordinates of the radio stations, each pair of radio stations detects each radiation beam pattern facing each other's positional direction, and based on each of the detected radiation beam patterns, the above Since each synchronized radiation beam pattern corresponding to each radiation beam pattern of one radio station was calculated and the third and fourth tables showing the relationship of each of the calculated radiation beam patterns were created, it is multi-hop. In the position estimation of the radio station outside the area, the position estimation of the radio station can be performed with higher accuracy and more reliably than in the conventional example.

<figref num="1">It is a plane layout of a plurality of radio stations 1-1 to 1-9 constituting an ad hoc radio network having a radio station position estimation function according to the embodiment of the present invention.</figref><figref num="2">It is a block diagram which shows the internal structure of each radio station 1 of FIG.</figref><figref num="3">It is a figure which shows an example of the sector beam pattern of the variable beam antenna 101 of FIG.</figref><figref num="4">It is a figure which shows the format of the packet data used in the ad hoc wireless network of FIG.</figref><figref num="5">It is a figure which shows an example of the NLS table measured in each radio station 1 of FIG.</figref><figref num="6">It is a figure which shows an example of the AS table measured in each radio station 1 of FIG.</figref><figref num="7">It is a timing chart which shows the transmission / reception processing of a tone signal and a packet signal used in the ad hoc wireless network of FIG.</figref><figref num="8">It is a timing chart which shows the type of the radiation pattern in each radio station used in the ad hoc radio network of FIG. 1 and the radio communication protocol.</figref><figref num="9">It is a top view for demonstrating the method of calculating the position of a node radio station P from two reference node radio stations R1 and R2 in the radio station position estimation function of the ad hoc radio network of FIG.</figref><figref num="10">It is a top view for demonstrating that the best beam pattern is transmitted and received between two node radio stations R1 and P in the radio station position estimation function of the ad hoc radio network of FIG.</figref><figref num="11">It is a figure which shows an example of the beam pattern number conversion table before and after synchronization for demonstrating the synchronization process of a beam pattern number in the radio station position estimation function of the ad hoc wireless network of FIG.</figref><figref num="12">It is a top view for demonstrating the method of estimating the position of a node radio station Q from the 2nd reference node radio stations P and S in the radio station position estimation function of the ad hoc radio network of FIG.</figref><figref num="13">After estimating the position of node radio station P from two reference node radio stations A and B in the radio station position estimation function of the ad hoc radio network in Fig. 1, node radio station Q from the second reference node radio stations P and B. It is a top view for demonstrating the method of estimating the position of.</figref>

Code description

1,1-1 to 1-9,1-i, 1-j, 1-k, 1-l, N₁To N₆... node radio station, 101 ... variable beam antenna, 102 ... circulator, 103 ... directional control unit, 104 ... packet transmission / reception unit, 105 ... traffic monitor unit, 106 ... line Control unit, 107 ... upper layer processing device, 130 ... packet receiver, 131 ... high frequency receiver, 132 ... demodulator, 133 ... receive buffer memory, 140 ... packet transmitter , 141 ... transmission timing control unit, 142 ... transmission buffer memory, 143 ... circulator, 144 ... high frequency transmitter, 151 ... management control unit, 152 ... search engine, 153. .. update engine, 154 ... database memory, 155 ... clock circuit, 160 ... spread code generator.