CN101815326B - Method for allocating tasks in wireless sensor network based on negotiation - Google Patents

Abstract

The invention discloses a negotiation-based wireless sensor network task assignment method, which includes the following steps: a node in the wireless sensor network issues a bidding notice as a bidder, and waits for bidders to bid; The degree of completion and its current remaining energy determine whether to participate in the bidding, and the nodes that decide to participate in the bidding act as bidders to bid for each attribute of the task to be assigned; the bidder uses a multi-attribute utility function to evaluate each bidder in the negotiation process with the bidder , and select an objective. In the process of task allocation, the present invention takes factors such as the remaining power of the node and the expected energy consumption of the task into consideration, and uses a multi-attribute utility function to evaluate the pros and cons of the allocation scheme, improves the comprehensive utility value of the allocation, and integrates the instant success strategy, round The fuzzy strategy and no-failure strategy are integrated into the MAS auto-negotiation algorithm, which improves the real-time performance, flexibility and success rate of task assignment.

Description

Negotiation-Based Task Allocation Method for Wireless Sensor Networks

technical field

The invention relates to the field of wireless sensor networks, in particular to a negotiation-based wireless sensor network task allocation method.

Background technique

After the emergence of wireless sensor networks, its application field has expanded from the initial military field to many other fields, and it can complete tasks that traditional systems such as disaster warning and rescue, family health detection, and space exploration cannot complete. Task assignment in sensor networks is a long-standing research field. Since wireless sensor networks are generally deployed with little manual management and intervention, there is a need for autonomous task allocation. At present, the relevant wireless sensor network task allocation algorithms focus more on the task cooperation between multiple nodes, and consider the joint completion of tasks through the cooperation between nodes so as to reduce energy consumption and communication traffic. At present, there is no method that specifically considers the fast and efficient allocation of current tasks when a single node is about to fail. Wireless sensor nodes are prone to failure. When a node that is performing a task detects that it is about to fail due to energy depletion and other reasons, it is very important to find a fast, low-consumption and high success rate method to seek a task successor. necessary.

According to the patent search of the State Intellectual Property Office, the technology related to the present invention is retrieved as a Chinese patent application as follows: the application number is 200810236555.0, and the name is "a method for allocating energy-saving mobile Agent multi-step negotiation tasks". This technology adopts the multi-step negotiation method for mobile Agent-oriented task assignment, and the algorithm adopted is the improved MAS (Multi-Agent System, Multi-Agent System) automatic negotiation algorithm. In terms of time consumption and power consumption, which are both concerned in task assignment, the attention to power consumption cannot be effectively reflected.

Specifically, in the technical solution provided in the patent application "A Multi-step Negotiation Task Allocation Method for Energy-saving Mobile Agent", multiple negotiations are performed based on the task consumption of MA (Mobile Agent, Mobile Agent), so The obtained task assignment results are not fixed, and will change with the dynamic changes of MANET (Mobile Ad hoc Network, mobile ad hoc network) network topology. In the method proposed by the present invention, each MA negotiates with other MAs based on the current system consumption, and in one negotiation, one MA is assigned only one task. When they complete their assigned tasks, they negotiate again based on the task consumption at the current time, and each MA is assigned to the next task until all tasks are completed. This method ensures that each MA is assigned only one task in each step of negotiation, which can reduce the time consumption of the entire cooperation system, reduce the power consumption of equipment, and thus prolong the survival time of the network.

Therefore, it can be seen that the technical solution disclosed in this patent application adopts a multi-step negotiation method for task allocation, which has relatively large communication volume and high energy consumption, and is not suitable for real-time allocation of node tasks.

However, the traditional task assignment method is to analyze the energy consumption after assigning tasks, resulting in a disjointed analysis of the interaction between task completion and energy consumption in the task assignment process of wireless sensor networks, and cannot effectively achieve the task During the allocation process, the impact of the expected energy consumption of tasks and the current energy of sensor nodes on task allocation is reflected.

Contents of the invention

The purpose of the present invention is to address the defects and deficiencies in the prior art, and to provide a wireless sensor network node that is performing tasks when it detects that it is about to fail due to energy depletion and other reasons, which can autonomously fast and low-consumption It also seeks a task successor with a high success rate, and at the same time, when evaluating the utility of the bidder in the negotiation algorithm in the allocation process, it fully considers the expected energy consumption of the task and the current remaining energy of the sensor node and other factors.

In order to achieve the above object, the present invention provides a negotiation-based WSN task assignment method, said method comprising the following steps:

S1, the node in the wireless sensor network serves as the tenderer to issue a tender notice, waiting for the bidder to bid;

S2. The node that receives the bidding invitation decides whether to participate in the bidding according to the completion degree of the task to be assigned and its current remaining energy, and the node that decides to participate in the bidding acts as the bidder to bid for each attribute of the task to be assigned;

S3, the tenderer uses a multi-attribute utility function to evaluate the bidding schemes of each bidder in the negotiation process with the bidder, and then selects the bid.

Wherein, the method further includes a step: S4, assigning tasks to the selected bidders, and sending a task assignment notification to all bidders.

Among them, in step S1, the principle followed by the tenderee waiting for bids from bidders is as follows: in the process of waiting for bidders to bid, the tenderee does not distinguish between bidding rounds, and does not wait for all bidders in each round to complete their bids before choosing to bid It also supports the dynamic joining and leaving of nodes during the bidding process.

Wherein, the bidding notice in step S1 is designed according to the multi-attribute utility function, and the designed bidding notice Notice includes the following contents:

Notice＝{P(p ₁ , p ₂ ,...p _N ), W(w ₁ , w ₂ ,...w _N ), LT, T _feedback , U _threshold },

in,

P(p ₁ , p ₂ ,...p _N ) is a task attribute vector, where p ₁ ,..., p _N are the N attributes concerned by the task to be assigned, and N is a positive integer;

W(w ₁ , w ₂ ,…w _N ) is the task weight vector, w ₁ ,……, w _N respectively correspond to the importance weight of each attribute in the task attribute vector,

LT is the deadline for the bidder to select bidders for the last time in a bidding round;

T _feedback is the time for bidders to wait for the bid-winning notice before proceeding to the next round of bidding;

U _threshold is the maximum threshold value of the utility value preset by the bidding party.

Wherein, step S3 is specifically:

When a bidder bids, it is judged whether the bid is greater than or equal to the maximum threshold value U _threshold of the utility value. If so, the bidder is selected as the bid and the bid winning notice is issued; otherwise, it is judged whether the deadline LT has been reached , if so, select the bid from all the current bids according to the utility value calculated by using the multi-attribute utility function, and issue a bid winning notice, otherwise, the tenderee marks the current bid with the highest utility value and continues to wait for a new bid;

Among them, the multi-attribute utility function is:

N是招标过程中需要协商的属性的个数，O_j ⁱ是第i个竞标方针对任务属性向量中的第j个属性的出价值，j∈[1，N]，该属性至少包括对待分配任务的可完成度和耗电量，In the above formula, the bid vector

N is the number of attributes that need to be negotiated in the bidding process, O _j ⁱ is the bid value of the i-th bidder for the j-th attribute in the task attribute vector, j∈[1, N], this attribute includes at least Task completion and power consumption,

w _j ⁱ is the importance weight of the i-th bidding party for the j-th attribute in the task attribute vector, v _j ⁱ is the evaluation function value of the i-th bidding party for the j-th attribute in the task attribute vector,

The w value is specified by the bidding party, and the v value indicates the degree of completion of the task to be assigned given by the bidding party, the satisfaction degree of the bidding party, and the v value is calculated by the following method:

max，min分别表示招标方对于该任务的最大、最小期望值；When the tenderer’s satisfaction decreases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

max and min respectively represent the maximum and minimum expectations of the tenderer for the task;

When the tenderer’s satisfaction increases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

The above-mentioned technical solution has the following advantages: 1. It solves the phenomenon that task allocation and energy consumption analysis are separated during the task allocation process of the wireless sensor network, and factors such as the remaining power of the node and the expected energy consumption of the task are taken into account during the task allocation process; 2. The multi-attribute utility function is used to evaluate the pros and cons of the allocation scheme, which improves the comprehensive utility value of the allocation; 3. The instant success strategy, the round fuzzy strategy and the no-failure strategy are integrated into the MAS automatic negotiation algorithm, which improves the real-time task allocation flexibility, flexibility and success rate.

Description of drawings

Fig. 1 is the method flowchart of the embodiment of the present invention;

Fig. 2 is a flow chart of the decision-making process of the bidding party in the method of the embodiment of the present invention.

Detailed ways

The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

The flow chart of the method according to the embodiment of the present invention is shown in Figure 1, including the following steps:

101. When a node is about to fail due to battery energy exhaustion or other reasons, it hopes to find a new node to replace itself to complete the current task. At this time, it sends a message to the same cluster nodes on the same layer, hoping to allocate tasks.

Nodes that want to assign tasks first issue a bidding notice, which includes the purpose of the negotiation, the preferred attribute structure, the value range and the deadline.

When a task allocation requirement is generated, the task issuing unit issues a task bidding notice, which is designed by an improved bidding algorithm combined with multi-attribute utility functions. The task release model is as follows:

Notice＝{P(p ₁ , p ₂ ,...p _N ), W(w ₁ , w ₂ ,...w _N ), LT, T _feedback , U _threshold }, Notice is a tender notice, which includes the following five items.

P(p ₁ , p ₂ ,...p _N ) is the task attribute vector, where p ₁ is the main attention attribute, p ₂ is the secondary attention attribute, p _N is the Nth attention attribute, from p ₁ to p _N , the attribute in descending order of importance.

W(w ₁ , w ₂ ,...w _N ) is the task weight vector, corresponding to the corresponding weight of each attribute in the task attribute vector,

LT (LastTime) is the deadline for the tenderee to make the last selection in a tender.

T _feedback , the bidder waits for the T _feedback time by default, and if there is no notification of winning the bid, the bidder will make the next round of bidding within his acceptable range.

U _threshold , a threshold value for the instant success of the selected target. When there is a bid greater than or equal to this value, the instant success strategy is adopted to improve the bidding efficiency. The "instant success" strategy is explained in step 203 .

102. The sensor nodes that have received the bidding invitation decide whether to participate in the bidding according to their own estimates of the task completion capability and energy maintenance. Bidders who decide to participate place bids on the individual attributes of the task to be assigned.

The tenderee adopts a certain strategy to evaluate the supplier's bid, and selects the utility optimal bid that conforms to the preference attribute weight as the winning bidder. The decision-making process (that is, the evaluation strategy adopted) is shown in Figure 2.

201. Waiting for bids from bidders: the round fuzzy strategy is followed in the process of waiting for bidding nodes to bid. The definition of "round fuzzy strategy" is: there is no need to clearly distinguish the bidding rounds, and there is no need to wait for all bidders in each round to complete the bidding before making a judgment and selection, and it also supports the dynamic joining and leaving of nodes during the bidding process.

202. Evaluate all current bidding schemes: use a multi-attribute utility function to evaluate the pros and cons of each bidder's bidding scheme in the negotiation process. In the design of the multi-attribute utility function, multiple factors that need to be considered in task assignment are combined into a bid vector, in which the task attribute is taken as the first component in the vector, and the attributes are arranged in order from high to low according to the degree of attention to the attribute. various components. The utility value of each bidding scheme is calculated by combining the task weight vector issued at the same time as the node publishes the task. The multi-attribute utility function designed by the method of this embodiment is as follows:

I: bid vector

N is the number of attributes that need to be negotiated in the bidding. O _j ⁱ (j∈[1, N]) is the bidding value of the i-th bidder for the j-th attribute in the task attribute vector. Attributes can be price, quality, payment time, etc. in the traditional field, and can be the completion of a certain task, power consumption, etc. in the sensor network.

II: Utility function

w _j ⁱ is the importance weight of the i-th bidding party for the j-th attribute in the task attribute vector. The weights are divided by full probability, that is, v _j ⁱ is the evaluation function value of the i-th bidding party for the j-th attribute in the task attribute vector. This embodiment of the method only involves the situation that there is only one bidding party.

The value of w is directly specified by the bidding party. The v value indicates the degree of completion of each task given by the bidder, corresponding to the satisfaction of the bidder for the task. Calculated according to the bid vector using the following formula:

max，min分别表示招标方对于该任务的最大、最小期望值；When the tenderer’s satisfaction decreases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

max and min respectively represent the maximum and minimum expectations of the tenderer for the task;

When the tenderer’s satisfaction increases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

根据该函数可计算出效用值。Therefore, the multi-attribute utility function of the bid vector O ⁱ can be obtained as

The utility value can be calculated according to this function.

203. Select the highest utility solution according to the "instant success" strategy, so as to improve the efficiency of task allocation. The bidding party first draws up a utility value U _threshold , which will not be published. The bidding party does not need to wait for the end of each round or strictly follow the traditional bidding step design to select the bid. If there is a calculated utility value U>= U _threshold , choose the highest bid that is greater than or equal to this value, immediately issue a receiving order, sign an agreement with the corresponding bidder, and successfully end this bidding. Instead of having to wait for the end of a bidding round or wait until there are no higher bids to end negotiations. In this way, a balance is maintained between utility and efficiency of task assignment. If no such utility value exists, wait for bidders to continue bidding.

204. When the deadline LT is reached: adopt the no-failure strategy to improve the success rate of task allocation, that is, the set deadline is not the end time of the bidding, but the last choice before the end at this moment, so as to ensure that there will be no failure of the bidding In this case, as long as there are currently bids, even if the satisfaction of all bids does not meet the preset requirements, the bid with the highest utility value among all current bids should be selected to complete this task assignment.

After the bidding scheme is selected, the task assignment node authorizes the task to the winning node. After the task is authorized, the entire task assignment is completed. Then send a task allocation notice to all bidders, and the entire negotiation process ends.

It should be noted that, in the embodiment of the present invention, each sensor node is considered as an Agent, and the nodes that need to assign tasks are called bidders, and those who participate in the competition and want to obtain the task execution right are called bidders.

An example is given below: when sensor node a needs to assign tasks, it will issue a bidding notice, and then wait for each participant to bid, that is, start the negotiation process of task assignment. The whole steps include:

1. After a certain bid is placed, first judge whether the current bid reaches or exceeds the immediate maximum utility value U _threshold ,

2.1. If yes, the bid winning notice will be issued, the bidding will be terminated immediately, and the bidding will be announced to be over.

2.2. Otherwise, judge whether the maximum negotiation time LT has been reached at this time,

3.1. When the current bid reaches LT, select the most satisfactory offer (target) according to the utility function and rules in the current bid, issue a bid winning notice, and announce the end of the bidding;

3.2. If the maximum negotiation time LT is not reached at this time, the bidder will mark the bid offer with the highest utility value at the moment, and continue to wait for the bid. The next round of bidding that continues to increase the price without receiving feedback after a certain time delay T _feedback . Then proceed to step 1 in a loop.

If a bidder leaves (withdraws) during the bidding process, it must go back to 3.1.

设招标方对于任务属性负荷x的期望值区间为：[100，200]，其满意度随负荷值增大而递增；对于任务属性耗电量y的期望区间为：[0，100]，其满意度随耗电量减少而递减。即The pros and cons of each round of bidding schemes in the negotiation process are judged by the multi-attribute utility function: Assume that the bidding notice issued by sensor node a includes two negotiation attributes: load x and power consumption y; maximum negotiation time LT; The immediate termination utility value U _threshold . That is, the bid vector is (x, y). The weight of load x is 0.8, and the weight of power consumption y is 0.2, namely

Assume that the tenderee’s expected range of task attribute load x is: [100, 200], and its satisfaction increases with the increase of the load value; the expected interval of task attribute power consumption y is: [0, 100], its satisfaction The speed decreases as the power consumption decreases. Right now

${\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; x</span>}}{\mathrm{<span\; class="notranslate">\; 200</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 100</span>}}$

${\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; a</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}}{\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 0</span>}}$

In the specific application of the above method, there are some other explanations and limitations on the multi-attribute utility function as follows:

The total value of preference is the largest;

Satisfaction of main attribute a > satisfaction of secondary attribute b;

When the total preference value is the same, choose the offer with high satisfaction.

If at this time sensor node a receives several bids shown in Table 1 at the same time, and calculates the multi-attribute utility of these bids.

Table 1

bid vector(x, y) Multi-attribute utility value U Offer1 (180, 30) 0.76 Offer2 (188, 12) 0.88 Offer3 (190, 20) 0.88 Offer4 (195, 45) 0.87

According to the above rules, it can be seen that although the satisfaction of attribute x of offer4 is very high, its total utility value is lower than that of offer2 and offer3 due to the low satisfaction of attribute y, and when the utility values of offer2 and offer3 are the same, choose The group with higher satisfaction of attribute x, that is, the best offer selected among the 4 offers in this round is offer3(190, 20).

The foregoing is only an embodiment of the present invention. It should be pointed out that for those of ordinary skill in the art, some improvements and modifications can be made without departing from the technical principle of the present invention. It should be regarded as the protection scope of the present invention.

Claims (4)

1. A wireless sensor network task assignment method based on negotiation, is characterized in that, described method comprises the following steps: S1, the node in the wireless sensor network serves as the tenderer to issue a tender notice, waiting for the bidder to bid; S2. The node that receives the bidding invitation decides whether to participate in the bidding according to the completion degree of the task to be assigned and its current remaining energy, and the node that decides to participate in the bidding acts as the bidder to bid for each attribute of the task to be assigned; S3, the tenderer uses a multi-attribute utility function to evaluate the bidding schemes of each bidder in the negotiation process with the bidder, and then selects the bid; The bidding notice in step S1 is designed according to the multi-attribute utility function, and the designed bidding notice Notice includes the following contents: Notice＝{P(p ₁ , p ₂ ,...p _N ), W(w ₁ , w ₂ ,...w _N ), LT, T _feedback , U _threshold }, where, P(p ₁ , p ₂ ,...p _N ) is a task attribute vector, where p ₁ ,...,p _N are the N attributes concerned by the task to be assigned, and N is a positive integer; W(w ₁ ,w ₂ ,…w _N ) is the task weight vector, w ₁ ,…,w _N respectively correspond to the importance weight of each attribute in the task attribute vector,

LT is the deadline for the bidder to select bidders for the last time in a bidding round; T _feedback is the time for bidders to wait for the bid-winning notice before proceeding to the next round of bidding; U _threshold is the maximum threshold value of the utility value preset by the bidding party. 2. The negotiation-based wireless sensor network task assignment method according to claim 1, further comprising a step: S4, assigning tasks to the selected bidders, and sending a task assignment notification to all bidders. 3. The wireless sensor network task assignment method based on negotiation as claimed in claim 1 or 2, characterized in that, in step S1, the principle that the bidding party waits for the bidding party to bid is as follows: in the process that the bidding party waits for the bidding party to bid , does not distinguish between bidding rounds, and does not wait for all bidders in each round to complete their bidding before selecting bidders. It also supports dynamic joining and leaving of nodes during the bidding process. 4. The negotiation-based wireless sensor network task assignment method according to claim 1 or 2, wherein step S3 is specifically: When a bidder bids, it is judged whether the bid is greater than or equal to the maximum threshold value U _threshold of the utility value. If so, the bidder is selected as the bid and the bid winning notice is issued; otherwise, it is judged whether the deadline LT has been reached , if so, select the bid from all the current bids according to the utility value calculated by using the multi-attribute utility function, and issue a bid winning notice, otherwise, the tenderee marks the current bid with the highest utility value and continues to wait for a new bid; Among them, the multi-attribute utility function is: $u\left(o^i\right)=\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}{w^i}_j{v^i}_j,$ In the above formula, the bid vector N is the number of attributes that need to be negotiated in the bidding process,

is the bid value of the i-th bidder for the j-th attribute in the task attribute vector, j∈[1, N], this attribute at least includes the completion degree and power consumption of the task to be assigned, w ⁱ _j is the importance weight of the i-th bidding party for the j-th attribute in the task attribute vector, v ⁱ _j is the evaluation function value of the i-th bidding party for the j-th attribute in the task attribute vector, The w value is specified by the bidding party, and the v value indicates the degree of completion of the task to be assigned given by the bidding party, the satisfaction degree of the bidding party, and the v value is calculated by the following method: When the tenderer’s satisfaction decreases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

max and min respectively represent the maximum and minimum expectations of the tenderer for the task; When the tenderer’s satisfaction increases with the increase of the bid O _j for the jth attribute, the tenderer’s satisfaction with the jth attribute

Images