CN101815326B - 基于协商的无线传感器网络任务分配方法 - Google Patents

Abstract

本发明公开了一种基于协商的无线传感器网络任务分配方法，包括以下步骤：无线传感器网络中的节点作为招标方发布招标启事，等待竞标方出价；收到竞标邀请的节点根据对待分配任务的可完成度以及其当前剩余能量来决定是否参与竞标，决定参与竞标的节点作为竞标方就待分配任务的各个属性进行出价；招标方采用多属性效用函数来评价与竞标方的协商过程中各竞标方的出价方案，然后选择标的。本发明在任务分配过程中就考虑到了节点的剩余电量和任务预期能耗等因素，采用多属性效用函数来评价分配方案的优劣，提高了分配的综合效用值，把即时成功策略、轮次模糊策略和无失败策略融入到MAS自动协商算法中，提高了任务分配的实时性，灵活性和成功率。

Description

基于协商的无线传感器网络任务分配方法

技术领域

本发明涉及无线传感器网络领域，尤其涉及一种基于协商的无线传感器网络任务分配方法。

背景技术

无线传感器网络出现后，其应用领域已经由最初的军事领域扩展到其他许多领域，能够完成诸如灾难预警与救助、家庭健康检测、空间探索等传统系统无法完成的任务。传感器网络中的任务分配是一个历久弥新的研究领域。由于无线传感器网络一般都是部署之后就基本很少人工进行管理和干预，所以就产生自主任务分配的需求。目前有关的无线传感器网络任务分配算法更多是关注多个节点之间的任务协作，考虑的是通过节点之间的协作来共同完成任务从而降低能耗、通信量等。目前还没有一种方法专门考虑单个节点即将失效时的快速有效的对当前任务的分配。无线传感器节点很容易失效，当一个正在执行任务的节点监测到自己由于能量即将耗尽等原因即将失效时，找到一种能够快速、低耗又成功率高的寻求一个任务接替者的方法是非常必要的。

根据国家知识产权局的专利搜索，检索到与本发明较为相关的技术为如下的一项中国专利申请：申请号为200810236555.0，名称为”一种面向节能的移动Agent多步协商任务分配方法”。该技术采用多步协商方法的面向移动Agent的任务分配，采用的算法是经过改进的MAS(Multi-Agent System，多Agent系统)自动协商算法。在任务分配中都关注的时间消耗和电量消耗方面，不能有效地体现对电量消耗的关注。

具体来说，该在专利申请“一种面向节能的移动Agent多步协商任务分配方法”所提供的技术方案中，以MA(Mobile Agent，移动Agent)的任务消耗为基础进行多次协商，所得到的任务分配结果是不固定的，而且会随着MANET(Mobile Ad hoc Network，移动自组网)网络拓扑结构的动态变化而变化。在本发明提出的方法中，每个MA与其他MA在基于当时的系统消耗下进行协商，并且在一次协商中，一个MA只分配到一个任务。当它们完成各自分配的任务后，它们重新以当前时间的任务消耗为基础再次进行协商，每个MA分配到下一个任务，直到所有任务都完成。该方法保证了每个MA在每一步协商中只分配到一个任务，这样做能减少整个合作系统的时间消耗，减少设备电量消耗，从而延长网络的生存时间。

因此可以看出，该专利申请所公开的技术方案采用多步协商的方法进行任务分配，通信量比较大，能耗较高，不适合节点任务的实时分配。

而传统的任务分配方法都是在分配任务之后才进行能耗的分析，造成了对于无线传感器网络任务分配过程中对任务完成度和能量损耗相互影响作用分析的脱节，不能有效的做到在任务分配过程中就体现出任务预期能耗和传感器节点当前能量对任务分配的影响。

发明内容

本发明的目的是针对现有技术中存在的缺陷和不足，提供一种当一个正在执行任务的无线传感器网络节点监测到自己由于能量即将耗尽等原因即将失效时，能够自主的快速、低耗又成功率高地寻求到一个任务接替者，同时在分配过程中的协商算法中对竞标方的效用进行评价时充分的考虑到任务预期能耗和传感器节点当前剩余能量等因素的任务分配方案。

为达到上述目的，本发明提供了一种基于协商的无线传感器网络任务分配方法，所述方法包括以下步骤：

S1，无线传感器网络中的节点作为招标方发布招标启事，等待竞标方出价；

S2，收到竞标邀请的节点根据对待分配任务的可完成度以及其当前剩余能量来决定是否参与竞标，决定参与竞标的节点作为竞标方就待分配任务的各个属性进行出价；

S3，招标方采用多属性效用函数来评价与竞标方的协商过程中各竞标方的出价方案，然后选择标的。

其中，该方法还包括步骤：S4，给所选择的竞标方分配任务，并给所有的竞标方发任务已分配通知。

其中，在步骤S1中招标方等待竞标方出价所遵循的原则如下：在招标方等待竞标方出价的过程中，不区分投标轮次，且不等待每一轮所有竞标方投标结束后再选择竞标方，也支持招标过程中节点的动态加入和离开。

其中，在步骤S1中的招标启事按照多属性效用函数进行设计，所设计的招标启事Notice包括以下内容：

Notice＝{P(p₁，p₂，…p_N)，W(w₁，w₂，…w_N)，LT，T_feedback，U_threshold}，

其中，

P(p₁，p₂，…p_N)是任务属性向量，其中p₁，………，p_N是待分配任务所关注的N个属性，N为正整数；

W(w₁，w₂，…w_N)是任务权重向量，w₁，………，w_N分别对应任务属性向量中每个属性的重要性权值，

LT是招标方在一个招标轮次中最后一次选择竞标方的截止时间；

T_feedback是竞标方进行下一轮出价前等待中标通知的时间；

U_threshold是招标方预设的效用值的最大门限值。

其中，步骤S3具体为：

当一个竞标方出价后，即判断该出价是否大于或等于效用值的最大门限值U_threshold，若是，则选择该竞标方为标的，并发布中标通知；否则判断此时是否已到达截止时间LT，若是，则在当前的所有竞标方的出价中根据采用多属性效用函数计算的效用值选择标的，并发布中标通知，否则，招标方标记当前的效用值最大的出价，继续等待新的出价；

其中，多属性效用函数为：

上式中，出价向量

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

w_j ⁱ是第i个招标方针对任务属性向量中的第j个属性的重要性权值，v_j ⁱ是对第i个招标方针对任务属性向量中的第j个属性的评价函数值，

w值是由招标方指定的，v值表示对于竞标方给出的对于待分配任务的可完成度，招标方的满意度，v值通过以下方式计算：

当招标方的满意度随对第j个属性的出价O_j的提高而降低时，招标方对第j个属性的满意度

max，min分别表示招标方对于该任务的最大、最小期望值；

当招标方的满意度随对第j个属性的出价O_j的提高而提高时，招标方对第j个属性的满意度

上述技术方案具有如下优点：1、解决了无线传感器网络任务分配过程中任务分配和能耗分析脱离的现象，在任务分配过程中就考虑到了节点的剩余电量和任务预期能耗等因素；2、采用多属性效用函数来评价分配方案的优劣，提高了分配的综合效用值；3、把即时成功策略、轮次模糊策略和无失败策略融入到MAS自动协商算法中，提高了任务分配的实时性，灵活性和成功率。

附图说明

图1是本发明实施例的方法流程图；

图2是本发明实施例的方法中招标方的决策过程流程图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

依据本发明实施例的方法流程图如图1所示，包括如下步骤：

101，当一个节点因为电池能量耗尽或者其他原因即将失效时希望找到一个新的节点来代替自己完成目前承担的任务，此时它向同层的同簇节点发布消息，希望进行任务分配。

要进行任务分配的节点首先发布招标启事，其中包括此次协商的目的任务、偏好的属性结构以及取值范围和截止时间。

当产生任务分配需求的时候，由任务发布单元发布任务招标启事，任务招标启事是由结合多属性效用函数改进的招标算法而设计的。任务发布模型如下：

Notice＝{P(p₁，p₂，…p_N)，W(w₁，w₂，…w_N)，LT，T_feedback，U_threshold}，Notice为招标启事，其中包含如下五项内容。

P(p₁，p₂，…p_N)是任务属性向量，其中p₁是主要关注属性，p₂是次要关注属性，p_N是第N关注属性，从p₁～p_N，属性的重要性依次递减。

W(w₁，w₂，…w_N)是任务权重向量，分别对应任务属性向量中每个属性相应的权重，

LT(LastTime)是招标方在一次招标中进行最后一次选择的截止时间。

T_feedback，竞标方默认等待T_feedback时间后如果没有中标通知就在自己可接受范围内进行下一轮出价。

U_threshold，选中标的即时成功的一个门限值。出现大于等于此值的投标时就采用即时成功策略，提高招标效率，“即时成功”的策略在步骤203中解释。

102，收到竞标邀请的传感器节点根据各自对任务完成能力和维持能量等方面的估算来决定是否参与竞标。决定参与的竞拍方就待分配任务的各个属性进行出价。

招标方采用一定的策略对供应商的投标进行评价，选择符合偏好属性权重的效用最优投标作为中标者，该决策过程(即所采取的评价策略)如图2所示。

201，等待竞标方出价：在等待竞标节点出价的过程中遵循的是轮次模糊策略。“轮次模糊策略”的定义为：不需要明确地区分投标轮次，不用等待每一轮所有竞标方投标结束后再进行判断选择，也支持招标过程中节点的动态加入和离开。

202，评价当前所有的投标方案：采用多属性效用函数来评价协商过程中各竞标方出价方案的优劣。在多属性效用函数的设计中把任务分配中需要考虑的多个因素组合成一个出价向量，其中任务属性作为向量中第一个分量，根据对属性的关注程度由高到低依次向后排开各个分量。结合在节点发布任务的同时发布的任务权重向量来计算每个出价方案的效用值。本实施例方法设计的多属性效用函数如下：

I：出价向量

N是招标中需要协商的属性个数。O_j ⁱ(j∈[1，N])是第i个竞标方针对任务属性向量中的第j个属性的出价值。属性在传统领域里可以是价格，质量，付款时间等，在传感器网络中可以是某个任务的完成度，耗电量等。

II：效用函数

w_j ⁱ是第i个招标方针对任务属性向量中的第j个属性的重要性权值。权值是全概率划分的，即v_j ⁱ对第i个招标方针对任务属性向量中的第j个属性的评价函数值。本方法实施例只涉及只有一个招标方的情况。

w值是由招标方直接指定。v值表示竞标方给出的对于每个任务的可完成度，对应招标方针对该任务的满意度。根据出价向量利用如下公式计算而得：

当招标方的满意度随对第j个属性的出价O_j的提高而降低时，招标方对第j个属性的满意度

max，min分别表示招标方对于该任务的最大、最小期望值；

当招标方的满意度随对第j个属性的出价O_j的提高而提高时，招标方对第j个属性的满意度

因此可以得到出价向量Oⁱ的多属性效用函数是

根据该函数可计算出效用值。

203，根据“即时成功”的策略选择最高效用方案，以提高任务分配的效率。招标方首先自拟一个效用值U_threshold，该值不进行公布，招标方不用等待每个轮次的结束或者严格遵循传统招标的步骤设计来选定标的，如果存在计算出的效用值U＞＝U_threshold，就选择大于等于此值的那个最高值的出价，立即发出接收命令，和相应竞标方签订协议，成功结束本次招标。而不用必须等待一个招标轮次的结束或者一直等到没有更高出价方案才结束协商。这样，在任务分配的效用和效率间维持了平衡。如果不存在这样的效用值，则等待竞标方继续投标。

204，到达截止时间LT时：为提高任务分配成功率采用无失败策略，即设定的截止时间不是招标结束时间，而是在此刻进行结束前的最后一次选择，这样能保证不出现招标失败的情况，只要当前有投标出现，即使所有投标满意度没有达到预设要求，也要选择当前所有投标中效用值最高的投标来完成本次任务分配。

选中投标方案后，任务分配节点就把任务授权给中标的节点。任务授权后，整个任务分配完成。然后发任务分配通知给所有的竞标方，整个协商过程结束。

需要说明的是，本发明实施例中，把每一个传感器节点都当做一个Agent来考虑的，其中需要分配任务的节点称为招标方，参与竞争想要获得任务执行权的称为竞标方。

以下举一实例：在传感器节点a需要进行任务分配时，就发布招标启事，然后等待各参与者竞标，即开始任务分配的协商过程，整个步骤包括：

1、在某个出价出后，首先判断当前投标是否达到或超过即时最大效用值U_threshold，

2.1、是则发布中标通知，即时终止招标，宣布招标结束。

2.2、否则判断此时是否到达最大协商时间LT，

3.1、当前达到LT时，则在当前出价中根据效用函数及规则选取目前最满意的offer(标的)，发布中标通知，宣布招标结束；

3.2、如果此时没有达到最大协商时间LT，则投标方标记当前的效用值最大的投标offer，继续等待投标，新的投标包括可能新加入的竞标方的投标或者是前一轮的投标者在一定时延T_feedback后没有收到反馈而继续加价的下一轮投标。然后至步骤1循环进行。

招标过程中如果出现竞标方离开(撤标)，则要重新回到3.1处进行。

对于协商过程中每一轮出价方案的优劣采用多属性效用函数进行评判：假设在传感器节点a发布的招标启事中包括两个协商属性：括负荷x和耗电量y；最大协商时间LT；即时终止效用值U_threshold。即出价向量是(x，y)。负荷x的权值是0.8，耗电量y的权值是0.2，即

设招标方对于任务属性负荷x的期望值区间为：[100，200]，其满意度随负荷值增大而递增；对于任务属性耗电量y的期望区间为：[0，100]，其满意度随耗电量减少而递减。即

$v_x^a=1-\frac{200-x}{200-100}$

$v_y^a=\frac{100-y}{100-0}$

上述方法的具体应用中有如下对多属性效用函数的其他一些说明与限定：

偏好总值最大；

主属性a的满意度＞次属性b的满意度；

偏好总值相同时选择a满意度高的offer。

如果此时传感器节点a同时收到表1中所示的几个投标，并且计算这些出价的多属性效用。

表1

	出价向量(x，y)	多属性效用值U
			Offer1	(180，30)	0.76
Offer2	(188，12)	0.88
			Offer3	(190，20)	0.88
Offer4	(195，45)	0.87

根据如上规则，可以看出虽然offer4的x属性满意度很高，但是由于对属性y的满意度太低，它的总效用值低于offer2和offer3，而offer2和offer3的效用值相同时，选择属性x的满意度较高的那一组，即在本轮的4个offer中选择的最优offer是offer3(190，20)。

以上所述仅是本发明的实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变型，这些改进和变型也应视为本发明的保护范围。

Claims (4)

1.一种基于协商的无线传感器网络任务分配方法，其特征在于，所述方法包括以下步骤：

S1，无线传感器网络中的节点作为招标方发布招标启事，等待竞标方出价；

S2，收到竞标邀请的节点根据对待分配任务的可完成度以及其当前剩余能量来决定是否参与竞标，决定参与竞标的节点作为竞标方就待分配任务的各个属性进行出价；

S3，招标方采用多属性效用函数来评价与竞标方的协商过程中各竞标方的出价方案，然后选择标的；

在步骤S1中的招标启事按照多属性效用函数进行设计，所设计的招标启事Notice包括以下内容：

Notice＝{P(p₁，p₂，…p_N)，W(w₁，w₂，…w_N)，LT，T_feedback，U_threshold}，其中，

P(p₁，p₂，…p_N)是任务属性向量，其中p₁，……，p_N是待分配任务所关注的N个属性，N为正整数；

W(w₁，w₂，…w_N)是任务权重向量，w₁，……，w_N分别对应任务属性向量中每个属性的重要性权值，

LT是招标方在一个招标轮次中最后一次选择竞标方的截止时间；

T_feedback是竞标方进行下一轮出价前等待中标通知的时间；

U_threshold是招标方预设的效用值的最大门限值。

2.如权利要求1所述的基于协商的无线传感器网络任务分配方法，其特征在于，还包括步骤：S4，给所选择的竞标方分配任务，并给所有的竞标方发任务已分配通知。

3.如权利要求1或2所述的基于协商的无线传感器网络任务分配方法，其特征在于，在步骤S1中招标方等待竞标方出价所遵循的原则如下：在招标方等待竞标方出价的过程中，不区分投标轮次，且不等待每一轮所有竞标方投标结束后再选择竞标方，也支持招标过程中节点的动态加入和离开。

4.如权利要求1或2所述的基于协商的无线传感器网络任务分配方法，其特征在于，步骤S3具体为：

当一个竞标方出价后，即判断该出价是否大于或等于效用值的最大门限值U_threshold，若是，则选择该竞标方为标的，并发布中标通知；否则判断此时是否已到达截止时间LT，若是，则在当前的所有竞标方的出价中根据采用多属性效用函数计算的效用值选择标的，并发布中标通知，否则，招标方标记当前的效用值最大的出价，继续等待新的出价；

其中，多属性效用函数为： $U\left(O^i\right)=\underset{j=1}{\overset{N}{\mathrm{\Σ}}}{w^i}_j{v^i}_j,$

上式中，出价向量N是招标过程中需要协商的属性的个数，

是第i个竞标方针对任务属性向量中的第j个属性的出价值，j∈[1，N]，该属性至少包括对待分配任务的可完成度和耗电量，

wⁱ _j是第i个招标方针对任务属性向量中的第j个属性的重要性权值，vⁱ _j是对第i个招标方针对任务属性向量中的第j个属性的评价函数值，

w值是由招标方指定的，v值表示对于竞标方给出的对于待分配任务的可完成度，招标方的满意度，v值通过以下方式计算：

当招标方的满意度随对第j个属性的出价O_j的提高而降低时，招标方对第j个属性的满意度

max，min分别表示招标方对于该任务的最大、最小期望值；

当招标方的满意度随对第j个属性的出价O_j的提高而提高时，招标方对第j个属性的满意度

Images