Method for deciding communication topology of wireless network consisting of plural distributed nodes

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

Background of the Invention

【0002】

[Field of Invention]

The present invention relates to wireless networks for data transmission, telemetry, or remote monitoring of some physical condition or process. In particular, it relates to a wireless distributed network of remote sensors used to remotely detect and track vehicles and people, or to monitor physical phenomena.

【0003】

[Explanation of related technologies]

Networks that communicate by wiring or by cable means are common and well known. Examples are local area networks (LANs), the Internet, and telephone networks. In such networks, the connection is largely determined by the physical structure of the communication medium and is generally well known before placement. For example, in a bus structure such as Ethernet, when a computer transmits a message, other computers on the bus can receive the message. The computer then needs to take turns using the medium according to the set protocol.

【0004】

Wireless networks, such as wireless link networks, offer more complex possibilities. A wireless network consists of a number of wireless transceivers called "nodes". All (useful) nodes can communicate with at least one other node. However, if the radio range of an individual node is smaller than the size of the entire network, that node can only communicate with an exact subset of other nodes in the network. The remaining nodes are out of communication range. The complete set of information that defines which node can communicate with which other node is called the "topology" of the network.

【0005】

In general, the topology of a wireless network is that each node's transmission is received only by a subset of the other nodes, and each node's view of the medium is different. This type of topology is useful as a "multi-hop network" where the transfer of a message from one node to another can make multiple "hops" (ie, inter-node relay) until it reaches its destination. is there. Multi-hop communication is more efficient when using power because the radio strength has a non-linear inverse relationship with the distance from the transmitter. For example, in an ideal condition where the radio strength follows the inverse square law, 10 small straight hops each with a distance of d each use one-tenth the transmit power of one large hop, so overall that 10 times stronger. In a real environment, intensity attenuation generally follows a function of inverse cube or higher power. In that case, multi-hop transmission saves even more power than single-hop transmission.

【0006】

In one simple implementation of a wireless network, nodes send and receive on the same radio frequency or "channel". It modulates a fixed carrier frequency to transmit information. (This could be generalized as a frequency hop channel where the carrier frequency "hops" pseudo-randomly, but it is still essentially a single channel system as the receivers hop synchronously. In such an implementation, the node can either send or receive, but not both at the same time. This is known as a "half-duplex" or "push-to-talk" system. The ability to detect collisions in the physical layer is not envisioned. In a multi-hop topology, the nodes are basically well separated from each other so that they can communicate well on the same channel at the same time (for example, between CDs and AB at the same time). This is called "spatial reuse" or "frequency reuse".

【0007】

Spatial reuse allows for more efficient use of the limited radio spectrum available in the network. If the network has, for example, 100 nodes and each node has a range that covers the entire network, 100 channels are needed to avoid interference due to simultaneous transmission between the nodes. On the other hand, if the node range is very short and each node can only hear the other two nodes, many distant nodes can use the same channel at the same time, with only 4 channels. There is a possibility that the network can be fully connected without interference. A well-known example is FM radio broadcasting, where the FCC assigns the same or overlapping frequencies to different stations in distant cities. Interference is prevented because the range of each station is limited. More generally, in the case of time domain multiple access (TDMA), the channel is a time slot, and in the case of frequency domain multiple access (FDMA), a frequency band is considered. In either case, the reuse of space allows for more effective use of bandwidth. However, in order to allocate channels and schedule transmissions, it is necessary to know which nodes are far enough apart to interfere with each other (the "interference topology" of the network).

【0008】

In certain applications, such as networks of short range sensors, it is possible to have a large number of nodes (more than 1000) with very limited transmission distances, and therefore for efficient low power communication, Multi-hop routines for messages with some form of channel reuse are needed. Therefore, efficient communication requires some way of knowing the topology of a network whose topology is at least partially unknown at first. For example, a network of wireless sensors may be dropped from an airplane and randomly placed, or several nodes may be run on a pre-characterized network. Once the topology is known, communication is scheduled so that the channels can be reused by nodes outside of each other's range.

【0009】

It is often desirable to know the topology of the network in a distributed manner. The procedure for knowing the topology can be called "distributed" if it operates in a distributed manner that does not require a central controller and only impacts that area of the affected network. The network that adopts such processing is a self-organizing system. Other topology determination methods that operate from the central processing position are possible, but only if relatively high levels of electrical and computational output are available. These methods tend to be easily jammed and easily and completely disabled by hostile behavior or accidental component failure. When applying these methods to a large network with a very large number of nodes, it depends and is limited by the central processing position and capacity.

【0010】

The prior art method of knowing the topology of a wireless network in a distributed manner has serious drawbacks. One of them was explained by Ephremides in "Design Concepts for Highly Reliable Mobile Radio Networks with Frequency Hopping Signaling" (IEEE Minutes, Vol.75, No. 1, pp. 56-73, 1987). ("A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling" Proceedings of the IEEE, Vol. 75, No. 1, pp. 56 --73 (1987)). This method requires allocating a block of N slots in a TDMA frame (where N is the maximum total number of nodes in the entire network). Each node is pre-allocated with a specific time slot for transmission, at least for the duration of the organization. Assigned nodes use this slot to send an understanding of which other nodes they can receive, and ultimately all nodes determine the overall topology. (For example, in a 2N slot). This method has some drawbacks. The upper bound N must be known and all nodes must be assigned their own identification numbers. A more serious problem is that a large number of nodes takes a long time to organize. The method disclosed by Ephremides has utility for networks of less than 100 nodes and is not practical for larger networks. This limitation arises because this method uses one global time slot (channel) for each node during organization. That is, a network with a large number of nodes requires many time slots in each time frame, which slows down organization. This method is useful in networks with a small number of highly mobile nodes. It can also be used to "boot up" a set of nodes to initialize the network. However, it is not efficient for large networks where the nodes are basically fixed (for a period of time). The addition of new nodes is limited because the total number of nodes is limited to N (the number of time slots initially allocated).

【0011】

Other prior art methods of knowing the topology when nodes first communicate asynchronously using random access technology are described by A. Bhatnagar in "Layer Net, New Self-Organizing Network Protocol", IEEE Military Communications Conference Minutes, Vol. .2, pp. 845-49 (1990) ("Layer Net:" Described in A New Self-Organizing Network Protocol, "IEEE Military Communication Conference Record". This technology requires some form of collision detection and does not provide bounded latency (maximum time to organize is unpredictable). ). Not necessarily fully utilizing the available node positions or distance measurement methods. Asynchronous mode requires many node receivers to be activated at the same time for long periods of time, increasing power consumption. This method Does not assume that the transmitter's interference distance is greater than its effective communication distance. If two nodes cannot communicate with each other, they need to be prevented from interfering with each other. Probably very much. The serious thing is that the layer net protocol does not always find all the possible links in the network topology.

【0012】

[Summary of Invention]

The present invention provides a more efficient topology knowledge procedure for wireless networks operating in a distributed self-organizing manner. This topology knowledge procedure is "distributed" in that it does not require a central controller and operates in a distributed manner that impacts only the affected areas of the network. The number of time slots required in a TDMA scheme to organize is less than in predecessor systems, and this number is not the total number of nodes in the network, but the maximum number of nodes (a node can connect). The number of nodes). The present invention is therefore fast and scalable, with no inherent restrictions on the size of the network. You can also add and remove nodes from your existing wireless network.

【0013】

The advantage of the present invention is that networks can be very efficiently self-organizing while saving power and time (or frequency) resources. That is, it is very advantageous for networks of low power wireless nodes where many of the nodes have a limited power source (battery or solar power, etc.). This network can be used, for example, for peripheral security, personnel detection and tracking, vehicle detection and tracking, or conditional monitoring and control of industrial processes. The "node" in these applications may be a detector equipped with a wireless transceiver for communication. The present invention can also be used in communication networks, where nodes are transceivers or repeaters.

【0014】

The present invention maximizes the space of a channel (generally a TDMA time slot) by identifying two sets of adjacent nodes, i.e. (1) a set of communicating neighbors and (2) a set of interfering neighbors, for each node. The purpose is to reuse it. A "communicating neighbor" for a given node n is any node within the reliable communication distance of n. An "interfering neighbor" for any given node n is any that transmissions from the "interfering neighbor" are within a (wider) distance that can interfere with the communication between n and its communicating neighbor. That node.

【0015】

The present invention is based on a hypothesized existing, well-located network of member nodes that is smaller than a generally organized network. Also, it is preferable that the maximum communication and maximum interference distances of all nodes are known approximately in advance (by direct measurement). The starting network can be a single node, but this method works better with a larger number of starting member nodes. One of the starting member nodes (the "send solicitation node") sends a solicitation to join the network to the new node (whose location is unknown). If the new node responds to the solicitation sent, the solicitation node calculates the area in which the new node should exist, based on the maximum known distances of both the solicitation node and the new node ( Within the distance of the solicitation node). Then it identifies the member node (whose location is known) within the range of the area where the new node should be. These member nodes are potential communication neighbors of the new node, but some of them may not actually be communication neighbors. This is because the new node is actually located in the identified area but is not exactly known, and the terrain or medium may be uneven or directional, affecting transmission in local areas. Because there is. It then identifies a set of possible member nodes (whose location is known) within the interference distance in a similar manner, based on the actual location of the new node.

【0016】

The solicitation node and the new node then determine the distance to each other by one of various distance measurement methods. The soliciting node uses this distance information to update the identification of the new node's set of communication and interfering neighbors.

【0017】

The soliciting node then determines a transmission schedule that allows the new node to more accurately determine its set of communication neighbors. This schedule allows the new node to send to each potential communication neighbor and each potential communication neighbor to send to the new node. After executing this schedule, the new node further limits the potential set of communication neighbors based on the results of the trial transmission. Distance measurement procedures with newly discovered communication neighbors allow new nodes to better calculate their location estimates.

【0018】

Once the location of the new node is determined (as much as possible), the new node's interfering neighbors can be better identified. The transmission schedule is expanded and executed to identify the interfering neighbors on this new node.

【0019】

Once the new node's communication neighbors and interfering neighbors are identified, the information that identifies both the neighbor and the new set of nodes is disseminated to at least locally affected nodes and incorporated into communication and routing schedules. This new node also informs the soliciting node about its features and traffic. That is, it tells you if you are a user node, if you have urgent data, or if you have other important information. The soliciting node also conveys this information to locally affected nodes. In this way, the complete topological impact of the new node on the network can be seen. The new node will be informed about local network traffic as well as routing and communication schedules. The new node can thus become a member of the network and issue solicitations to other new nodes. This entire process can be repeated until all nodes within the communication range of the nodes embedded in the network are embedded in the network and the topology is completely understood. Then, this information that characterizes the topology can be used to develop an efficient communication schedule for the network.

【0020】

The present invention is particularly advantageous for networks of distributed, on-node programmable, signal processing, very low power, wireless link nodes. Wireless integrated networks of sensors are possible applications. Low power, TDMA radio communication is an efficient communication method for such networks as it allows power savings with nodes off in some of the time slots. The topology information obtained by the present invention allows TDMA multi-hop transmission to be scheduled in a very efficient manner and requires little prior knowledge of the location of the nodes. It also has the advantage of being scalable and distributed. It can be run from any node and from multiple (outside the distance) nodes at the same time. In this way, it is elastic and can easily cope with damage and loss of some nodes.

【0021】

[Detailed explanation]

The present invention is a method and device for knowing the topology of a wireless communication network. Spatial reuse of channels provides the information needed to efficiently schedule multi-hop wireless communications.

【0022】

The present invention will be described in the context of a network of small electronic devices, each including a wireless transceiver, capable of transmitting, receiving and relaying data. Each of these small devices is hereafter referred to as a "node" and preferably includes sensors (s), control circuits, signal processors and RF transceivers. Also, these nodes most preferably include a device for determining the inter-node distance, which may include an ultrasonic transducer. Sensors can detect vibrations, seismic signals, infrared signals, magnetic signals, voice and other detectable physical phenomena. For convenience, radio is considered here as a general medium for communication, but other wireless media such as ultrasound, infrared or optics can also be used. A network of such nodes can be arranged in a variety of ways, including dropping from an aircraft or from a vehicle, and manually arranging them with personnel. The specification also assumes fixed carrier frequency radio channels that are modulated to convey information for convenience (although the method can be generalized to hopped frequencies or other communication channels). First, the method of the present invention will be described. The node device that can be used in the present invention will be described below.

【0023】

[Network self-organization]

For each deployed node, there is a maximum communication distance g at the area where the node is located and at a given power level. The communication distance g is preferably determined in advance by empirical testing. Similarly, it is preferred that the maximum interference distance b, at which transmission can interfere with other transmissions on the same channel, is also predetermined. Two sets of neighbor nodes can be specified for each node. That is, (1) a set of communication neighbors and (2) a set of interference neighbors. The "communication neighbor" of a given node n is any node capable of reliable communication with n. An "interfering neighbor" of a given node n is a node that cannot communicate with n with high reliability and whose transmission may interfere with communication between n and its communication neighbor. .. The goal of the present invention is to determine its communication and interfering neighbors "on a node-by-node" basis. This information is sufficient to fully define the network topology and to efficiently schedule communications organized in TDMA, FDMA, Code Division Multiple Access (CDMA) or other aspects. Topology can be thought of informally as defining "who can speak directly to whom" and "who cannot speak at the same time". More formally, the "topology" of a network can be defined as complete information that identifies communication and interfering neighbors for each node in the network.

【0024】

In one method of scheduling (TDMA), nodes that are members of the same network operate in synchronized periodic time frames. Each time frame is divided into a plurality of time slots having a shorter duration than each frame. Different nodes in the same area are scheduled to transmit in different allotted time slots. However, different nodes with completely non-overlapping interference regions can be scheduled to transmit (simultaneously) in the same time slot without data collisions. For power-limited applications, TDMA has advantages over random access. This is because power can be saved by turning off the transmitter and receiver during idle time slots.

【0025】

FIG. 1 is a diagram showing a communication neighbor node and an interference neighbor node. In the figure, nodes 200 and 300 are the transmitting side, and nodes 100 and 400 are the receiving side. For convenience of conceptual description and illustration, in FIG. 1, any node within the distance g is a communication neighbor, and any node between the distances g and b is an interference neighbor. If the receiving node is within the distance g of the transmitting node (circle 205 centered on 200 and 300 shown by the solid line), it can communicate well with the transmitting node. That is, the receiving node is the communication neighbor of the transmitting node. However, if the receiving node is farther than g and within the interference distance b of the transmitting node (dotted line 206 centered on 200 and 300), this is an "interference neighbor". In FIG. 1, node 200 is a communication neighbor of node 100, and node 300 is an interference neighbor of node 100. Node 400 is a communication neighbor of node 300, but node 400 is outside the interference distance of node 200. So, if nodes 200 and 300 transmit at the same time and nodes 100 and 400 receive, the transmission of node 300 is successfully received by node 400. The transmission of node 200 is not accurately received by node 100 due to interference from node 300.

【0026】

The relationship between the nodes is as shown in Fig. 2. Topology is represented by links in the graph. Communication neighbors are linked by a solid line 207. The interfering neighbors are linked by the dotted line 208.

【0027】

Of course, the region specified by the circles such as 205 and 206 above is an idealized estimate assuming an ideal region. The actual area generally contains fairly irregular obstacles such as rocks, hills, trees, and other terrain, and the actual range of interference and communication is irregular rather than circular (or spherical in 3D). It will be something like that. Nevertheless, idealized approximation (circular region) is a useful concept in that it, in some cases, represents the maximum region of communication or interference. These estimates are preferably predicted or measured prior to deploying the node to give approximate values of g and b for use in the methods of the invention.

【0028】

FIG. 3 is a larger example of a network having the topology shown by the dotted and solid lines in the same manner as in FIG. In some cases, the link can be unidirectional. That is, it is possible that 100 can hear 200, but 200 cannot hear 100, for example due to propagation effects or variability in the hardware. The topology knowledge procedure of the present invention is applicable even in such a case, and provides a method for obtaining the topology of the target link.

【0029】

For example, if you drop a node from an aircraft and deploy the network first, the nodes can be arranged approximately randomly. In the present invention, it is desirable that the relative positions of some nodes (at least one) be known first. This can be done in a variety of ways, including placing some nodes in known locations, installing location-finding devices such as the Global Positioning System (GPS) on some nodes, or visually exploring and discovering them. You can do it with certainty. The present invention can be used to add new nodes to an existing functioning system or to create a network from multiple separate, unorganized nodes. To best show all the steps of this method, it is convenient to first consider the invention in relation to adding nodes to an existing functioning network. Then, using the present invention, a special case of creating a network from pre-organized nodes can be easily described.

【0030】

To illustrate how to add nodes to a network using the present invention, here we organize to allow communication (with multi-hop relay, if necessary) between any two members of the network (member nodes). Assume a "start network", which is an existing communication network consisting of the nodes. The startup network may be organized by conventional methods or the present invention as follows. The most convenient case is when the startup network contains a node whose relative position is known first. It is preferred that each member node "knows" (remembers data about it) the relative location of all other member nodes within the maximum interference distance b. As described in more detail below, each node preferably includes a microprocessor capable of storing information, including location information. This information isIt can be pre-programmed or acquired during startup configuration and then distributed among the nodes via wireless communication. For startup networks such as those described above, the present invention provides a method of adding one or more new nodes to a network and knowing the resulting topology so that communications can be scheduled for the resulting larger network. To do. As part of the normal operation of the startup network, the network preferably has the ability to repeatedly request the addition of new nodes by sending solicitations. The solicitation for transmission is repeated to some extent periodically, and the cycle is p plus some pseudo-random delay (jitter). Jitter is added to prevent two accidentally synchronized nodes from repeatedly sending solicitations at the same time, thereby not missing each other's transmissions. This ensures that the new node receives the solicitation by receiving it for at least some intervals longer than p. All member nodes of the network may issue solicitations for new nodes on a somewhat periodic basis to join the network. It is convenient if interference is avoided because the member nodes in the distance range of g + b do not issue such solicitations at the same time. All non-member nodes that are not yet part of the network are pre-programmed and occasionally listen (turn on their receivers) for a few predetermined cycles of solicitation p. The new solicited node is then synchronized with the rest of the network to use the same specified TDMA time frame as the member nodes of the network used by the new node.

【0031】

When a member node ("Send Solicitation Node") issues a Send Solicitation to be received by the new node, the new node responds, which means that they are communication neighbors to both the Solicitation side and the new node. FIG. 4 shows a new node 210 that responds to a solicitation from a node 110 that invites transmission, and other member nodes (138 etc.) of the existing network are shown by connected small circles.

【0032】

Before sending a solicitation, the network schedules the communication so that there is no conflict. The schedule is preferably calculated by the solicitation node. Without knowing the exact location of the new node, the soliciting node 110 can set an outer boundary near the interference that may be affected by the new node. As shown in FIG. 5, this outer boundary is a circle 118 centered on 110 and has a radius of g + b, which can be explained as follows. That is, if the new node 210 receives and responds to the transmission solicitation, it should be found within the communication distance g of the transmission solicitation side 110. Therefore, 210 is somewhere in the circle 112 centered on 110 with radius g. The new node 210 is known to have an interference distance b. Therefore, the actual interference distance is a region within some circle of radius b centered on an unknown location within circle 112. The actual interference distance is generally irregular in shape based on the local signal propagation characteristics, but since b is the maximum interference distance, the region of some circle with radius b certainly includes the actual region. One such hypothetical circle centered on any point 211 on the outermost circumference of 112 is shown in Figure 5 at 116. Since it is not yet known which point on the circle 112 will be the actual position of the new node 210, it is not known which circle centered on the circle 112 contains the actual interference distance of the new node 210. Therefore, consider a combination of all circles. Here, the "potential interference distance" is defined as a combination of all possible regions bounded by a circle of radius b, centered somewhere within the circle 112. The combination of all the regions in the circle itself is a circular region with 118 as the boundary, with the transmission solicitation node 110 as the center and the radius g + b as shown in FIG. Outside this region, bounded by circle 118, there are no points that could be at the interference distance of any new node that can be received from node 110.

【0033】

Based on knowledge of b and g (preferably pre-determined and programmed into the node), calculations on the solicitation node preferably schedule communications and avoid conflicts in solicitation and response. .. An easy way to schedule is to schedule the solicitation and response so that none of the member nodes in circle 118 are scheduled to send or receive at the same time as the solicitation and expected response from the new node. Is enough. Alternatively, the schedule is configured to meet the following constraints: That is, (1) none of the nodes in the range of b + g of the soliciting node do not transmit during the solicitation of transmission, and (2) none of the nodes in the range of b of the soliciting node send. Do not receive during solicitation, (3) do not receive any node within the range of b + g on the solicitation side, and (4) do not receive during the response, and (4) do not receive during the solicitation of transmission. None of the nodes send during the response. In this alternative method, in some cases, the placement of the nodes may allow more nodes to communicate during the solicitation / response period.

【0034】

Similarly, the new node can have a "potential communication neighborhood" for the new node (depending on its actual location) only if the new node is within the communication distance g of the soliciting node. It can be defined as the maximum region of sex. The outer boundary of the potential communication neighborhood of this new node is calculated before the solicitation is sent (preferably by the solicitation node 110), as shown in FIG. Any new node that can receive and respond to the soliciting node is within the communication distance g (predetermined) of the soliciting node as shown by the circle 112 centered on 110 with a radius g. .. It is not known in advance exactly where the new node is in circle 112. Other member nodes that may communicate with the new node are within the distance g of the new node, i.e. within a circle of radius g centered on the location of the new node (unknown). In order to obtain the broadcastable area that the new node may communicate with without accurate knowledge of the location of the new node, here the area within all circles of radius g for all possible locations of the new node. Can be combined. It is a combination of all circle regions centered on or within circle 112. When the insides of these circles are combined, a set of points in the circle 114 having a radius of 2 g and centered on the transmission soliciting node 110 is obtained. No matter where the new node is within the circle 112, it will not be able to communicate with the member nodes outside the circle 114 resulting from a radius of 2g centered on 110.

【0035】

The new node may potentially be able to communicate with some of the nodes in circle 114 if it is in the right place, but generally its actual (not yet determined) location and specific locality. Propagation characteristics do not allow communication with all of them. For example, in FIG. 6, the new node 210 is not actually in the communication distance of the member node 136, but since the location of 210 is not known in advance, this cannot be predicted. That is, some of the points on or in circle 112 are very close to 136. The area within circle 114 in FIG. 6 is thus identified (by calculation for the node) as the "potential communication distance" of the new node 210, rather than the actual communication distance.

【0036】

Once the potential communication neighborhood and potential interference neighborhood of the new node are identified, the first solicitation is sent according to an appropriate schedule. In the TDMA communication system, this occurs in a time slot where the solicitation is sent from the soliciting node 110 and the response from the new node is not received by any of the other member nodes in circle 118. It can be said that it means that it has become like this.

【0037】

When a new node is detected, the soliciting node and the new node determine the distance d between each other using the distance measurement capability, if available. The distance between the nodes can be determined by various prior art methods such as measuring the travel time of sound h waves, ultrasonic waves, or RF pulses, or comparing the RF received signal strength with the transmitted signal strength. Skolnik, Merril I., Radar Handbook, McGlowhill (1990), Section 17.4 (Radar Handbook,) As described in Mcgraw Hill), various means for performing distance measurement by radar echo processing of RF pulses, such as a plurality of discrete PRF pulse (pulse repetition frequency) distance measurement, are known. These RF pulse methods are suitable for high clock speeds and sufficiently high RF frequencies to make accurate measurements at short time intervals that match the minimum distance to be measured. Another method of ranging distance measurement, timing sound waves or ultrasonic pulses, is better suited for low clock speeds and low RF frequency operation, resulting in lower power and lower frequency (less than 1 Ghz) circuits. More appropriate. An example of realizing a distance measuring method using sound waves or ultrasonic waves will be described below in relation to the description of the node hardware. In some embodiments, the location of each node may be known, for example, by a Global Positioning System (GPS) device installed on the node. In that case, the distance can be easily calculated from the known position. Regardless of how it is obtained, ranging information greatly enhances the topology knowledge process of the present invention.

【0038】

FIG. 7 shows the results of distance measurement between the new node 210 and the transmission solicitation node 110 in the same network example shown in FIGS. 3 to 6. FIG. 7 also shows the new node 210 with its potential communication neighborhood 114 and potential interference neighborhood 118, both of which are centered on the soliciting node 110. After measuring the distance g, the soliciting node 110 can determine that the new node is on the circle 120 and is centered on the sending node 110 with a radius d. The new node 210 can determine that the transmitting node is on a circle 122 with a radius d and is centered on the new node 210.

【0039】

After determining d, the soliciting node modifies the calculation of the new node 210 potential communication neighborhood and potential interference neighborhood shown in FIG. The new node 210 has a distance g and its communication neighborhood is known to be within the region of a circle with a radius g, but the center of the circle may be somewhere on the circle 120. Despite this uncertainty, it is still possible to define the outer boundaries of the potential communication neighborhood. The potential communication neighborhood is the union of all regions centered on 120 and bounded by multiple circles of radius g, within circle 124 of radius d + g, and soliciting node 110. Focusing on. Depending on its actual position on circle 120, the new node 210 may be able to communicate with any node in g from any point on circle 120. That is, it will only be able to actually communicate with nodes within one such circle centered on the actual location of the new node 210 (and only with nodes that are not blocked by the local signal propagation effect of the region). ..

【0040】

Distance measurement information d was used to limit the area in which the new node may have communication neighbors for the area within circle 124. Since d is less than or equal to g, this will not be larger than the previously predicted region of 114 (radius 2 g). By comparing this area within circle 124 with the (known) location of member nodes, the set of potential communication neighbors for the new node 210 can be narrowed down by excluding nodes outside circle 124. .. In the subsequent example shown in FIG. 8 and earlier, it can be seen that the three member nodes 126, 128 and 130 are outside the potential communication neighborhood of the new node 210, which is bounded by the circle 124.

【0041】

Similarly, the transmission solicitation node can use the distance measurement information d to limit the area where interference is possible to the area within the circle 119 centered on 110 and having a radius d + b as shown in FIG. ..

【0042】

Next, the soliciting node determines the schedule on which the new node 210 can determine its communication neighbor. It schedules and executes transmissions from each member node in a set of (narrowed down) potential communication neighbors (and new nodes are scheduled to receive) and / or (filtered out). This is done by scheduling transmissions from new nodes while scheduling all nodes in the (contained) potential communication neighbor set to receive. If the network topology is directionally asymmetric, both schedules are needed. It is possible that some transmissions will not be received, in which case the intended member node is outside the actual communication neighborhood of the new node 210. In this example, transmissions from member nodes 132, 134, 136, 138, 140, 142 and 144 within circle 124 will be scheduled with the new node 210. In this example, transmissions from member nodes 126, 128, and 130 determined to be outside circle 124 do not need to be scheduled.

【0043】

If distance measurement is unsuccessful or impossible, as in the example without ranging capability, the soliciting node is centered on the soliciting node 110 and has a radius of 2 g (larger) circle 114. Communication probe procedures can be scheduled for all nodes within. This was a preliminary estimate of the potential communication area, as explained above. In this case, more transmissions may be required, but this method does not have to involve all member nodes of the network.

【0044】

Note that power and time (or bandwidth) are saved by first narrowing down the set of potential communication neighbors, so each step sends to / from all member nodes, or 2g of soliciting node 110. It was not necessary to schedule even transmissions from / to all member nodes in the range of. Since there are few nodes involved, the number of scheduled transmissions is also small, which saves power. Depending on the algorithm used for the communication schedule, transmissions from the new node to multiple member nodes can occur in multiple time slots, with each intended receiving member node between its respective assigned slots. Only set to receive. In such a schedule, transmissions to multiple receiving member nodes actually require multiple transmissions, and the greater the number of intended receiving nodes, the greater the energy and time required. Even if the scheduling algorithm allows a single transmission from the new node to multiple receiving member nodes, the intended receiving node must each report the result of the attempted transmission to the soliciting node 110. Must be. To report, you need to send at least once for each node you report. In this way, power and time can be saved by keeping the number of nodes involved low. Power and time can also be saved by scheduling a small number of test transmissions from the member node to the new node. In a hardware implementation, the receiver can also save extra power by turning it off during unscheduled time slots. At every step in this method, the sending node 110 calculates the neighborhood and identifies a restricted set of member nodes before scheduling the transmission and, if possible, narrowing down the number of transmissions required. Power is saved by taking advantage of the fact that the power required for the calculation is less than the power required for wireless communication.

【0045】

The transmission schedule is distributed to the associated member nodes and then executed, and the result is stored by the microprocessor for each associated member node. Now you know exactly the set of member nodes that are the communication neighbors of the new node 210. In the example shown in FIG. 9, the new node discovers only the other two communication nodes 132 and 144 in addition to the solicitation node 110. The communication neighbor should actually be within a circle 146 with a radius g centered on the new node 210. This is because g is the maximum communication distance of node 210.

【0046】

Once the new node determines its set of communication neighbors, its absolute position calculation can be revised. In essence, in a 2D network, if a communication neighbor is found other than the soliciting node, the location of the new node is on a circle (or sphere in a 3D network) with a radius of d from the soliciting node. Only determined. If one other communication neighbor is discovered, distance measurement is performed on this additional communication neighbor, and the location of the new node is one of two points on the surface (or a circle in the case of 3D space). ) Is determined. This state is shown in FIG. After distance measurement on the member node 144 and the soliciting node 110, 210 is on a circle 122 with a center on 110 and a radius d, and on another circle 148 with a radius d on the member node 144. It turns out that there is. This information limits the possible locations of the new node to the two intersections of circles 122 and 148. It is at 210 locations (its actual exact location) or at the other intersection 212 of circles 148 and 122. A third node, eg 132, determines the location to one of the actual locations of the new node 210 (except in special cases where member nodes 132 and 144 and the soliciting node 110 are on the same line). On the surface, as is well known to navigators, measuring distances at three points on non-identical lines is sufficient to determine a single location. Knowledge of connectivity is also used to help determine location. However, radio propagation is non-uniform and can complicate the problem.

【0047】

Once the location of the new node 210 is further determined, the new set of interfering neighbor member nodes should be limited by comparing the known location of the member node with the improved approximate value of the location of the new node. Can be done. The calculation of comparing the location of the member node to the interference neighborhood of the new node 210 can be performed by the microprocessor in either the new node 210 or the soliciting node, and the resulting information is used to calculate the interference neighbor of the new node 210. Can calculate an improved communication schedule that does not send at the same time as the new node 210. This limitation is shown in FIG. 11, where the step of measuring distance at node 132 is a more general case where the position of the new node is not known exactly, but it is narrowed down to two candidate points. Is omitted for a better explanation. The interfering neighbors are in the range of two circles 150 (centered on the possible new node location 210 with radius b) and 152 (centered on the other possible new node location 212 with radius b). There should be.

【0048】

The schedule is then expanded to further limit the set of member nodes that are the interfering neighbors of the new node 210. If the location of the new node is not known exactly, the area where interference is possible is not completely limited to a circle with radius b (Circle 150 in the example in Figure 11). Even if you do not know exactly where the new node is, the terrain effects can be adjusted so that the interference neighborhood cannot be the same as the calculated one. Various methods can be used to identify the actual interference neighborhood. For example, each member node in the vicinity of potential interference and known communication neighbors can transmit at the same time, and the new node can determine whether the communication neighbor's transmission can be received with high reliability. These operations can be conveniently controlled from the microprocessor of the soliciting node, and instructions are relayed over the network to the associated member nodes. Another method is to use physical measurements at the receiver of the new node to determine the interference level, such as by measuring the received signal strength of scheduled transmissions from each member node in the vicinity of potential interference. Is what you do. Alternatively, the soliciting node can send a test message to each potential interfering member neighbor at a higher power level than usual to characterize the situation. With either method, the set of potential interfering nodes is pre-limited at multiple stages, requiring less transmission and energy compared to simply transmitting to / from all member nodes. The advantage of the present invention is that it consumes less. Moreover, the technology is scalable, and no matter how many nodes are in the network, given the maximum spatial density, the time and effort to incorporate new nodes is limited.

【0049】

Figure 11 shows that after running the interference probing schedule in this example, the new nodes 210 interfere with only seven (out of the nine that were possible before probing) in a circle 150 centered on node 210, all with radius b. The case of discovering that it does not have a neighbor is shown. The interfering neighbors found are 134, 136, 138, 140, 142, 126 and 144.

【0050】

Now that the topology of the new node 210 is fully understood, the effect that the new node has on the network is calculated and distributed and incorporated into the network communication schedule protocol. The new node can communicate with any of its communication neighbors, but cannot receive at the same time while the interfering neighbor (not the communication neighbor) is transmitting. The new node cannot receive at the same time while the interfering neighbor (not the communication neighbor) is transmitting. Also, the new node will allow interference neighbors (not communication neighbors) to receive (assuming media transmission / reception symmetry, otherwise probing will have to go bidirectionally to completely determine the interference topology). Cannot send at the same time while doing. This information allows transmission to be scheduled for multi-hop communication over the network, preferably in the TDMA protocol. TDMA is advantageous in low power networks because it saves energy by allowing inactive transmitters and receivers to be temporarily turned off in a given time slot. Nodes can still employ spread spectrum or frequency hopping techniques in their TDMA time slots, and it is desirable to employ such techniques as well.

【0051】

After the tropological effects of the new node are known, the information obtained (new node ID, location and communication and interfering neighbors) is distributed to the network, at least to the extent necessary to schedule communication. A network communication protocol, controlled by individual pre-programmed microprocessors on a node, is that information is routinely routed within the network and goes to a user interface node (a node accessible to the user for data output or input). Information about the appropriate topology needs to be distributed so that it can be directed from /. Similarly, the new node receives routing and other information from the network and stores that information in its microprocessor. The new node 210 is now a member node of the network. This node can now solicit transmissions to other new nodes that are willing to join. The characterization method of the new node is repeated from each member no and for each new node. Network organization propagates outward from the startup network in a decentralized manner that organizes a complete network. Even after the complete network has been configured, solicitations will continue to be issued and can be added if there are new nodes provided later (eg, by user behavior).

【0052】

Unless otherwise noted in the above description, the present invention is considered to be related to a two-dimensional network, assuming that all of the nodes are on the surface. However, the present invention is not limited to nodes on the surface. In a three-dimensional network, the same procedure can be applied because the communication distance and the interference distance define the area in three spaces. Moreover, the method of this case is not limited to the one used together with the omnidirectional antenna. In a network with directional antennas, the various regions considered are irregular regions in plane (2D) or 3 space (3D). The methods of the invention are essentially the same, except that the irregular geometry complicates the calculations.

【0053】

When FIGS. 12 to 15 are combined, a flowchart is formed from the top of FIG. 12 to the end of FIG. 15, showing detailed steps of the present invention. Since the method is decentralized, i.e. the task is done on multiple nodes at the same time, the chart will be read in three columns representing the actions that occur on the new node, the soliciting node, and the other active member nodes. ing.

【0054】

The flow chart begins with the new node powering on (220). After powering on, the new node begins a pre-programmed initialization process that includes a built-in test and built-in calibration program (222). After initialization, the new node asks if there is a solicitation to send to the network (224). If no solicitation is received after listening for one full cycle, the new node enters solicitation node mode, assuming it is the first node in the network. This is indicated by the route to the solicitation mode column.

【0055】

If the solicitation node issues a solicitation (226), the new node responds when it receives it (228). The soliciting node receives the response from the new node (230) and is in pairs between the new node and its potential communication neighbor member nodes so that the new node can know its communication and interference topology. Move on to communication scheduling. The pair-based communication schedule is preferably assigned to each node pair (link between two nodes) of a specific time slot in a TDMA time frame, but includes FDMA as described above. Other types of organizations are also possible.

【0056】

Upon receiving the per-pair communication schedule (232), the new node undergoes an active process of exchange, negotiation and initiation (232). These activation processes may include high priority invalidation instructions or data from the user such as "power down for 5 minutes", "all sensors to maximum alert activity". Emergency orders to this type of network should be followed immediately before completing the topology knowledge method. This allows the user to send a "bottled message" into the network, for example by launching a new node into the network with an artillery or by dropping it from an aircraft. The initiated activation process may include more normal functions, such as initiating the detection of earthquakes in the environment and activities that can be detected by other sensors.

【0057】

On the other hand, other member nodes also receive the communication schedule (234). The soliciting node and other active nodes will initiate a similar active process (236). The new node and the transmission start node measure the distance between the nodes there (238). When the distance is measured, the soliciting node generates a new communication schedule based on the set of potential communication neighbors within the measured area, as described above (240). The new node and the other member nodes receive the new communication schedule in steps (242 and 244). After generating a general communication schedule, the soliciting node has a specific schedule of transmissions to be performed between the new node and other active nodes in order to know the communication topology changed by the addition of the new node. Occurs (246) and sends the same schedule. The new node and other active nodes receive the communication topology knowledge schedule (248 and 250) and execute the transmission schedule (252).

【0058】

After knowing the communication topology (the set of communication neighbors of the new node), the new node sends the information to the soliciting node (254). When the transmission solicitation node receives the communication topology information (256), it generates a new communication schedule near the communication and interference of the new node (258), and transmits the new schedule. The schedule is received by the new node and other member nodes (262) (260). The soliciting node generates a schedule to find the location of the new node (264) and informs the new node and other member nodes (268) about this schedule (266). As mentioned earlier, this also includes performing distance measurements with one or more neighbors (270) to find new nodes. The location of the new node is calculated by the new node (272) and notified to the soliciting node. Upon receiving this information, the soliciting node generates another communication schedule to know the interference topology (the set of nodes in the vicinity of the interference of the new node) (274). When the new node and other member nodes receive this communication schedule (276), they move on to implement the schedule (278) and know the interference topology. Knowing the interference topology, the new node informs the soliciting node (280), and the new node reschedules communications in the light of new and more accurate interference topology information (282). The soliciting node makes a transmission, and the new node and other member nodes receive this new schedule (284).

【0059】

Finally, the new node tests itself (286) to determine if a "sink" is attached and informs the soliciting node. A "sink" is an output port or node through which information is communicated to the user. It can even be a node hand carried by the user. These are important points when a user interfaces with a network. In some applications, it may be useful to perform a sink test, step 286, prior to the early stages of the method, eg communication schedule / activation process step 232. This is because users may have a high priority for the use of network data. Users may want to quickly tap the network for information without disturbing the topology. In that case, all remaining procedures may be omitted or delayed.

【0060】

When the microprocessor on the soliciting node receives the sink information (288), it calculates the end-to-end circuit requirements of the network and finds an overall communication schedule that meets these requirements. The new node and other active nodes receive this new schedule and routing information (290). Upon receiving the complete routing information and schedule for communication within the network, the new node becomes a member of the network and repeats the entire flowchart from each node as a soliciting node in the network until no new node is detected.

【0061】

Figure 16 shows an example of a TDMA frame that can be used to schedule communication between nodes. Communication is organized into time slots 310a, b, etc. within the repeating time frame 312. The illustrated frame is considered from the viewpoint of a specific node, node i. There are several types of time slots allocated. Network entry slot 314, node i broadcast slot 316 for simultaneous broadcasting to multiple neighbors, slot 318 for inter-node communication between node i and its neighbors (i to j and j to i respectively) One slot in the direction), slot 320 (interfering neighbor slot) that is allocated for use on other nodes and not available on node i, and slot 322 that is specially allocated for temporary priority needs. All of the remaining bandwidth (slot 324) allocated according to. Although only one of many suitable methods of allocating time slots, in the example shown in FIG. 16, network entry slot 314 has special importance for network self-organization and topology knowledge. These slots consist of a solicitation slot 310a, a response slot 310b, and a pointer slot 310c. The solicitation node broadcasts the solicitation in the solicitation slot 310a (step 226 in FIG. 12 as described above), and the new node responds in the response slot 310b (step 228 in FIG. 12). And receive a pointer from the soliciting node in pointer slot 310c, which indicates the correct slot assigned for further communication to the new node (step 232 in Figure 12).

【0062】

In addition to adding nodes to an existing network, the present invention can be used to create an initial network from multiple unorganized nodes. This may be the "startup network" assumed in the above description of the present invention. Network creation begins with multiple nodes deployed in either power down or in a timed inactive mode. When the user manually turns on the node or the timed inactivity period ends, one of the nodes powers up and enters active mode. This method can be summarized as follows according to flowcharts 12-15 above. That is, upon initiating the active mode, the node can perform initial startup procedures (connecting to users, checking built-in self-tests, starting counters to measure usage, etc.). The node then enters listening mode, activates the receiver, and asks for invitations to join the existing network. After listening for some time longer than the maximum solicitation period, if there is no solicitation, the node assumes that it is the first (first) node. Following pre-programming, prepare a TDMA schedule that allocates time slots for solicitation and at least 2 slots for bidirectional communication with the expected new node. Then the first node issues a solicitation to send.

【0063】

If no response is received, the first (solicitation) node reverts to inactive mode and can be heard again after some interval, preferably with some pseudo-random "jitter". Jitter prevents unnecessary synchronization conditions in which two or more nodes relentlessly issue simultaneous solicitations that interfere with each other and miss each other's solicitations. If no new node is detected, the first node can issue the solicitation again and the process is repeated.

【0064】

Eventually, the nodes will be deployed to configure the network, and the new node will receive and respond to the first soliciting node. The solicitation and response initiates the method described above and shown in FIGS. 2-15. This method is essentially the same except that some steps are trivial if there are only two nodes. That is, there is no other member node that schedules for transmission and reception. The transmission solicitation node 110 can perform distance measurement at the new node. The exact location of the new node cannot be determined at this point in the network deployment. Potential communications and interference neighborhoods are calculated as in the examples given above, but they cannot be narrowed down. In this way, both the first and second nodes can iteratively find a third node and add it to the network. You can finally fully deploy a multi-node network, but you can't calculate the exact relative location for a node until you have a sufficient number of known locations, so there are more to know the topology. Is required to be sent. Alternatively, the relative location can be calculated when a sufficient number of nodes with overlapping communication distances are incorporated (eg by trigonometry). Even if the position cannot be calculated, in some applications the topology itself may be useful and no position information may be needed. For example, a wireless network may be useful for detecting the presence of an intruder without knowing the exact location of the intrusion. In a topologically organized network, it may be sufficient to relay an intruder alert to the user, even without location information.

【0065】

This method can be used with nodes that have adjustable transmitter and receiver power. Nodes can be programmed to adjust to a finite number of discrete power levels. The topology knowledge sequence can be performed separately for each of the individual levels in the sequence. To reduce power consumption, it is preferable to run this sequence first at a lower power level.

【0066】

One special situation that needs to be considered is when two new nodes respond to soliciting nodes at the same time. In this case, the soliciting node and the new node detect that a conflict has occurred and use appropriate random access or prioritized technology to schedule retransmissions from the new node. ALOHA technology described by Norman Abramson in "The Throughput of Packet Broadcasting Channels," IEEE Transactions on Communications, Vol.Com-25, No. 1, Jan. 1977. Various conventional techniques such as, etc. can be used. Alternatively, nodes can be prioritized for retransmissions based on their own assigned ID number. Know the topology obtained by adding the first new node using the method of FIGS. 12 to 15, and know the topology obtained by adding the second new node again.

【0067】

[Node device]

A. General Since the present invention is specifically designed to launch and utilize a low power, integrated network containing a large number of sensors, it is preferably used in a network of micropower, wireless integrated sensors. Such networks are made possible by providing nodes that are highly integrated, miniaturized, have short communication distances, are flexibly programmable, and have a low cost per node.

【0068】

Figure 17 shows one possible implementation of a single device or node that may be deployed in an area. This node contains a functional component (indicated by a virtual line) including circuit 2 and an enclosure 1 to house the power supply (battery) 3 and provide environmental protection. An antenna 4 for transmitting and receiving wireless signals is mounted on the enclosure 1. The antenna 4 is shown as a vertical dipole with an artificial ground plate, but other configurations may be used, including an isometric antenna loop or even an integrated antenna element. The outer shape of the node housing 1 can be changed to almost any shape depending on the application. The dimensions of housing 1 are variable and the minimum size is limited only by the degree of integration and miniaturization of circuit 2 and power supply 3. The illustrated node also includes a sonic or ultrasonic transducer 6 for producing audio pulses as shown. This transducer is generally optional, but in some embodiments it exists as part of a mechanism that acoustically measures the distance from adjacent nodes, as described in more detail below. In many applications where an acoustic or ultrasonic transducer 6 is used for distance measurement, it is advantageous to use a transducer that can spread the sound widely or in almost all directions and can measure distance in many directions.

【0069】

Figure 18 shows the architecture for individual nodes. Local environmental conditions or changes (including seismic, ultrasonic, sonic or electromagnetic signals) are detected by the sensor or sensor array 12. In the typical case where a sensor (s) generate an analog signal (s), an analog-to-digital converter (ADC) 14 is provided to digitize the data from the sensor. The data is stored in the buffer memory 16 for processing. The digital signal processor (DSP) 18 preferably filters and analyzes the stored data to improve the signal-to-noise ratio and extract information about the amplitude and spectral characteristics of the sensor data. After filtering, DSP18 compares this feature with a user-programmed profile and gives the comparison result to microprocessor 20. The microprocessor 20 makes a decision based on this information from the DSP 18. For example, if a low frequency signal indicating a vehicle is detected, the wireless transformer 22 may be alerted. The microprocessor 20 can perform further signal processing and analysis of the data if desired (eg, decision analysis or target classification) or can reconfigure the DSP 18 to more closely examine a particular spectral band. In addition, the microprocessor 20 can be programmed to control and schedule communications with other nodes and / or users, or a second microprocessor can be provided to control the wireless transceiver 22 for these functions. It can be performed. The microprocessor 20 also preferably controls the signal generator 44, thereby driving an amplifier 46 that feeds an acoustic or ultrasonic transducer 6 when a distance measuring function is required.

【0070】

Many of the node's functions, including signal processing, judgment, ranging and communication management, can be performed by separate dedicated microprocessors. The present invention includes an embodiment having a plurality of microprocessors, but for the sake of brevity, only one microprocessor having various functions is shown in the drawings.

【0071】

The wireless transducer 22 controlled by the microprocessor 20 communicates with the network 32 and the user (s) 34 of other nodes. Communication is bidirectional, allowing data (spatial and time domain) or instructions to be transmitted, received or relayed. The received data or instructions can be stored by the microprocessor 20 and used to modify the programming of either the microprocessor 20 or the DSP 18. Transceivers with low power consumption levels are preferred because the present invention is preferably used in networks consisting of a large number of nodes with limited power (ie, generally batteries or solar cells).

【0072】

In a preferred embodiment, the subsections of some components of the node (sensor 12, ADC14, DSP18, microprocessor 20, signal generator 44, amplifier 46, received signal strength indicator 48 and wireless transceiver 22) are all. It is fully integrated on the chip 24 powered by the power supply 3 and housed in the enclosure 1. Such integration enables low cost manufacturing and extremely small packaging. However, the degree of integration can be increased or decreased, and the resulting node can also be used with the present invention.

【0073】

The detailed operation and structure of each node subsection will be described individually, but the sensor 12 will be the starting point.

【0074】

B. Sensor 12 Sensor systems need to identify signals in the presence of noise in the environment. All source signals (earthquakes, infrared, heat, light, acoustics, machinery, etc.) rapidly decay in amplitude as they move away from their source. In order to increase the detection distance, the sensitivity of the sensor must be increased. Also, due to the basic limitation of background noise, every sensor has a maximum detection distance. Therefore, it may be desirable to utilize a small sensor that has maximum sensitivity and can be distributed more widely and densely. Also, in some applications, it is desirable to integrate multiple sensors (with variable features) with the signal processing, control, and wireless transceiver portion of the node to increase the information available from that node.

【0075】

The integration of the sensor with other electronic components is preferably done by prior art "flip chip" bonding. In the "flip chip" process, a sensor die and a CMOS interface die are manufactured respectively. The CMOS interface die is then flipped and coupled to the sensor die, which generally includes a bulk macromachined sensor structure. This process allows for modular processing. That is, the manufacturing of sensor dies (with materials that are incompatible with CMOS processing) is separated from the manufacturing of CMOS. Thus, high performance piezoelectric and pyroelectric actuator and sensor materials can be integrated into CMOS measurement and control systems without interfering with CMOS manufacturing.

【0076】

A general sensor that can be used in the present invention is disclosed in Japanese Patent No. 5,659,195 of William J. Kaiser. The patent discloses, for example, a CMOS integrated micro-vibration accelerometer that can be used as a seismograph or vibration sensor. Integrated microacoustic sensors and thermoelectric sensors are also disclosed by the patent. Another thermal infrared sensor suitable for use with the present invention is David T. Chang's "Micropower High-Detectivity Infrared Sensor System," Solid State Sensor and Actuator Workshop (Technical). Digest), TRF cat. No. 98TRF-001, Lib. Of Congress no. 98-60214, ISBN no.0-9640024-2-6) The high-sensitivity thin-film radiation thermopile sensor described on pages 205 to 208 (1998). Such devices are well suited for large-scale integration with other components of the nodes of the invention, but together with geophones, acoustic detectors, thermal sensors, opto-electrical detectors or even mechanical transducers or It can be used as a substitute for integrated sensors.

【0077】

In one embodiment of the invention, a prior art microphone is included in the sensor array 12 as an acoustic sensor, in addition to the other sensors included. Microphones are used in the ranging process to detect acoustic or ultrasonic pulses as described below (range measuring device).

【0078】

C.ADC14 In a typical embodiment of the invention shown in FIG. 3, the sensor produces an analog signal output. On top of that, it is necessary to provide ADC14 to convert the sensor output to digital format and process it. The Σ-Δ architecture provides low power and low noise operation and is suitable for use with the ADCs of the present invention. The low power limitation makes it difficult to use flash, pipeline and sequential approximation architectures, but if there is sufficient bandwidth and resolution for the sensor data of interest, and even ADC power consumption, the available power and power life The ADC architecture can be used if it does not conflict with the requirements.

【0079】

C.DSP While improving the signal-to-noise ratio of the signal within the spectral region of interest, it is preferable to provide a DSP to analyze the amplitude and spectral characteristics of the signal obtained by the sensor. The DSP then compares the amplitude and spectral characteristics of the signal with the reference spectral profile stored or communicated from the network. Comparison results, spectral data, and raw signal data will be available to microprocessor 20. If multiple sensors are provided on top of the node to extract clues about the ID, number, size, distance and direction of the signal source (s), this data will be collected by microprocessor 20 from other sensors. Can be combined with the data of.

【0080】

It is preferable that the DSP is realized with an emphasis on low power consumption. Low signal processing speeds can be tolerated if they allow low power continuous operation. This is because the bandwidth of a general sensor system is low, for example, in the case of a seismic vibrometer, it is about 100 Hz. Dedicated equipment can be used, such as either a spectrum analyzer or a widely available and commercially available Fast Fourier Transform (FFT) chip. Alternatively, the data can be processed by the microprocessor 20 under software control, in which case the microprocessor 20 also serves as the DSP 18.

【0081】

By comparing the analyzed spectrum to the reference profile, a method of identifying the output source of the sensor signal is provided. For example, a large heavy vehicle with a pronounced spectral signature can be distinguished from other types of signal sources by reference to a programmed frequency profile.

【0082】

D. microprocessor 20 The microprocessor 20 provides essential control, logic and programming functions for the node. In addition to making decisions based on sensor data, communication scheduling, network topology knowledge, routing table management and updating, distance calculation for neighbor nodes or targets, data storage, and node-to-node, to user 34 / Handles multiple tasks, including relaying communications from.

【0083】

As mentioned earlier, all of the features involved in communication scheduling and topology knowledge are controlled by (at least one) node microprocessor. The microprocessor at each member node can store, for example, a matrix showing other network member nodes, their location, their connecting communication links, and the time slots scheduled for transmission and reception.

【0084】

The microprocessor 20 may be any of several commonly available microprocessors, but it is preferred to choose for low power and flexible power management capabilities, low cost and sufficient processing power. For example, candidates include AMD "18ER" available from Advanced Micro Devices or low-power "80186" family processors from Intel. The microprocessor preferably can operate temporarily in a low-power "sleep" mode, from which it can be "awakened" by an interrupt (eg, detection of a signal of interest occurs). A special purpose processor can be used. In this case, the design should focus on the ability to use duty cycles with low power and use of "sleep" mode. When "wake up" from "sleep" mode by detecting a signal, the microprocessor checks for other spectral signatures, whether to increase data acquisition, while giving warnings about signal decisions and other nodes. Make decisions about the appropriate course of action. The microprocessor preferably also has the ability to schedule and control RF communications and activate / disable RF and other circuits, depending on the circumstances. In some applications, the microprocessor can routinely send spectral density information from DSP 18 and / or buffered time domain sensor data to the RF transceiver 22 to the network. The microprocessor 20 also controls the upload of coefficients for the DSP 18 and can dynamically reconfigure the DSP in response to conditions, data, received instructions or programming. For example, the microprocessor 20 uploads coefficients from memory 21 (generally on-chip memory integrated with the microprocessor) to DSP18 to narrow or widen the spectral region of interest, or move the center frequency (by changing the coefficients). , Or the signal and ratio You can load a new threshold profile to compare. This allows a node to collaborate with other nodes in collaborative tasks or data acquisition, or to modify its data processing based on the current characteristics of sensor data.

【0085】

E. Wireless Transceiver 22 In a preferred embodiment, the wireless transceiver 22 provides bidirectional RF communication between a node and another node or user under the control of microprocessor 20 to provide data, decision, programming or routine network protocol management information. To communicate. The transceiver is preferably capable of taking a low power consumption "off" mode when not needed in the time slot, allowing power to be saved in the TDMA communication scheme.

【0086】

As shown in FIG. 19, the transceiver 22 preferably includes a transmitter 86 and a receiver 87 that share an antenna 4, a power source 3 (generally a battery). Transmitter 86 and receiver 87 are activated / disabled by enable signals 88 and 89 from microprocessor 20, respectively. A universal asynchronous receiver / transmitter (UART) controller 90 (eg, the MAX3243CAI chip available from Maxim) handles the data transfer between receiver 87, transmitter 86 and microprocessor 20. The receiver design preferably has less noise and higher selectivity while maintaining low power requirements. In some protocols, the receiver needs to be able to operate for some period of time with a high duty cycle so that each node can catch the randomly arriving signal.

【0087】

Conventionally highly integrated transceivers suitable for use in the present invention are available. For example, commonly available chipsets include Rockwell Digital Cordless Telephone (DCT) chipsets based on R900DCTM-4 or R900DCTM-3 transceiver modules. These highly integrated transceiver integrated circuits (ICs) are suitable for operation in the 902 to 928 MHz band and, with the appropriate accompanying chips available from the same manufacturer, Digital Diffusion Spectrum (DSS). Operation is also possible. Other available ICs suitable for use in the present invention include the RX2010 receiver and HX2000 or AT1000 transmitter, all manufactured by RF Monolithic, Inc. Whichever RFIC is used, it is preferable to select it based on its small size, low downtime, peak power consumption, and short on / off time. Most preferably, the transceiver electronic components are integrated with sensors, microprocessors and signal processing electronic components.

【0088】

In some embodiments, a received signal strength indicator (RSSI) 92 (shown in FIG. 18) is provided to measure the received signal strength of the RF signal and provide that information to the microprocessor 20. The received signal strength information is useful in connection with the network self-organizing method in some embodiments of the present invention, as described above.

【0089】

Although the present invention has been described in the context of a wireless communication wireless node, the medium of communication may be other wireless medium, including infrared waves, light waves, sound waves, microwaves or ultrasonic waves. It is assumed that all the various means of modulation are also available and within the scope of the present invention.

【0090】

The power output and receiver sensitivity of the transceivers described above may be variable in some embodiments or programmable under the control of a microprocessor.

【0091】

F. ranging component In some embodiments, the node is capable of measuring distance from other nodes, facilitating the self-organization of the network. In one such embodiment, the microprocessor 20 controls the signal generator 44. When activated by the microprocessor 20, the signal generator produces a signal of either audible or ultrasonic frequency. Lower frequencies are preferred for applications that require better sound wave dispersion. Higher frequencies are preferred for very small networks or conversion applications (inaudible sounds are better). The signal generator 44 drives an amplifier 46, which drives an acoustic or ultrasonic transducer 6 to generate voice pulses.

【0092】

FIG. 20 is a flow diagram of an operation for measuring a distance by a method of timing a sound wave or an ultrasonic pulse. Suppose two nodes, node A and node B, measure the distance to each other. All operations on a node are most conveniently controlled by a programmed microprocessor 20 that resides on the node itself. To measure the distance between node A and node B, both nodes first agree to establish a wireless contact and initiate distance measurement (step 330). Node A then establishes control and sends an RF signal to put Node B in standby mode (step 332). In response, Node B waits for the expected RF trigger command (step 334). When B enters this mode, there is no delay caused by other processes. Then, in step 336, node A sends an RF trigger command and simultaneously starts a timer, and the microphone or sensor 12 detects an acoustic (or ultrasonic) pulse. The timer may be a simple software loop that checks to see if a signal has been received, otherwise it increments the counter register, loops back and repeats. Upon receiving the RF trigger command, Node B immediately sends an acoustic (or ultrasonic) pulse (step 338). The timer on node A continues to operate until a pulse is received (step 340), at which point the timer is stopped and latched. The time to be latched is the time it takes for the voice pulse to travel from node B in one direction to node A, taking advantage of a known velocity in the medium (usually air) between node B and node A. Used to calculate the distance. Distance calculations may include corrections for factors such as wind, humidity and temperature (if the required information is provided by local sensors or user input). The calculated distance can be used in the method of topology knowledge and self-organization as described above.

【0093】

Although specific embodiments of the present invention have been illustrated and described, various modifications and alternative embodiments will be conceivable to those skilled in the art. Therefore, the present invention is intended to be limited only by the preceding claims.

[Simple explanation of drawings]

[Figure 1]

It is a schematic diagram which shows the overlapping communication distance of four wireless communication nodes.

[Figure 2]

It is a figure which shows the neighbor of a given node.

[Fig. 3]

It is a figure which shows an example of a network topology.

[Fig. 4]

It is a figure which shows the new node which responds to the transmission solicitation from an existing network according to this invention.

[Fig. 5]

It is a figure which shows the potential interference area of the new node of FIG.

[Fig. 6]

It is a figure which shows the potential communication area of the new node of FIG.

[Fig. 7]

It is a figure which shows the place where the transmission solicitation node and the new node determine the distance d which separates them.

[Fig. 8]

It is a figure which shows the latent area of communication and interference which is limited after performing distance measurement.

[Fig. 9]

It is a figure which shows the communication neighbor of a new node determined by the step of this invention.

[Fig. 10]

It is a figure which shows the method of finding a new node further and the limitation obtained as a result of an interference area.

[Fig. 11]

It is a figure of the interference neighbor node of a new node.

[Fig. 12]

It is a flowchart of the preferable method used by this invention.

[Fig. 13]

It is a flowchart of the preferable method used by this invention.

[Fig. 14]

It is a flowchart of the preferable method used by this invention.

[Fig. 15]

It is a flowchart of the preferable method used by this invention.

[Fig. 16]

It is a figure which shows an example of the allocation of the time slot in the TDMA time frame which can be used for scheduling a communication in this invention.

[Fig. 17]

It is one outside perspective view of the electronic detection device or "node" of this invention.

[Fig. 18]

It is a block diagram which shows one architecture of the electronic detection device or "node" of this invention.

[Fig. 19]

It is a block diagram of the wireless transceiver which can be used in this invention.

[Fig. 20]

It is a flowchart of the ultrasonic wave or voice distance measuring method which can be used in this invention.

[Explanation of symbols]

100 nodes, 200 yen, 400 nodes, d distance, g distance.