CN1973490B - Method of operating an ad hoc network and apparatus for forming an ad hoc network - Google Patents

Abstract

The present invention provides a wireless ad hoc network. A method of operating an ad hoc network comprising a plurality of devices (11-16). Each device comprises communication means for communicating with other devices of the plurality of devices when they are within range. The method comprises the following steps: one or more node policies (1-6) are stored in each device, the node policies specifying rules for determining how the device should operate in response to various common circumstances, and each device is controlled to operate in accordance with one or more of the stored node policies. In addition, an adaptive parameter is stored on each device, and its value is adjusted according to the level of activity of the device (in particular, activity consistent with its stored policy). Furthermore, each device monitors the value of its stored fitness parameter and the activity of its communication means and sends (46, 48, 49) one or more of its stored node policies (5) to other devices (13, 15, 16) within range when its fitness parameter exceeds a threshold and its communication means is not needed for other purposes.

Description

Method of operating an ad hoc network and apparatus for forming an ad hoc network

technical field

The present invention relates to an ad hoc network, and more particularly to a method of operating an ad hoc network in which a plurality of small devices with limited processing power and communication bandwidth cooperate with each other on a peer-to-peer basis, There is no central control mechanism to allow data to be sent between the devices that make up the ad hoc network.

Background technique

The inventors have previously developed a protocol inspired by the way colonies evolve to adapt to changing environments. The protocol was originally designed for use in active networks, where the switching nodes of the network are capable of performing more than the simple switching function traditionally assigned to switching nodes in data or communication networks. This protocol is described in detail in the following published international patent applications: WO 01/59991, WO 02/23817, WO 02/073889, the contents of which are hereby incorporated by reference.

The protocol is described in more detail in the aforementioned application, and in brief, the protocol enables active nodes to exchange pieces of software (commonly referred to as node policies) between each other, modifying the functionality of each node accordingly, these software Each of the blocks controls a corresponding functional block of the node. This is similar to the way bacteria in a community exchange small pieces of genetic material between each other to change the function of each individual bacterium. This exchange is controlled simply by allowing "successful" bacteria to distribute chunks of genetic material over the colony, which are then acquired by less "successful" neighboring bacteria. In the natural setting of a colony, success is determined by the amount and rate at which nutrients are metabolized to produce energy. In this similar protocol devised by the present inventors, the success of each node is determined by the amount and speed at which the node performs the service.

The inventors expect that the protocol can be successfully applied to ad hoc networks formed by a large number of simple devices with limited processing and communication capabilities. However, the inventors have not actually attempted to do so, so it is unclear whether the technique would port well to such an environment.

Contents of the invention

According to a first aspect of the present invention, there is provided a method of operating an ad hoc network comprising a plurality of devices, each of which may be located within the device if the operating environment permits communicating with other devices of the plurality of devices while within range of each other, the method comprising: each device storing one or more node policies, and based on the stored node policies operate; each device stores an adaptive parameter and updates the adaptive parameter by increasing the adaptive parameter during active periods of the node and decreasing the adaptive parameter during inactive periods; and each Each node sends one or more of its stored node policies to neighboring nodes according to the value of its fitness parameter, and each node stores the received node policies according to its fitness parameter, where each device has Where the stored node policy indicates that the node should simultaneously send data to one or more neighboring devices, the sending of the node policy is suppressed.

The inventors have found that operating the ad hoc network in this way results in a network with excellent performance. Specifically, by using the same communication channel to send data and policies, whenever possible, the scarce bandwidth resources in typical ad hoc networks are fully utilized to send data. However, in an ad hoc network, even the most successful nodes will still have periods of inactivity, and this natural outage provides enough bandwidth to send policy messages, allowing the network to evolve to adapt to changing environments, etc.

Preferably, said adaptive parameter varies inversely according to the number of neighboring devices having within its range in response to an increasing amount of the active period. In this way, devices that manage to remain active but communicate with only a few neighbors (assuming that the topology of these devices is not controlled by a single device) are considered more efficient than those that are only equally active but have many more neighbors interacting. Be adaptable.

In a preferred embodiment, the method is employed to form a sensor network comprising a plurality of sensing devices that can operate autonomously, thereby enabling the devices to collect sensory information from moderately harsh environments. sensed data and wirelessly sends the sensed data back to the processing center. When utilizing one or more node policies in this manner, the one or more node policies may specify that a device may, under certain conditions, use some of its processing resources to compress its storage for subsequent forwarding Sent sensor data. Preferably, one type of compression that the device can perform is comparing a target stored measure with a corresponding reference stored measure taken at a different time instant, determining whether the target stored measure is within a range that can be derived according to a predetermined formula The estimated measurement value derived from the reference measurement value is within a predetermined acceptable error range, and if it is within the range, the target measurement value is deleted. Then, at the processing center, an estimated measurement is generated using the same formula that the compression device first used to determine whether to delete the target measurement, thereby "recovering" (with an acceptable error) the deleted Measurements. As an example, the reference measurement values may be measurement values immediately before and after the target measurement value in time, and the predetermined formula may take an average value of the reference measurement values.

According to a second aspect of the present invention there is provided an apparatus for forming an ad hoc network when communicating with other compatible devices, said apparatus comprising: communication means for forming said ad hoc network with a part of other means for communicating; storage means for storing node policies; processing means for processing said stored node policies and operating accordingly, and also for determining a level of adaptability associated with said device ; wherein the device is operable to transmit via the communication means to a neighboring device when it detects that its adaptability level is above a predetermined threshold and it is not using the communication means to transmit data in accordance with the stored node policy One or more of its node policies.

Said communication means is preferably, but not necessarily, a radio transceiver. However, alternative communication means or transceivers may use sonar or optical transmission methods, for example.

According to a third aspect of the invention there is provided an ad hoc network comprising a plurality of devices according to the second aspect of the invention.

Other aspects of the invention relate to corresponding computer programs and carrier media carrying such computer programs. Examples of carrier media used for this purpose are a magnetic or optical disc, solid-state memory or a carrier signal suitable for modulation or a series of underlying data packets enabling the program or programs to be downloaded to such a memory, for example over an analog or digital network superior.

Description of drawings

For a better understanding of the invention, embodiments thereof will be described below, by way of example only, with reference to the accompanying drawings, in which:

1 to 6 are schematic diagrams showing positions and states of each mobile device in each of a series of six consecutive time periods (epochs) in an ad hoc network according to a first embodiment of the present invention;

Figure 7 is a timing chart representing the sequence of messages passing between the devices during the six time periods shown in Figures 1 to 6; and

8, 9, 10 and 11 are graphs showing simulation results of another embodiment of the present invention.

Detailed ways

In general, the ad hoc network of the present invention assumes that the devices forming (the individual nodes of) the ad hoc network have only data to carry (hereafter, data is used to mean that other than genetic material (i.e. node policies) are transmitted between devices anything) a finite amount of bandwidth for communication. The second assumption is that: data should be treated as time-critical in order for the network to operate efficiently, however, genetic information can be distributed at a slower rate due to the properties of the colony-inspired genetic algorithm used to improve the overall efficiency of the network . Finally, it is assumed that the properties of the network will be such that there will be periods when nodes do not send data, and during these periods the same communication channel can be employed to send less temporally critical genetic information between nodes.

Therefore, two different embodiments implementing the above assumption will be described below. The first embodiment clearly illustrates an example setup that realizes the above assumptions. Simulations and performance analysis were performed on the second embodiment, and it was found that the second embodiment performed well.

first embodiment

The first embodiment concerns an ad hoc network formed of a plurality of personal digital assistant type devices, each device having a mechanism for communicating with other such devices over a wireless communication channel of limited bandwidth, as long as the devices are in close proximity to each other , and is open and not shielded (e.g. in elevators, etc.).

In this embodiment, each device has a function that enables devices located within range of each other to communicate with each other in an efficient manner. This involves enabling each device to broadcast to, or be received by, up to a predetermined maximum number of devices during predetermined time intervals called time slots. Such functionality needs to resolve issues such as collisions, noise, interference, etc. These issues are considered low-level issues, which are not addressed by the present invention. In particular, the present invention does not address issues related to the 2 lowest layers (ie, the physical layer and the link layer) according to the 7-layer OSI reference model.

The only way the underlying functionality is relevant to the present invention is assuming that these communications are broadcast rather than point-to-point. However, it will be apparent to the reader that the present invention can be readily adapted to point-to-point communication methods without much modification. A great deal of work has been done, and is still going on, to improve this type of communication protocol for ad hoc networks, and any suitable such protocol may be employed by the present invention. The presently available examples are given in "Ad Hoc networking", Charles E. Perkins, Pub. Addison Wesley, Dec. 2001 and references cited therein or in "The Handbook of Ad Hoc Wireless Network" Mohammad llyas (Ed.) An example of such a protocol.

In this embodiment, each device is programmable and capable of performing a variety of different functions according to the user's preferences. One of these functions provided in this embodiment is the function of the communication layer, i.e. receiving as input data for sending to neighboring devices in the ad hoc network, and outputting data received from neighboring devices in the ad hoc network (Throughout this specification, the term neighbor device is used to refer to those other devices in the network with which any given device can communicate directly through the air interface). In this embodiment, it is configured to perform such communication once within a time period hereinafter referred to as a time period, and this time period can be changed according to the user's preference, the number of neighboring devices, and the like.

Based on the above concepts, the communication layer (in the sense of the ISO seven-layer data communication model) is the bacterial algorithm layer, which controls the storage strategies described in detail below, controls the operation of the device according to these strategies, and executes the bacterial algorithm. Functions for general functionality required for correct operation.

Each of the devices in this embodiment runs an application operable to accept requests from users, in addition to the underlying functions that enable communication and the functions that control the operation of the device according to the bacterial evolution algorithm Thereby displaying a specific document and, if the requested document is found not stored locally, initiating a search for the document in the ad hoc network.

example

Referring now to FIGS. 1 to 6 and 7, the example follows the steps performed by each of the six devices 11, 12, 13, 14, 15 and 16 in six consecutive time periods. In this embodiment, each time period includes a first part, not explicitly shown in any of Figures 1 to 7, in which a device may send a request to its neighbors to receive data , and nodes that have already received this request can respond to this request (but only such requests) in the same time period.

In FIG. 1, each of the devices 11 to 16 is represented by a rectangle including three integers in the format x, y/z, where x and y represent the proxylets currently stored and effectively used by each device. ). Here, the term applet is used to refer to a small program that adds functionality to the performance of a device used as a node in an ad hoc network in a manner similar to how an applet adds functionality to a web browser. The integer z represents the adaptability level parameter of the device.

In this example, the device is a very simple proof-of-concept device, in which all functions above the underlying communication functions are provided through the above-mentioned small agent program, and each device can store and use only two small agents at any time. agent. Of course, in an alternative more complex system, each device could alternatively store many different small agents, or, in addition, a more complex device could run multiple applications using a complex operating system, thereby The agent execution environment will represent only one such application, and data can easily be passed between different applications running on the device.

Therefore, in this simple embodiment there are only 6 sub-agents numbered 1 to 6 as follows: 1 Charge (this is to enable the user to receive data from the ad hoc network and to charge the user appropriately so that the user can use this necessary to obtain data from the network); 2 security (the small agent allows the node to encrypt and decrypt the data); 3 compression (the small agent allows the node to compress the data before sending it); 4 view ( The aglet enables the user of the device to view the received data - it includes means for sending a request to fetch specified data from the network (in case the data is not available locally), and in this embodiment it also request to send this data in a compressed format and decompress it as necessary before displaying it to the user on the PDA screen); 5 routing (the little agent enables routing of data requests towards nodes that can fulfill the request, and towards the original requesting node routing data from remote nodes); and 6 database (this little agent enables devices to store data and transmit data back towards the requesting node in response to a request for data from another node).

If the device receives a request to which it can respond successfully (because it contains the appropriate aglet or agents), it will send an appropriate response signal. If the device does not send or receive signals associated with the request (i.e., not just genetic material signals), it seeks to receive genetic material signals or send genetic material signals depending on whether its fitness is below the lower threshold or above the upper threshold signal (if the adaptation is between these thresholds, the device will neither send nor receive any gm signal). A device increases adaptability by receiving or sending signals related to a request, and loses adaptability by doing nothing. In a sparsely populated environment, a node may sometimes have no choice but to do nothing, which can be distinguished from a situation where there is no wireless communication of any kind. There is no penalty for not doing anything more than necessary. Sending or receiving gm signals tends to enable the device to maintain its current fitness level.

In the present example shown in Figures 1 to 7, the communication ranges of some devices (11, 12, 14 and 15) are indicated by dotted circles (11a, 12a, 14a, 15a). Therefore, it can be seen from Figure 1 that the following pairs of nodes are within range of each other: 12&13; 13&14 and 14&16. Nodes 11 and 15 have no neighbors.

Prior to the time period shown in Figure 1, node 16 had requested (as a result of the user's control of the device) that a specified piece of data be sent for viewing by the user. Also before the time period shown in Figure 1, the node 14 containing the routing aglet has now received the request and therefore attempts to route the request onward.

Thus, in time period 1, node 14 sends a (broadcast) request for data, node 16 ignores the request (because it is the original requester), and the request causes node 13 (because it has the database aglet 6 and the compression The aglet 3, which also happens to store the requested data item) responds to the request from the node 14 by routing the data signal 22 to the neighboring node 14. Note that node 13 also sends signal 20 to its other neighbor node 12 because all communications are broadcast to all neighbor nodes in this embodiment, but since this node did not request the data, the It simply ignores the signal, as indicated by the "Do Not Enter" symbol in Figure 1.

Note that Figure 7 also shows node 13 sending signals 20 and 22 to nodes 12 and 14, respectively, in time period 1. In FIG. 7 , the fact that the receiving node ignores signal 20 is shown by the dashed arrow representing signal 20 , while the solid arrow is used to represent signal 22 received and processed by node 14 . The fact that both signals are data signals is indicated by the word "data" written above the arrows representing signals 20 and 22 .

As mentioned above, each node maintains a fitness parameter. At the end of each time period, the adaptive parameter is changed according to a set of rules. In this embodiment, the following rules are used: 1) If a device has no neighbors for that time period (i.e., it is out of range or obstructed from communicating with any other device for that time period), then adapt 2) If the device sends or receives genetic material signals (and thus not data signals), this parameter remains unchanged; 3) If the device sends or receives data signals, the parameter value increases by 10 points; 4) If a device does not send or receive any signals through a neighbor even though the device has one or more neighbors that can exchange signals, its fitness parameter is reduced by 5 points.

Therefore, by comparing Figure 1 and Figure 2 (Figure 1 and Figure 2 respectively show the value of the adaptive parameter of the node at the beginning of time period 1 and time period 2), it can be seen that the adaptive parameter values of the six nodes Between the start and end of time period 1 the following changes: node 11 keeps its fitness parameter at 50 because it has no neighbors during the first time period; node 12's fitness decreases from 50 to 45 because despite its Can communicate with node 13, but it does not (because it has no interest in receive signal 20 containing the data requested by node 16); node 13 adaptability increases from 50 to 60 because it sends data signal 22 (and 20) The fitness of node 14 increases from 50 to 60 because it receives signal 22; the fitness of node 15 remains unchanged at 40 because it has no neighbors during time period 1; while the fitness of node 16 decreases from 50 to 45 because although it was able to communicate with node 14 during time period 1, it did not communicate at all.

In time period 2, the main action is sending a signal 36 from node 14 to node 16 carrying the requested data (originally from node 13). Besides this, (as shown in Fig. 7) the signal is also broadcast to neighboring nodes 13 (as unwanted signal 34).

However, in this embodiment, each device is operable to use a selected one of its aglets (with any together with accompanying usage information) as a genetic material (gm) signal to adjacent devices, these conditions are:

1) the device has a fitness parameter value greater than 50; and

2) The device does not actively send data to or receive data from neighboring devices.

In addition, each device is additionally operable to accept any gm signals broadcast to it from neighboring devices, and to replace its own stored aglets with new aglets received in this way, subject to the following conditions A small agent in the program, these conditions are:

1) the device has a fitness parameter of less than 50; and

2) The device does not actively send data to or receive data from neighboring devices.

Thus, in time period 2, device 13 (which has an adaptive parameter value of 60 and which does not transmit or receive any data signals) sends to nodes 12 and 14 the gm signal accepted by node 12 (signals 30 and 32, respectively), This node 12 has an adaptability parameter of 45 and does not send or receive any data signals, thereby replacing its own previously stored aglet 1 with the received aglet 3 (see FIG. 3 ). (Note that in this embodiment, the aglets are swapped on a first-in-first-out basis; however, in alternative embodiments, the selection of the The current aglet is swapped with the new aglet). However, node 14 does not receive the broadcast signal because its fitness parameter is 60 and because it is sending a data signal (either of which reasons alone would be sufficient to prevent reception of the gm signal).

Referring now to Figures 2 and 3, at the end of time period 2 (or, equivalently, at the beginning of time period 3), the fitness of each node changes (during time period 2) as follows: Node 11 maintains its fitness parameter is 50 because it has no neighbors during time period 2; the fitness of node 12 remains constant at 45 because it receives a gm (genetic material) signal 30 from node 13; the fitness of node 13 remains constant at 60, Because it sends the gm signal 30; the fitness of node 14 increases from 60 to 70 because it sends the data signal 36 (and 34); the fitness of node 15 remains unchanged at 40 because it has no neighbors during time period 2 device; while the adaptability of node 16 increases from 45 to 55 because it receives data signal 36 during time period 2 .

At the beginning of time period 3, node 11 is within range of node 13 . Although not explicitly shown, as the first part of this time period, node 11 sends a data request to node 13, which happens to have the relevant requested data (and has the required alets 3 and 6). Thus, the primary data transfer signal during time period 3 is node 13 sending the requested data to node 11 via data signal 40 (and also broadcasting this data via unwanted signals 42 and 44 to nodes 12 and 14, respectively) .

Furthermore, in time period 3, node 14 is idle (i.e., it does not receive or transmit any data signals) and has an adaptive parameter value greater than 50 (it is 70), so that it converts gm signals 46, 48, 49 to all its neighbors (ie, nodes 13, 15 and 16). Nodes 13 and 16 reject the gm signal (because they have too high a fitness score—and also because node 13 is busy sending data signals), but node 15 is idle and also has a fitness value below 50 (which is 40), so the node 15 accepts the gm signal (which in this case contains the aglet 5) and stores the newly received routing aglet 5 in place of the view aglet 4 (see Figure 4). Node 16 is also idle during time period 13, so it also tries to send some of its genetic material (aglet 1) to its two neighbors (nodes 14 and 15) using signals 43 and 45 respectively. However, node 14 rejects the signal because its fitness parameter is too high (not lower than 50); node 15 rejects the signal because it preferentially receives signal 48 from node 14 because the fitness parameter of node 14 is higher than that of node 16 Adaptability parameter (note that this makes in this embodiment, the node that needs to send the genetic material also informs the receiving node of its adaptability level, so that the receiving node (multiple receiving nodes) determines to accept which signal; in alternative embodiments, the determination may be made randomly, or more than one such signal is received simultaneously, bandwidth permitting, etc.).

Referring now to Figures 3 and 4, at the end of time period 3 (or equivalently, at the beginning of time period 4), the fitness of the individual nodes is as follows: The fitness parameter of node 11 increases from 50 to 60 because its A data signal 40 is received during time period 3; the fitness of node 12 decreases from 45 to 40 because it did not send or receive any signal during time period 3; the fitness of node 13 increases from 60 to 70 because its transmits data signal 40; node 14's fitness remains unchanged at 70 because it transmits gm signal 48; node 15's fitness remains unchanged at 40 because it receives gm signal 48 during time period 3; and node 16's Adaptability is reduced from 55 to 50 because it did not (successfully) send or receive any signal during time period 3.

In time period 4, node 13 loses communication with all its surrounding nodes (eg because it entered an area blocking communication (eg elevator) or because it temporarily lost power, etc.). Node 11 wants to continue receiving more data; since node 13 has lost connection with node 11, node 12 (which now contains the correct aglet for responding to the request, i.e., aglet 6 (database) and 3 (compression)) replace node 13 and provide the required data to node 11 via signal 50 . The data is also broadcast (via signal 52 ) to other neighboring nodes 15 of node 12 ; however, node 15 ignores signal 52 because it did not request the data. Node 14 is idle during time period 4 because it has moved out of range of all other nodes so that it has no neighbors to communicate with. Node 15 has received a request for some data from its user (not shown) and has therefore issued a (broadcast) request for said data which has been received by node 15 (the only neighbor of node 16) signal (not shown). Node 15 does not have suitable data or an aglet to respond directly to the request with the required data, but instead sends a return signal 54 indicating that it will forward route the request; like all signals in this embodiment, this The return signal is broadcast such that signal 56 is also generated and received by node 12 . However, in this embodiment, node 12 ignores signal 56 since the return message is only addressed to node 16 .

Referring now to FIGS. 4 and 5 , the adaptability level of the nodes thus changes during time period 4 as follows: node 11's adaptability parameter increases from 60 to 70 because it receives data signal 50 during time period 4; node 12 adapts The fitness increases from 40 to 50 because it sends a data signal of 50 during time period 4; the fitness of node 13 remains unchanged at 70 because it has no neighbor nodes during time period 4; the fitness of node 14 remains the same is 70 because it also has no neighbors during time period 4; the adaptability of node 15 increases by 10 from 40 to 50 because it sent a return routing message signal 54 to node 16 during time period 4; and, similar to Clearly, the adaptability of node 16 increases by 10 from 50 to 60 because it received signal 54 during time period 4 .

In time period 5 (see Figures 5 and 7), node 15 issues a (broadcast) data request, node 12 (because it has database aglet 6 and compression aglet 3, and because it happens to store the requested data item) responds to the data request with a data signal 60 for routing to the neighboring node 15 . During time period 5, nodes 11, 13 and 14 are all idle because they have no neighbors. Node 16 attempted to send gm signal 62 to its only neighbor node 15 because it was not involved in any request-related signal during time period 5 and because its fitness parameter was greater than the upper threshold (adaptability parameter (60) > upper limit Threshold (50)); however, since node 15 receives request-related data signal 60 from node 12, it ignores signal 62.

Referring now to Figures 5 and 6, the adaptability level of the nodes thus changes during time period 5 as follows: the adaptability parameter of node 11 remains unchanged at 70 because it has no neighbors during time period 5; the adaptability of node 12 The fitness increases from 50 to 60 because it sends a data signal 60 during time period 5; the fitness of node 13 remains unchanged at 70 because it has no neighbor nodes during time period 5; the fitness of node 14 remains the same is 70 because it also has no neighbors during time period 5; the fitness of node 15 increases by 10 from 40 to 50 because it receives data signal 60 from node 12 during time period 5; while the fitness of node 16 The performance decreased by 5 from 60 to 55 because it did not receive and (successfully) send any signal during the period 5.

Referring now to FIG. 6 , during time period 6 , node 15 again sends to original requesting node 16 via data signal 70 the data that node 15 received from node 12 during the previous time period. Nodes 11 and 14 have now moved completely out of view, remaining idle since they had no neighbors during time period 6. Nodes 12 and 13 (which have "come back online" during time period 6) both (unsuccessfully) attempt to communicate Neighboring nodes transmit some of their genetic material; however, none of the other nodes are in a position to receive the gm signal, so the gm signal was not successfully transmitted and received during time period 6. The unsuccessful gm signal for node 12 is signal 76 to node 15 and signal 78 to node 13, while the unsuccessful signal for node 13 is gm signal 79 to node 12 and gm signal 80 to node 15 . Node 12 ignores the signal 72 back from node 15 to node 12 because node 12 just sent that data to node 15 and is not interested in receiving it back, and likewise the signal 74 sent to node 13 also contains the same data is also ignored because node 13 did not request the data, and node 13 does not contain an associated aglet to route the data forward.

It will be obvious to the reader that at the end of time period 6, the nodes will have the following fitness levels: node 11 fitness = 70, node 12 fitness = 55, node 13 fitness = 65, node 14 fitness = 70, fitness of node 15 = 70, fitness of node 16 = 65. The adaptive rewards used can be coarse and large in order to reveal the running state in as few steps as possible. Actual implementations will have a much finer-grained penalty/reward structure, where rewards are based on fees and quality of service, and penalties are based on drop rates, wait times, and fees.

Alternative to the first embodiment

It will be apparent to the reader that many changes can be made to the first embodiment. For example, a finer set of rules could be employed to vary the level of fitness in a more complex manner. For example, the amount of change in the fitness level may depend to some extent on the actual fitness level in order to avoid reaching the limit value of 0 or 100% too quickly or completely. Furthermore, the amount of fitness is also varied in a more complex way (in the above example there are two classes, namely, no nearest neighbors (in which case fitness remains constant) and one or more nearest neighbors (in this case, changing fitness)) depends on the number of nearest neighbors, e.g., proportional to the number of nearest neighbors, or by having three or more independent categories ( For example, zero adjacent nodes, one or two adjacent nodes, and three or more adjacent nodes) etc. to change the amount of adaptive variation.

second embodiment

As mentioned in the introduction, the present inventors previously developed an algorithm for distributing software in active networks. It can be speculated that a similar approach can be used to provide services in ad hoc networks. The second embodiment described here was simulated with and without specific modifications to use the algorithm in an ad hoc network. The results show that although a direct transfer of the method from active networks to ad hoc networks shows good performance graphs, improving the algorithm with specialized modifications to account for some properties of ad hoc networks can give particularly good performance A set of performance graphs. Surprisingly, the algorithm actually seems to be more applicable to ad hoc networks than to fixed active networks. The lower (compared to fixed) hardware standards of mobile devices means that more attention should be paid to what software is installed on mobile devices and what software is downloaded when needed, so that the right software is installed on the right node at the right time software.

To demonstrate the applicability of the bacteria-based adaptive algorithm, a set of simulation experiments is designed to test various networked device scenarios.

The test is divided into 3 parts:

1. Test (i.e. simulate) the "bacteria" algorithm without improvement in an active network scenario (as previously described), where the bandwidth between devices is "infinite", the devices are 100% reliable and a fixed phase neighbor structure;

2. The same algorithm without improvement is then tested (i.e. simulated) in a more Ad-Hoc environment, where devices are less reliable, have smaller bandwidth connections, and do not maintain a fixed structure;

3. Finally, the algorithm is improved to include some specialized modifications to make it more suitable for Ad-Hoc networks, and then retested and resimulated in an Ad-Hoc environment.

All three simulations involved the use of four nodes, each of which forwarded requests that it could not satisfy by itself. The nodes to which unsatisfied requests are forwarded depend on the node under consideration, as follows:

Node 0 forwards to nodes 1 and 3,

Node 1 forwards to nodes 2 and 0,

Node 2 forwards to nodes 3 and 1, and

Node 3 forwards to nodes 0 and 2.

To make the nodes less reliable in the "Ad-Hoc"-like environment in the second and third simulations, each node was randomly disabled X% of the time, and each connection was randomly disabled Y% of the time disconnect. By allowing only Z requests through at any one time (queuing any that don't come through, and dropping them if they time out), the bandwidth of the connection is actually smaller. The lack of a fixed network is simulated by changing the two forwarding receivers at random intervals. The modification to improve the aptitude of the Ad-Hoc network is as follows:

1. Pass genetic data only if there is excess bandwidth - There is a fixed bandwidth between devices for passing data and control variables, and genetic properties are passed in this way as well. In a wireless ad-hoc network, this is determined by the frequency used, range and power output (watts). The need for the control variable is intermittent, so that it provides a great advantage together with the new bandwidth limitations required for the more economical use of bandwidth by the Ad-Hoc network. Sending communications of no time importance during the quiet period is a very advantageous means of optimizing the algorithm. A "quiet period" is the time during which a node neither sends nor receives data or requests during the most recent send and receive window.

2. Broadcast structure data to all neighboring nodes - In a wireless environment, there is inherent efficiency in one node broadcasting to multiple recipients. Some nodes may be busy and thus unable to receive, but the sending node does not incur additional load when sending its structured data in broadcast mode compared to unicast. While some wireless transmissions are directional (directional transmitter and receiver), there are a large number of networks where wireless transmissions are non-directional, and in these cases this advantage is significant.

In all cases, the performance measures (proportion of lost data packets, total number of data packets received by the receiver) were compared with the performance of the stochastic approach and the caching approach.

Initial results show that:

a) For all algorithms, performing "Ad-Hoc" simulations significantly increases latency and loss rates; this is to be expected since nodes are offline or unreachable for a fraction of the time and bandwidth is limited;

b) genetic/bacterial approaches continue to provide the most adaptive solutions; and

c) Improving the Genetic/Bacterial Approach Algorithm through Ad-Hoc-specific refinements further significantly improves performance.

The algorithm for making equipment decisions according to the present embodiment is different from the methods described in International Patent Applications WO 01/59991, WO 02/23817 and WO 02/073889. The algorithm and simulation environment are summarized as follows:

The designed model is that of a simple Ad-Hoc sensor network with the task of optimizing their battery usage while collecting data from a station. This simulation setup can be described by the following statement:

Gives every device in the network the ability to move geographically along bounded random lines.

Each device can be active or inactive at each time step (period).

Every device has a battery that is used, monitored, and recharged during periods of inactivity.

The task is to route the data sensed at the nodes to some central data "sink".

There are three qualities of data to be sensed, ie high quality, medium quality and low quality.

Each device puts each data item sensed or received into a FIFO queue by forwarding. Then operate on that data (delete, combine or forward). The length of the queue is initially set to 50, and if the queue exceeds 50 at any point, any newly sensed data is simply discarded without storing it.

The new task assignment algorithm is described by the following statement:

Nodes are able to execute one task per time period. Sense, forward, delete, compress or invalidate (these tasks will be described below).

Each node determines what state it is in during each time period based on a set of values and a random number. For example, a node can have the following behavior values:

Sensing 20%

Retweet 50%

remove 2%

3% compression

Ineffective 25%

So it will sense 20% of the time, forward 50% of the time, etc.

These values are changed in two ways, namely local rules and evolution-based, adaptive rules.

Local rules act on these values according to internal values of battery level and queue length.

1. If the queue is larger than (random number (0-1)*15), then

Relay*1.05

Sensing*0.95

combination*1.01

If the queue is less than (random number (0-1)*15), then

Relay*0.95

Sensing*1.05

Combination*0.99

2. If the queue>45, then node_plasmid(i).sense=0

3. If the queue > 30, then

Relay +0.02

Sensing - 0.03

Delete +0.01

combination +0.01

If queue < 30, then

Relay - 0.02

Sensing +0.03

delete=0

Combination - 0.01

4. If the battery <100, then

Relay*0.95

Sensing*0.95

Adaptiveness-based rules employ an adaptive indicator to determine whether to change the value of a node randomly or by copying values from neighboring nodes. This is similar to the same bacterial evolution method in the above-mentioned international patent application, and it is a long-term learning method. Node fitness rewards are given for sensing data and forwarding data. The initial settings of the nodes are determined randomly.

The different possible tasks are:

Sensing: This involves taking measurements, and storing the resulting data for subsequent forwarding, or simply discarding the sensed data if the queue is too long. In this embodiment, all possible types of measurements that the device is capable of taking are made during a single sensing period, however, in alternative embodiments, only one measurement may be made during any one time period, or only The subset of possible measurements to take (which may be determined in a systematic way or by node policies or the like) varies.

Forwarding: This simply involves broadcasting the next piece of data for forward forwarding. In the case of only one queue, the next piece of data can be determined directly. Where there are two separate queues (one for self-sensed data and one for data received from neighboring nodes), it can be done in a systematic way (e.g. always pick from one queue first, or always selection in turn, etc.) or by node strategy to determine the next piece of data. In some embodiments, a preferred node for forward transmission can be selected and broadcasts can be addressed only to that node, alternatively data can be forwarded to all nodes within range and each receiving node can determine Whether it is closer to the receiver than the sending node, thus determining whether to receive data, etc. A variety of ad-hoc routing schemes are known for handling such situations, and any suitable such scheme may be employed in this embodiment.

Delete: This involves selecting a piece of data to be deleted, and then deleting it. Can follow a systematic approach (e.g., find the earliest, lowest priority, self-sensing piece of data and delete it, if there is more than one data item that is also worthy of deletion, choose one at random, etc.) or through node strategy for deletion.

Compression: In this embodiment, two different types of compression can be performed, hereinafter respectively referred to as probabilistic compression and sliding window compression. In probability compression, by taking the weighted average of two measurements (preferably adjacent to each other in time, i.e., with no intervening measurements), and summing their weights to form a new average measurement, thus From these two measurements a new combined measurement is formed (e.g. if there are two measurements (t=10min, temp=8C, weight=1) and (t=20min, temp=10C, weight=1), These two measurements can then be combined to form (t=15min, temp=9, weight=2), which can then be further combined with the measurement (t=30min, temp=12C, weight=1) to form ( t=20min, temp=10C, weight=3)). In sliding window compression, a target measurement is compared to a calculated estimate, in this embodiment two reference measurements according to a predetermined formula such as a simple average, and if the estimate is within an acceptable error range , then delete the target value (for example, in the case where the target measurement value is (t=20min, temp=10C), and the reference measurement value is (t=10min, temp=8C) and (t=30min, temp=12C) Here, the estimated measurement will be (t=10min, temp=12C), which is equal to the target measurement, so the target measurement is removed). Which type of compression to do can be determined in a systematic way (e.g. always do sliding window if enough data is available, or alternately, etc.), or set by node policy Compression, which can change its decision based on local observations, etc.

Invalidation: As mentioned above, in this embodiment, each device has a mechanism to charge its battery, and during inactivity, the device can (if environmental conditions allow) charge its battery level up to a certain level.

Note that in this embodiment, each measurement is stored, processed, and forwarded as a separate data packet that includes the identification of the device that made the measurement, the time the measurement was taken, and an indication of the type of measurement (for example, temperature). In the case of statistical compression, each data packet also includes an indication of the weight of the measured values. The downside of this is that each data packet contains a larger proportion of overhead, but it does mean that the node has a greater degree of interest in lower priority measurements than higher priority measurements. Maximum flexibility for compression, and more. One possibility to reduce overhead in certain circumstances is to process multiple measurements into a single table-type format before sending, thereby reducing the amount of overhead before sending.

In this embodiment, Ad-Hoc network simulation is carried out for 4 different situations:

static/open - nodes do not move, and are 100% reliable

static/off - the node does not move, but is only active 95% of the time

move/open - nodes move around in a random route and stay open at all times

Move/Close - Nodes move around in a random route, but only valid 95% of the time.

While the first 2000 epochs exhibit low loss rates due to the initial highly charged battery state, after 1000 epochs each node must more carefully determine how to use its limited battery resources. For three of the four test scenarios, the loss rate during the 1000 to 2000 time period was similar to the loss rate during the 9000 to 10000 time period, while performance improved only in the mobile/closed test environment. While moving nodes and unreliability do increase the loss rate somewhat, this is entirely understandable since both mobility and unreliability can completely isolate some nodes in a situation where the sending range is limited. The fact that performance is stable over 10,000 time steps is an important achievement, and the fact that most of the knowledge is seen in most dynamic environments indicates success with modifications, especially those that only send genetic material during quiet periods Degree.

Similar results were shown for send rate (the amount of data returned to the receiver). This is also encouraging, as it suggests that the stable or decreasing loss rate is not due to any reduction in data transmission.

Figure 8 relates to the case where there are three different priorities assigned to different types of data packets. It shows how a reduction in the rate at which a device can send data affects the success rate of three different data types by varying amounts through a specially adapted bacterial algorithm. The performance degradation obviously depends on the importance of the three data types. High priority from 100 as bandwidth decreases from maximum (where up to 20 data packets can be sent per time period) to minimum test bandwidth (where each node can only send one data packet per time period) % to 90%, medium priority from 97% to 63%, and low priority from 95% to 46%. This is a desirable feature because less important data is preferentially discarded when the network is more "stressed".

Fig. 9 shows a problem that as the number of data packets that can be sent per time period decreases, the number of lost data packets also increases. The question is, is it only the number of lost data packets that has an effect on the reduction in sending rate? It is evident in Fig. 9 that the increased loss rate does not have much effect on the reduction of packets (the dashed line is the number of packets that should have been received without any packets being lost). Conversely, it would also be desirable behavior to have some back off at sensing points in the network in response to packets accumulating at nodes closer to the receiver.

Figure 10 shows the effect of a node's position in the network. The number of sensing epochs performed by each node during a run of 10,000 epochs was measured and plotted against the order of each node for the static and moving networks, and the results are shown in Fig. 10. It was evident that some nodes were sensing more than others, so a second test was performed to find the reason for this (see discussion of Figure 11 below).

Figure 11 shows that the number of sensing time periods per 10,000 time periods decreases as the number of nodes acting as conduits increases, except when the nodes involved are adjacent to the receiver, where The number of time sensing periods is slightly increased. In Figure 11, each plotted point represents the average number of senses made by all nodes with the specified number of other nodes used as conduits; since 5 different trials were used to generate Figure 11 , so that for each valid number of nodes (for which one or more nodes are used as pipelines), there are 5 distinct points. The percentages above each set of 5 points represent the percentage of nodes (which have the specified number of "pipe" nodes) adjacent to receiver nodes (which themselves do not take sense readings and are therefore not included in Figure 11). Thus, in the second test (the results of which are summarized in FIG. 11 ), each node is a conduit to between 0 and 12 other nodes, and, for example, there are 3 nodes that are conduits for 2 nodes node, out of those 3 nodes, only one node is adjacent to the sink, then 33% of the "2 pipes" nodes (one of the three nodes) are adjacent to the sink. Only one node is used as a conduit to 12 other nodes, and this node is adjacent to the sink, so 100% of the "12 conduit" nodes are adjacent to the sink. As mentioned above, Figure 11 shows the number of pipelines versus sensing rate results for 5 repeated runs (each using a different random number seed).

Thus, Figure 11 shows that the number of sensor readings made decreases as the connected-ness of the nodes increases. Nodes at the extremity of the network and thus not serving as conduits to other nodes collected 2500 to 3000 readings per 10000 epoch trial. Nodes with higher connectivity took fewer reads (eg, a pipeline for 3 nodes collected 1900 to 2100 reads, while a pipeline for 7 nodes collected 1400 to 1650 reads). Nodes adjacent to the receiver (e.g. 8, 10 and 12 pipeline nodes) deviate from this curve because they have higher values than expected.

These two findings can be explained by the fact that nodes used as pipes need to spend more time in "relay" mode to handle the increased data packet rate. Also nodes adjacent to the receiver have the benefit of being a constantly on node to which data packets can be sent. The receiver is not affected by battery drain like other nodes and is always available as a data receiver.

Alternative to the second embodiment

In order to increase the reader's overall understanding of the second embodiment, the following briefly describes the experimental apparatus that has been programmed to implement some of the features of the second embodiment. The device has been fabricated and tested as part of the Self-Organizing Collegiate Sensor (SECOAS) network project.

The 'algorithms' used in this test facility are actually a mix of decision making and data processing systems. For the purposes of this discussion, it is assumed that the data being processed has already undergone some initial preprocessing. For example, tidal currents can be measured by averaging a large number of tilt readings over time. Traditional measurement criteria related to the number of slope readings that need to be collected over a period of time convert "slope readings" into a single "flow" measurement. There are thus 3 decision-making components:

1. Sliding Window Averaging - A time "sliding window" of readings can be looked at to find sufficient removal conditions. Given a time series of sensor readings at t0, t1, t2, a simple analysis of the readings at t1 can determine how useful they are. If the reading of t1 is the average of the readings of t0 and t2, removing it will not have any effect on the characteristics of the time series, because its value can be obtained by interpolating from the readings of t0 and t2. Smaller amounts of deviation from this average are also acceptable if increased compression is desired. A balance must be struck between loss of information and compression. If you are concerned about losing too many sequence values, you can keep any values after the ones that were dropped, but this will obviously reduce compression to a maximum of 50%.

2. Local rules—monitoring of internal states that affect the frequency of certain actions, employing negative feedback to achieve homeostatic behavior. During a certain period of time, a node may perform no actions, or may perform one or more actions. These actions are eg sensing, forwarding and queue management. Each action has overhead in terms of queue occupancy, battery usage, and bandwidth usage. By monitoring the status of these resources, the probability of performing these actions can be changed. For example, if the queue length is near its maximum, it would be wise to do fewer reads and/or do more forwards, or, if the battery is being used at an unsustainable rate, high battery usage behavior should be reduced , while increasing the lower battery usage behavior. This is called "local learning".

3. Parameter Evolution - Genetic transplantation of internal parameters and fitness-based evolution enables well-behaved nodes to share their configuration with poorly-behaved nodes. Both Approach 1 and Approach 2 involve multiple parameters, values that affect performance (e.g. if a read from T1 is Z% larger or smaller than the average of the reads from T0, T2, delete the read from T1. If the queue exceeds Y, then delete The probability of sensing is reduced by X). Effective values for these parameters are found in advance using multi-parameter optimization of the simulated environment. But that's only likely to be as good as a simulated environment. By genetically encoding these parameters, node performance can be assessed and the genetic material of the "most fit" nodes diffused, while the genetic material making up the less fit nodes is modified or eliminated.

These methods can be used independently or in combination. Results on real datasets are discussed further below.

To obtain this dataset, a single buoy was set up that collected 6 channels of data for 7 days at 10 min intervals. The 6 channels are electrical conductivity (mS), temperature ('C), water depth (m), turbidity (g/l), slope 1 (mV) and slope 2 (mV). Due to the limitation of hardware, only the first three values are processed by this method, which will be explained below, and the other three values are directly stored in the recorder. Available elsewhere [see M. Shackleton, F. Saffre, R. Tateson, E. Bonsma and C. Roadknight: "Autonomic computing for pervasive ICT-a whole system approach" BTTJ Vol 22, No3, 2004; and C. Roadknight, "Sensor Network of Intelligent Devices", 1st European Workshop on Wireless Sensor Networks (EWSN′04), Berlin, 2004] for additional details on hardware and software setup.

It is important to assess how much impact the individual steps of the algorithm have, evaluating each element independently before looking at how they function when combined.

If we look at the sliding window removal method, it shows that the compression ratio increases as we increase the range over which the median is considered interpolable, but this varies with each data set. More complex algorithms exist to determine whether to remove the median of the 3 values (e.g. using the standard deviation of a longer time series), but as a simple preferred method, this is sufficient. Simplification is important not only for clarity, but also because the PIC microcontroller used for this configuration [PIC18FXX2 Data Sheet, Microchip Technology Inc, Document DS39564B, 2002] is not a powerful digital calculator and does advanced floating Point stats are way beyond their capabilities. Temperature is the least variable reading with similar values being frequently recorded. Water depths vary widely and are not predictable, so the sliding window method cannot safely remove many sounding readings.

The dropped values are resynthesized by taking the average of the previous and subsequent points, and then the actual error is calculated by referencing the original dropped values. For example, it is possible to have three consecutive depth readings at 10 minute intervals: 8.35, 8.525, 8.75 meters. Since the "difference from the mean" value is 50% (i.e., the difference between any one external reading and the mean is 8.75-8.55 = 8.55-8.35 = 0.2, 50% of 0.2 is 0.1, so if the actual reading is between 8.45 and 8.65), the median value is considered to be deleted, and when resynthesizing the resulting interval in the series by averaging the previous and subsequent values, an interpolation of 8.55 results, so that the deletion introduces an error of 0.025 meters. This is a simple way to estimate missing values, more sophisticated methods give better approximations. For 1008 measurements, an "allowed difference" of 50% would remove 38.4% of the readings and introduce an error of 13.45 meters, while an "allowed difference" of 1% would remove 13.5% of the readings and introduce 4.32 meters The error (about 0.043 cm per reading when the average reading is 9.13 meters).

The local learning part of the algorithm is more adaptive and works on different information, not interested in the values themselves, but in the effect of making and forwarding readings on the state of the node. The analysis shows how the probabilities of the 4 actions (sensing, forwarding, compressing, deleting) change and stabilize over time. For example, a node with sufficient battery and bandwidth can "suffer" from sensing nearly every possible reading and forward elements in its queue at a high rate. Fewer than one percent of the readings were removed or compressed. However, nodes that are more stressed have insufficient batteries to sense and relay every possible reading. Here, less than 30% of the possible number of readings are sent, and many of these data are compressed values consisting of the average of 2 or more readings. The advantage of local learning methods in sensor network environments is that specific information on battery usage and bandwidth availability is not required prior to experimentation, and since these factors are greatly influenced by environmental conditions, any estimates must generally be conservative. If experimental conditions are exceptionally good, non-adaptive methods will not be able to utilize unforeseen excesses in resources, conversely, if conditions are exceptionally bad, non-adaptive methods can be used without restriction in the initial stages of the experiment Insufficient resources, leaving no resources for the final phase. Adaptive methods, such as the proposed one, handle both cases well by changing their behavior accordingly.

Claims (13)

1. method of operating ad hoc network, this network comprises a plurality of equipment, each equipment in described a plurality of equipment all comprises communicator, and this communicator is used for when other equipment of described a plurality of equipment are positioned at scope and they communicate, and described method comprises:

One or more facility strategy of storage in each equipment, described facility strategy have stipulated to be used for determining the rule how equipment should move in response to various common environment;

Control each equipment to operate according in the facility strategy of described storage one or more;

On each equipment, store adaptability parameter;

Each equipment is all adjusted the value of storage described adaptability parameter thereon according to this relevant device with the tactful corresponding to validity rank of its storage;

Each equipment all monitor its storage adaptability parameter value with and the activity of communicator; And

Each equipment sends one or more of facility strategy of its storage all when its adaptability parameter surpasses threshold value and its communicator and need not be used for other purposes to other equipment that are arranged in its scope.

2. method according to claim 1, wherein, the rate of change of described adaptability parameter all depends on the quantity of other equipment of the scope that is positioned at relevant device at any time.

3. method according to claim 1 wherein, adopts broadcast mechanism to carry out the transmission of the facility strategy stored, so that the every other equipment in scope can receive described broadcast transmission.

4. any described method in requiring according to aforesaid right, wherein, described equipment is sensor device, and described ad hoc network forms sensor network, and wherein, described method comprises: before transmitting the sense data of being stored towards receiver node this sense data is carried out preliminary treatment, the place is put in order the data from a plurality of equipment at described receiver node, described preliminary treatment comprises optionally deletes one or more sensing reading, thereby reduces the data volume that needs forward direction to send.

5. method according to claim 4, wherein, the step of the sensing reading that selection will be deleted comprises: object sensing reading and two other sensing readings are handled, thereby produce estimation sensing reading according to described two other sensing readings, and should estimate that sensing reading and described object sensing reading compared, if this relatively indicates described object sensing reading and described estimation sensing reading in the acceptable limit of error each other, then delete described object sensing reading, otherwise do not delete.

6. method according to claim 5, this method also comprises: subsequently in the position away from the equipment of obtaining described object sensing reading, regenerate described estimation sensing reading, as the estimated value of the object sensing reading of being deleted.

7. equipment that is used to form ad hoc network, described network comprises a plurality of similar equipment, described equipment comprises:

Communicator, it is used for when other equipment of described a plurality of equipment are positioned at scope and they communicate;

Data storage device, it is used to store one or more facility strategy, and is used to store adaptability parameter, and described facility strategy has stipulated to be used for determining the rule how described equipment should move in varying environment; And

Processing unit, it is used for controlling described equipment to operate according to one or more of the facility strategy of described storage, be used for adjusting the value of the adaptability parameter of being stored with the tactful corresponding to activity level of being stored according to described equipment, be used for the value of the adaptability parameter stored and the activity of described communicator are monitored, and be used to make described communicator when described adaptability parameter surpasses threshold value and described communicator and need not be used for other purposes, send in the facility strategy of being stored one or more.

8. equipment according to claim 7, wherein, described processing unit can be operated and be used for regulating according to predetermined function the value of the adaptability parameter of being stored, this function depends on described equipment and tactful corresponding to activity level that stored, and depends on the quantity of other equipment of the scope of being positioned at.

9. according to claim 7 or 8 described equipment, this equipment comprises at least one transducer, and wherein, described processing unit also can be operated and be used for transmit the sense data of being stored that described transducer collects towards receiver node before these data being carried out preliminary treatment, the place is put in order the data from a plurality of equipment at described receiver node, described preliminary treatment comprises optionally deletes one or more sensing reading, thereby reduces the data volume that needs forward direction to send.

10. equipment according to claim 9, wherein, described processing unit can be operated and be used for selecting the sensing reading that will delete by object sensing reading and two other sensing readings are handled, described processing comprises: generate according to described two other sensing readings and estimate the sensing reading, should estimate that sensing reading and described object sensing reading compared, if this relatively indicates described object sensing reading and described estimation sensing reading in the acceptable limit of error each other, then delete described object sensing reading, otherwise do not delete.

11. an equipment that is used to form ad hoc network, described equipment comprises:

Transceiver, it is used for communicating with other similar devices;

Data storage, it stores one or more facility strategy, and the storage adaptability parameter, and described facility strategy has stipulated to be used for determining the rule how described equipment should move in varying environment; And

The electronic digit processor, it can be operated and be used for: control described equipment to operate according in the facility strategy of being stored one or more; Adjust the value of the adaptability parameter of being stored according to described equipment with the tactful corresponding to activity level of being stored; The value of the adaptability parameter stored and the activity of described communicator are monitored; And make described transceiver when described adaptability parameter surpasses threshold value and described transceiver and need not be used for other purposes, send in the facility strategy of being stored one or more.

12. an ad hoc network, this ad hoc network comprise a plurality of according to any described equipment in the claim 7 to 11.

13. method of operating ad hoc network, described network comprises a plurality of equipment, each equipment in described a plurality of equipment all comprises communicator, and this communicator is used for when other equipment of described a plurality of equipment are positioned at scope and they communicate, and described method comprises:

One or more facility strategy of storage in each equipment, described facility strategy have stipulated to be used for determining the rule how equipment should move in response to various common environment;

Control each equipment to operate according in the facility strategy of described storage one or more;

On each equipment, store adaptability parameter;

Each equipment is all adjusted the value of storage described adaptability parameter thereon according to this relevant device with the tactful corresponding to activity level of its storage;

Each equipment all monitor its storage adaptability parameter value with and the activity of communicator; And

Each equipment is all when its adaptability parameter surpasses threshold value, send one or more of facility strategy of its storage to other equipment that are arranged in scope, the rate of change of wherein said adaptability parameter all depends on the quantity of other equipment of the scope that is positioned at described relevant device at any time.

Images