一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法

摘要

本发明涉及一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法，包括四个阶段：（1）、任务分层：中心簇根据任务的DAG图对其进行分层划分；（2）确定协作簇：如果中心簇的能量消耗度超过设定阈值，则向周边一跳簇发送请求协助消息，周边一跳簇的能量消耗度如果未超过设定阈值，则成为中心簇的协作簇（3）任务分配到簇头：每层任务首先由中心簇负责处理，中心簇将未分配任务分配给协作簇；（4）簇头将任务分配给簇内节点：簇内任务分配采用第二低价密封拍卖方法，簇头作为拍卖方，簇内节点作为竞标方，拍卖方选择出价最低的竞标方中标，中标方以第二低价进行交易。本发明达到网络节点能量平衡，延长网络生存时间。

说明书

[0001] 技术领域

本发明属于无线多媒体传感器网络领域，具体地本发明涉及一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法，将网络中的复杂任务分簇处理，可提高任务处理效率，平衡网络负载，延长网络寿命。 

背景技术

相关文献如下： 

1、2007年，朱敬华等人在《无线传感器网络中能源高效的任务分配算法》中提出多跳传感器网络中的一种基于遗传算法的嵌套优化技术的任务分配算法，通过结合基于遗传算法的任务映射、路由路径分配、任务调度以及动态电压调制来获得最优分配方案，同时实现应用的实时性和能源利用的高效性。 

2、2010年，Sherine Abdelhak等在《Energy-balancing Task Allocation on Wireless Sensor Networks for Extending the Lifetime》中提出了一种任务分组方法，该方法可以保证任务的并行处理，但是当同一个孩子任务有若干个父任务，并且该子任务被同时要求加入不同父任务的任务小组的情况没有提供相应解决方案。同时，该任务分配方案中也缺少相应的节能措施，仅仅是根据节点的剩余能量来选择工作节点，不能达到系统性能的最优化。 

3、2011年，Morteza Okhovvat等人《Task Allocation to Actors in Wireless Sensor Actor Networks:An Energy And Time Aware Technique》提出了一种基于排队论优化的任务分配机制，该机制既考虑了系统能量优化又考虑了任务的完成时间。算法的第一阶段，任务被平均的分配给每一个代理服务器，并根据这些代理服务器的处理效果来判断服务器的处理性能；第二阶段是根据服务器的处理性能来分配任务。以此方法来达到缩短任务处理时间的目的，但是在无线传感器网络中，节点能量受限且难以补充，节点的剩余能量也会随着处理任务个数的增多而减少，其任务处理性能直接受到影响，不可能一直保持不变。 

发明内容

为了克服现有技术中存在的不足，本发明提供了一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法。 

一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法，包括如下步骤： 

（1）任务分层，根据任务DAG图对其进行分层划分，任务分配时从上至 下逐层分配，每层分布有若干簇； 

（2）当任务事件发生后，事发点所在的簇作为中心簇，中心簇的簇头负责将层中任务进行分配，当中心簇的簇能量消耗度超过阈值时，则向周边一跳簇发送请求信息，如果周边一跳簇能量消耗度未超过阈值，则接受请求，作为中心簇的协作簇；中心簇与周边一跳簇形成协作簇群，周边一跳簇簇头接受中心簇头的安排； 

（3）中心簇将未分配任务分配到协作簇，分配时保证各个簇的能量均衡，能量消耗度相差最小；任务分配时从上至下逐层分配，第一层的任务需分配到中心簇；在第一层任务处理的同时，进行第二层任务分配，从而缩短任务的完成时间； 

（4）任务分配到中心簇或协作簇的簇头后，簇头再将任务分配到簇内成员节点上进行处理，将博弈论引入任务分配中，采用拍卖形式，拍卖策略为第二低价密封拍卖；出价最低的节点中标，并以第二低的价格完成交易，进行处理任务。 

上述步骤（1）中的根据任务的DAG图对任务进行分层划分的步骤如下： 

（2a）入口任务划分为第一层; 

（2b）如果某一子任务前驱最大层为k，则该子任务划分到k+1层。 

上述步骤（2）中判断中心簇接受新任务后是否超过自身的簇能量消耗度的计算过程如下： 

（1）计算簇当前能量消耗C(Cluster_i)：簇当前能量消耗是指某个簇当前已有的任务的总能量消耗； 

（2）计算簇总剩余能量E_Resi(Cluster_i)：簇总剩余能量是簇内所有节点的剩余能量之和$E_{\mathrm{Resi}}\left(\mathrm{Clust}{\mathrm{er}}_i\right)=\underset{{\mathrm{Node}}_i\in {\mathrm{Cluster}}_i}{\Sigma }{E}_{\mathrm{Resi}}\left({\mathrm{Node}}_i\right),$其中Node_i表示簇Cluster_i中的节点； 

（3）计算簇能量消耗度：簇能量消耗度是该簇内当前能量消耗与占簇总剩余能量之比， 

$\mathrm{Load}\left({\mathrm{cluster}}_i\right)=\frac{C\left(\mathrm{Clust}{\mathrm{er}}_i\right)}{E_{\mathrm{Resi}}\left({\mathrm{Cluster}}_i\right)}\times 100\%$

上述步骤（₂）中设定簇能量消耗度阈值L_Thre，如果簇的能量消耗度超过设定阈值，说明簇负载已经很重，如果再继续接受表任务，簇内节点会有死亡的可能性；为了保证网络能量平衡，延长网络寿命，该簇不再接受新任务。 

上述步骤（2）中的中心簇请求周边一跳簇协作的具体步骤如下： 

（1）中心簇计算如果处理某层所有任务后的簇能量消耗度Load(Cluster_i)，并判断Load(Cluster_i)是否大于设定阈值L_Thre； 

（2）如果中心簇能量消耗度小于设定阈值，则中心簇有能力完成所选层中所有任务，不向周边一跳簇发送请求信息； 

（3）如果中心簇能量消耗度大于或等于设定阈值，则中心簇没有能力完成所选层中所有任务，中心簇簇头向周边一跳簇簇头发送请求协作消息； 

（4）周边一跳簇接收到消息后，首先计算自身簇能量消耗度，如果簇能量消耗度超过设定阈值，则返回拒绝请求的消息，如果簇能量消耗度未超过阈值，则返回接受请求的消息； 

（5）接受请求的簇作为中心簇的协作簇，协作簇中的簇头接受中心簇簇头分配的任务。 

上述步骤（3）中的中心簇将任务分配给协作簇的具体步骤如下： 

（1）第一层任务分配给中心簇，在第一层任务处理的同时，进行第二层任务分配； 

（2）中心簇簇头将选定层中自身能力完不成的任务分配给协作簇簇头，分配时保证各个簇的能量消耗度尽量平衡； 

（3）如果协作簇分配到任务，但分配任务后能量消耗度大于设定阈值，则该簇不将任务分配到簇内成员节点执行，而是将超出阈值的任务请求自身周边一跳簇协作处理； 

（4）任务分配到簇头后，由簇头将任务分配到簇内成员节点执行，同时进行下一层任务分配，直到所有任务分配完成。 

上述步骤（4）中中心簇或协作簇的簇头将接收的任务分配到簇内成员节点，该问题描述成不完全信息拍卖问题，采用第二低价密封竞标策略，具体步骤为： 

（1）簇头作为拍卖方，将任务进行拍卖，并对任务进行描述，包括任务大小、任务期限、任务预算； 

（2）簇内成员节点作为竞标方，接到任务消息后，根据自己的实际情况计算出标值，并进行投递； 

（3）拍卖方在等待时间结束后，选择出价最低的竞标者中标，并通知其他竞标者已经有人中标，结束拍卖； 

（4）拍卖方将任务分配给中标方处理。 

上述拍卖方发送给竞标方的标书格式为：<T,S,DL,B>,其中， 

T是任务标识； 

S是任务大小，用所用节点CPU周期表示； 

DL是任务完成期限，在DAG图中标出； 

B是拍卖方所出最大预算。 

上述竞标方接收到拍卖方发送的任务消息后，根据自己的剩余能量、已有任 

务完成时间，计算出完成该任务所需实际成本，成本计算的公式为： 

$C_{\mathrm{ij}}\left(t\right)(\mathrm{ComCost}+S_j\times {\mathrm{EP}}_i)[1+\exp [-\frac{\lambda (t,{\mathrm{DL}}_j)}{\gamma (t,{\mathrm{RT}}_i)}\left]\right],$其中， 

t是任务到达时间； 

C_ij(t)是节点i在t时刻时接受任务j，完成它所所需实际成本； 

ComCost是任务之间传输数据所消耗通信成本； 

S_j×EP_i是节点处理任务所消耗计算成本，其中S_j是任务大小，EP_i是完成单位任务所消耗计算成本，E_i是节点i剩余能量，节点剩余能量越大，计算成本越小; 

DL_j是任务j完成期限时间； 

RT_i是节点i是空闲时间。 

λ是关于t和DL_j的函数； 

_γ是关于t和RT_i的函数。 

上述成本公式中λ(t,DL_j)，γ(t,RT_i)取值如下： 

$\lambda (t,{\mathrm{DL}}_j)=\left(\begin{array}{c}k(t-{\mathrm{DL}}_j),t<{\mathrm{DL}}_j\\ +\infty ,t>{\mathrm{DL}}_j\end{array}\right)$

$\gamma (t,{\mathrm{RT}}_i)=\left(\begin{array}{cc}{\mathrm{RT}}_i-t,& t<{\mathrm{RT}}_i\\ 0,& t>{\mathrm{RT}}_i\end{array}\right).$

其中， 

k是自定义常数; 

上述成本公式中表示，当任务到达时间小于节点空闲时间时，任务到达时间 越接近节点空闲时间，成本越低，任务到达时间越接近于任务完成期限时间，成本越高；当任务到达时间大于节点空闲时间，即节点处于空闲状态，则成本固定，就是通信消耗与计算消耗之和。 

上述竞标方为了能够最大概率中标，出价价格应该接近于成本价，即Bidi_j＝Cij。 

本发明的有益效果为：与现有技术相比，本发明提供了一种一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法，单个簇无法完成复杂任务时，向周边簇请求协作，组成协作簇，共同完成复杂任务，将簇能量消耗度作为是否参与协作的门槛，从而平衡各簇能量，延长网络生命周期；簇内任务分配采用第二低价密封拍卖方法，使得簇内节点根据自己的真实情况进行报价，从而提高任务分配效率及完成质量。 

附图说明

图1：任务DAG图。 

图2：根据任务DAG图分层结果。 

图3：中心簇请求周边一跳簇协助流程图。 

图4：周边一跳簇接受中心簇请求流程图。 

图5：簇头拍卖任务流程图。 

图6：簇内节点竞拍任务流程图。 

具体实施方式

以下结合附图及实施例对本发明作进一步的详细说明。 

如图1、2、3、4、5、6所示，一种基于逆向拍卖策略的无线传感器网络中复杂任务协作求解方法，包括如下步骤： 

（1）任务分层，根据任务DAG图对其进行分层划分，任务分配时从上至下逐层分配，每层分布有若干簇； 

（2）当任务事件发生后，事发点所在的簇作为中心簇，中心簇的簇头负责将层中任务进行分配，当中心簇的簇能量消耗度超过阈值时，则向周边一跳簇发送请求信息，如果周边一跳簇能量消耗度未超过阈值，则接受请求，作为中心簇的协作簇；中心簇与周边一跳簇形成协作簇群，周边一跳簇簇头接受中心簇头的安排； 

（3）中心簇将未分配任务分配到协作簇，分配时保证各个簇的能量均衡，能量消耗度相差最小；任务分配时从上至下逐层分配，第一层的任务需分配到中心簇；在第一层任务处理的同时，进行第二层任务分配，从而缩短任务的完成时间； 

（4）任务分配到中心簇或协作簇的簇头后，簇头再将任务分配到簇内成员节点上进行处理，将博弈论引入任务分配中，采用拍卖形式，拍卖策略为第二低价密封拍卖；出价最低的节点中标，并以第二低的价格完成交易，进行处理任务。 

上述步骤（1）中的根据任务的DAG图对任务进行分层划分的步骤如下： 

（2a）入口任务划分为第一层; 

（2b）如果某一子任务前驱最大层为k，则该子任务划分到k+1层。 

上述步骤（2）中判断中心簇接受新任务后是否超过自身的簇能量消耗度的计算过程如下： 

（1）计算簇当前能量消耗C(Cluster_i)：簇当前能量消耗是指某个簇当前已有的任务的总能量消耗； 

（2）计算簇总剩余能量E_Resi(Cluster_i)：簇总剩余能量是簇内所有节点的剩余能量之和$E_{\mathrm{Resi}}\left(\mathrm{Clust}{\mathrm{er}}_i\right)=\underset{{\mathrm{Node}}_i\in {\mathrm{Cluster}}_i}{\Sigma }{E}_{\mathrm{Resi}}\left({\mathrm{Node}}_i\right),$其中Node_i表示簇Cluster_i中的节点； 

（3）计算簇能量消耗度：簇能量消耗度是该簇内当前能量消耗与占簇总剩余能量之比， 

$\mathrm{Load}\left({\mathrm{cluster}}_i\right)=\frac{C\left(\mathrm{Clust}{\mathrm{er}}_i\right)}{E_{\mathrm{Resi}}\left({\mathrm{Cluster}}_i\right)}\times 100\%$

上述步骤（2）中设定簇能量消耗度阈值L_Thre，如果簇的能量消耗度超过设定阈值，说明簇负载已经很重，如果再继续接受表任务，簇内节点会有死亡的可能性；为了保证网络能量平衡，延长网络寿命，该簇不再接受新任务。 

上述步骤（2）中的中心簇请求周边一跳簇协作的具体步骤如下： 

（1）中心簇计算如果处理某层所有任务后的簇能量消耗度Load(Cluster_i)，并判断Load(Cluster_i)是否大于设定阈值L_Thre； 

（2）如果中心簇能量消耗度小于设定阈值，则中心簇有能力完成所选层中所有任务，不向周边一跳簇发送请求信息； 

（3）如果中心簇能量消耗度大于或等于设定阈值，则中心簇没有能力完成所选层中所有任务，中心簇簇头向周边一跳簇簇头发送请求协作消息； 

（4）周边一跳簇接收到消息后，首先计算自身簇能量消耗度，如果簇能量消耗度超过设定阈值，则返回拒绝请求的消息，如果簇能量消耗度未超过阈值，则返回接受请求的消息； 

（5）接受请求的簇作为中心簇的协作簇，协作簇中的簇头接受中心簇簇头分配的任务。 

上述步骤（3）中的中心簇将任务分配给协作簇的具体步骤如下： 

（1）第一层任务分配给中心簇，在第一层任务处理的同时，进行第二层任务分配； 

（2）中心簇簇头将选定层中自身能力完不成的任务分配给协作簇簇头，分配时保证各个簇的能量消耗度尽量平衡； 

（3）如果协作簇分配到任务，但分配任务后能量消耗度大于设定阈值，则该簇不将任务分配到簇内成员节点执行，而是将超出阈值的任务请求自身周边一跳簇协作处理； 

（4）任务分配到簇头后，由簇头将任务分配到簇内成员节点执行，同时进行下一层任务分配，直到所有任务分配完成。 

上述步骤（4）中中心簇或协作簇的簇头将接收的任务分配到簇内成员节点，该问题描述成不完全信息拍卖问题，采用第二低价密封竞标策略，具体步骤为： 

（1）簇头作为拍卖方，将任务进行拍卖，并对任务进行描述，包括任务大小、任务期限、任务预算； 

（2）簇内成员节点作为竞标方，接到任务消息后，根据自己的实际情况计算出标值，并进行投递； 

（3）拍卖方在等待时间结束后，选择出价最低的竞标者中标，并通知其他竞标者已经有人中标，结束拍卖； 

（4）拍卖方将任务分配给中标方处理。 

上述拍卖方发送给竞标方的标书格式为：<T,S,DL,B>,其中， 

T是任务标识； 

S是任务大小，用所用节点CPU周期表示； 

DL是任务完成期限，在DAG图中标出； 

B是拍卖方所出最大预算。 

上述竞标方接收到拍卖方发送的任务消息后，根据自己的剩余能量、已有任务完成时间，计算出完成该任务所需实际成本，成本计算的公式为： 

$C_{\mathrm{ij}}\left(t\right)(\mathrm{ComCost}+S_j\times {\mathrm{EP}}_i)[1+\exp [-\frac{\lambda (t,{\mathrm{DL}}_j)}{\gamma (t,{\mathrm{RT}}_i)}\left]\right],$其中， 

t是任务到达时间； 

C_ij(t)是节点i在t时刻时接受任务j，完成它所所需实际成本； 

ComCost是任务之间传输数据所消耗通信成本； 

S_j×EP_i是节点处理任务所消耗计算成本，其中S_j是任务大小，EP_i是完成单位任务所消耗计算成本，E_i是节点i剩余能量，节点剩余能量越大，计算成本越小; 

DL_j是任务j完成期限时间； 

RT_i是节点i是空闲时间。 

λ是关于t和DL_j的函数； 

_γ是关于t和RT_i的函数。 

上述成本公式中λ(t,DL_j)，γ(t,RT_i)取值如下： 

$\lambda (t,{\mathrm{DL}}_j)=\left(\begin{array}{c}k(t-{\mathrm{DL}}_j),t<{\mathrm{DL}}_j\\ +\infty ,t>{\mathrm{DL}}_j\end{array}\right)$

$\gamma (t,{\mathrm{RT}}_i)=\left(\begin{array}{cc}{\mathrm{RT}}_i-t,& t<{\mathrm{RT}}_i\\ 0,& t>{\mathrm{RT}}_i\end{array}\right).$

其中， 

^k是自定义常数; 

上述成本公式中表示，当任务到达时间小于节点空闲时间时，任务到达时间越接近节点空闲时间，成本越低，任务到达时间越接近于任务完成期限时间，成本越高；当任务到达时间大于节点空闲时间，即节点处于空闲状态，则成本固定，就是通信消耗与计算消耗之和。 

上述竞标方为了能够最大概率中标，出价价格应该接近于成本价，即Bidi_j＝Cij。 

以上所述，仅是本发明的较佳实施例而已，并非对本发明作任何形式上的限制，虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明,任何熟悉本专业的技术人员，在不脱离本发明技术方案范围内,当可利用上述揭示的技术 内容作出些许更动或修饰为等同变化的等效实施例,但凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均仍属于本发明技术方案的范围内。