一种用于移动群智感知的分布式协同计算方法

1.本发明属于无线通信技术领域，具体涉及一种用于移动群智感知的分布式协同计算方法。


背景技术：

2.移动群智感知利用移动设备丰富的传感器，大量、广泛地收集各类传感数据，实现对物理环境的实时感知与监测。但是受限于移动设备体积、成本等因素，移动设备计算能力有限，无法负担感知数据的处理任务。目前，针对移动群智感知设备计算能力不足的问题，都采用了边缘计算或云计算的解决方案，移动设备将复杂的计算任务卸载到拥有用较强算力的计算服务器中，借助服务器强大的计算能力，及时完成感知数据的计算处理，保证任务的实时性。借用边缘计算/云计算服务器的算力可以有效解决移动设备算力不足问题，但是该类解决方案依赖于基础设施建设，移动设备必须能够有效访问这些计算服务器才能使用其提供的计算服务，因此这类解决方案无法适用于某些场景，例如在边远地区进行感知任务，计算服务器负载过高无法访问等。为了解决访问受限情况下移动设备计算能力不足问题，我们提出了一种用于移动群智感知的分布式协同计算方法，该方法利用空闲移动的设备的算力，协助计算感知数据，确保感知任务按时完成。


技术实现要素：

3.有鉴于此，本发明的目的在于提供一种用于移动群智感知的分布式协同计算方法，利用周围空闲移动设备的算力，协助完成复杂的计算任务，通过通过联合优化协助设备分配、任务分割、通信资源分配与计算资源分配，在保证感知任务计算时延约束情况下，使得全网加权能耗和最小化，以最大化群智感知网络的生存时间。
4.为达到上述目的，本发明提供如下技术方案：一种用于移动群智感知的分布式协同计算方法，包括以下步骤：s1：全网设备交换位置与电量信息，协助设备根据这些信息与任务设备进行匹配，完成协助设备的分配，形成协助簇；s2：在每个协助簇内，将加权能耗和最小化问题分解为两个子问题，通过迭代优化的方法进行求解，得到次优的任务分割、通信资源分配、计算资源分配解；s3：每个任务设备根据任务分割结果，拒绝没有被分配任务的协助设备；s4：未被分配的协助设备根据其对任务设备的偏好，再次向任务设备发起协助请求，形成新的协助簇；s5：重复步骤s2-s4，直到协助设备分配达到稳定。
5.进一步，步骤s1具体包括：根据获取到的位置信息，得到任意两个设备距离，根据获取到的电量信息，得到任意设备的能耗权重，由此得到协助设备对任务设备的喜好程度：
其中；协助设备根据计算的喜好程度，向其最喜欢的任务设备发起请求，任务设备接收到请求后，接收该协助设备，在所有协助设备发送完请求后，以任务节点为簇头的协助簇随即形成。
6.进一步，步骤s2具体包括：s21：协助簇形成后，得到簇内加权能耗最小化问题如下：s22：将问题p1分解为两个子问题：任务分割问题与联合通信、计算资源优化问题，其中任务分割问题表示为：
联合通信、计算资源优化问题表示为：s23：通过类注水算法计算问题p1.1的最优解，即选择目标代价最小的设备分配任务，直到达到该设备在确保任务按时完成情况下的处理上限；s24：在对目标函数中的分式项进行处理后，使用二分法求解计算资源分配最优解；利用问题p1.2对偶间隙趋近0的特性，使用拉格朗日对偶法求解出通信资源分配的次优解；从而得到问题p1.2的求解算法；s25：使用交替优化的方法，对问题p1.1和问题p1.2进行交替优化，直到算法收敛，由此得到簇内加权能耗最小化问题p1的次优解。
7.进一步，步骤s23所述通过类注水算法计算问题p1.1的最优解，具体包括：输入子载波分配结果，传输功率分配结果，计算资源分配结果；s231：为每个任务设备设置待分配的任务比特数量，初始化设备遍历下标；s232：使用以下公式，计算当前协助簇内所有设备的目标代价s232：使用以下公式，计算当前协助簇内所有设备的目标代价s233：对结果进行升序排序，结果序列表示为:；s234：若，则根据以下公式进行任务分割
其中n=；s235：输出任务分割结果。
8.进一步，步骤s24所述使用二分法求解计算资源分配最优解，具体包括以下步骤：输入任务分割结果，拉格朗日乘子、，偏差容忍度；设置二分下限，设置二分上限，其中；设置，并计算；如果，设置二分上限，否则设置二分下限，迭代执行本步骤，直到；输出计算资源分配结果。
9.进一步，步骤s24所述使用拉格朗日对偶法求解出通信资源分配的次优解，具体包括以下步骤：输入分式优化辅助变量、，最大迭代次数，偏差容忍度；设置初始化拉了朗日乘子,和；设置初始化迭代次数，设置初始化拉格朗日函数结果；获取计算资源分配结果；对于每一个子载波，进行如下计算：计算，其中，计算，根据以下公式获取子载波分配结果与传输功率分配结果：；；更新拉格朗日函数结果，更新拉格朗日乘子,和；迭代执行本步骤，直到或者；
输出子载波分配结果，传输功率分配结果，计算资源分配结果。
10.进一步，步骤s24所述问题p1.2的求解算法如下：任务分割结果，偏差容忍度；计算设置初始化迭代次数，随机生成初始可行解,；计算分式优化辅助变量、初始值；给定和，获取,, 和结果；更新分式优化辅助变量和；迭代执行本步骤，直到且；输出子载波分配结果，传输功率分配结果，计算资源分配结果。
11.进一步，步骤s25所述使用交替优化的方法，对问题p1.1和问题p1.2进行交替优化，直到算法收敛，由此得到簇内加权能耗最小化问题p1的次优解，具体包括以下步骤：输入协助设备分配结果，子载波分配结果，最大迭代次数，偏差容忍度；设置初始化迭代次数,；随机生成初始可行解,,；给定，，，获取；给定，获取，，；计算每个协助簇的加权能耗；迭代执行本步骤，直到或者；输出任务分割结果，子载波分配结果，传输功率分配结果，计算资源分配结果。
12.本发明的有益效果在于：本发明解决了访问受限情况下移动设备计算能力不足问题，通过协同计算的方式，群智感知设备可以将其无法负担的计算任务卸载给临近设备同时计算，通过使用提出的联合优化方法可以确保在按时完成感知任务前提下最小化系统的加权能耗，与本地计算相比，本发明提出的协同计算方法可以极大的提高任务按时完成比率同时有效降低能耗，扩展移动群智感知网络生存时间。
13.本发明的其他优点、目标和特征将在随后的说明书中进行阐述，并且在某种程度上对本领域技术人员而言是显而易见的，或者本领域技术人员可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
14.为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行说明：图1为本发明协同计算架构系统模型。
具体实施方式
15.本发明的目的是提供一种用于移动群智感知的分布式协同计算方法，利用周围空闲移动设备的算力，协助完成复杂的计算任务，通过通过联合优化协助设备分配、任务分割、通信资源分配与计算资源分配，在保证感知任务计算时延约束情况下，使得全网加权能耗和最小化，以最大化群智感知网络的生存时间。针对所提出的协同计算架构，本发明构建起了一个普适的系统模型，具体如下：如图1所示，系统中包含个单天线任务设备，个单天线协助设备，个带宽为的正交子载波。使用表示每个设备被分配的计算任务大小，表示计算任务的复杂度，表示分配的计算资源，由此可以得到设备执行计算任务所花费的时间与能耗：。使用表示子载波的分配情况，使用表示传输功率的分配情况，根据香农公式可以得到设备和设备间的无线通信传输速率为：，由此可以得到设备卸载计算任务所花费的时间与能耗：。基于上述模型可以得到每个协助簇内的加权能耗和为：。
16.由此形成了以下优化问题：
为解决该问题，本发明提出了一种高效的求解方法，具体包括以下步骤：步骤一、全网设备交换位置与电量信息，协助设备根据这些信息与任务设备进行匹配，完成协助设备的分配，形成协助簇。具体为，根据获取到的位置信息，可以得到任意两个设备距离，根据获取到的电量信息，可以得到任意设备的能耗权重，由此可以得到协助设备对任务设备的喜好程度：其中。协助设备根据计算的喜好程度，向其最喜欢的任务设备发起请求，任务设备接收到请求后，接收该协助设备，在所有协助设备发送完请求后，以任务节点为簇头的协助簇随即形成。
17.步骤二、在每个协助簇内，将加权能耗和最小化问题分解为两个子问题，通过迭代优化的方法进行求解，得到次优的任务分割、通信资源分配、计算资源分配解。具体为，协助簇形成后，得到簇内加权能耗最小化问题如下：
为解决该问题，本发明将其分解为两个子问题：任务分割问题与联合通信、计算资源优化问题。其中子问题一任务分割问题表示为：该问题是一个线性规划问题，可以通过类注水算法求到最优解，即选择目标代价最小的设备分配任务，直到达到该设备在确保任务按时完成情况下的处理上限，算法步骤如表1。
18.表1
子问题二联合通信、计算资源优化问题表示为：在对目标函数中的分式项进行处理后，使用二分法求解计算资源分配最优解，具体算法流程如表2。
19.表2
利用该问题对偶间隙趋近0的特性，使用拉格朗日对偶法可以求解出通信资源分配的次优解，算法步骤如表3所示。
20.表3
由此可以得到子问题二的求解算法，如表4所示。
21.表4最后使用交替优化的方法，对子问题一和子问题二进行交替优化，直到算法收敛，由此得到簇内加权能耗最小化问题的次优解，算法步骤如表5所示。
22.表5
步骤三、每个任务设备根据任务分割结果，拒绝没有被分配任务的协助设备；步骤四、未被分配的协助设备根据其对任务设备的偏好，再次向任务设备发起协助请求，形成新的协助簇；步骤五、重复步骤二、三、四，直到协助设备分配达到稳定。
23.总算法步骤如表6所示。
24.表6表6最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。

技术特征：
1.一种用于移动群智感知的分布式协同计算方法，其特征在于：包括以下步骤：s1：全网设备交换位置与电量信息，协助设备根据这些信息与任务设备进行匹配，完成协助设备的分配，形成协助簇；s2：在每个协助簇内，将加权能耗和最小化问题分解为两个子问题，通过迭代优化的方法进行求解，得到次优的任务分割、通信资源分配、计算资源分配解；s3：每个任务设备根据任务分割结果，拒绝没有被分配任务的协助设备；s4：未被分配的协助设备根据其对任务设备的偏好，再次向任务设备发起协助请求，形成新的协助簇；s5：重复步骤s2-s4，直到协助设备分配达到稳定。2.根据权利要求1所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s1具体包括：根据获取到的位置信息，得到任意两个设备距离，根据获取到的电量信息，得到任意设备的能耗权重，由此得到协助设备对任务设备的喜好程度：其中；协助设备根据计算的喜好程度，向其最喜欢的任务设备发起请求，任务设备接收到请求后，接收该协助设备，在所有协助设备发送完请求后，以任务节点为簇头的协助簇随即形成。3.根据权利要求1所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s2具体包括：s21：协助簇形成后，得到簇内加权能耗最小化问题如下：
s22：将问题p1分解为两个子问题：任务分割问题与联合通信、计算资源优化问题，其中任务分割问题表示为：联合通信、计算资源优化问题表示为：
s23：通过类注水算法计算问题p1.1的最优解，即选择目标代价最小的设备分配任务，直到达到该设备在确保任务按时完成情况下的处理上限；s24：在对目标函数中的分式项进行处理后，使用二分法求解计算资源分配最优解；利用问题p1.2对偶间隙趋近0的特性，使用拉格朗日对偶法求解出通信资源分配的次优解；从而得到问题p1.2的求解算法；s25：使用交替优化的方法，对问题p1.1和问题p1.2进行交替优化，直到算法收敛，由此得到簇内加权能耗最小化问题p1的次优解。4.根据权利要求3所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s23所述通过类注水算法计算问题p1.1的最优解，具体包括：输入子载波分配结果，传输功率分配结果，计算资源分配结果；s231：为每个任务设备设置待分配的任务比特数量，初始化设备遍历下标；s232：使用以下公式，计算当前协助簇内所有设备的目标代价s232：使用以下公式，计算当前协助簇内所有设备的目标代价s233：对结果进行升序排序，结果序列表示为: ；s234：若，则根据以下公式进行任务分割
其中n=；s235：输出任务分割结果。5.根据权利要求3所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s24所述使用二分法求解计算资源分配最优解，具体包括以下步骤：输入任务分割结果，拉格朗日乘子、，偏差容忍度；设置二分下限，设置二分上限，其中；设置，并计算；如果，设置二分上限，否则设置二分下限，迭代执行本步骤，直到；输出计算资源分配结果。6.根据权利要求3所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s24所述使用拉格朗日对偶法求解出通信资源分配的次优解，具体包括以下步骤：输入分式优化辅助变量、，最大迭代次数，偏差容忍度；设置初始化拉了朗日乘子, 和；设置初始化迭代次数，设置初始化拉格朗日函数结果；获取计算资源分配结果；对于每一个子载波，进行如下计算：计算，其中，计算，根据以下公式获取子载波分配结果与传输功率分配结果：；；更新拉格朗日函数结果，更新拉格朗日乘子, 和；迭代执行本步骤，直到或者；输出子载波分配结果，传输功率分配结果，计算资源分配结果。7.根据权利要求3所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s24所述问题p1.2的求解算法如下：任务分割结果，偏差容忍度；
计算设置初始化迭代次数，随机生成初始可行解, ；计算分式优化辅助变量、初始值；给定和，获取, , 和结果；更新分式优化辅助变量和；迭代执行本步骤，直到且；输出子载波分配结果，传输功率分配结果，计算资源分配结果。8.根据权利要求3所述的用于移动群智感知的分布式协同计算方法，其特征在于：步骤s25所述使用交替优化的方法，对问题p1.1和问题p1.2进行交替优化，直到算法收敛，由此得到簇内加权能耗最小化问题p1的次优解，具体包括以下步骤：输入协助设备分配结果，子载波分配结果，最大迭代次数，偏差容忍度；设置初始化迭代次数,；随机生成初始可行解, ,；给定，，，获取；给定，获取，，；计算每个协助簇的加权能耗；迭代执行本步骤，直到或者；输出任务分割结果，子载波分配结果，传输功率分配结果，计算资源分配结果。

技术总结
本发明公开了一种用于移动群智感知的分布式协同计算方法，属于无线通信技术领域，包括以下步骤：S1：全网设备交换位置与电量信息，协助设备根据这些信息与任务设备进行匹配，完成协助设备的分配，形成协助簇；S2：在每个协助簇内，将加权能耗和最小化问题分解为两个子问题，通过迭代优化的方法进行求解，得到次优的任务分割、通信资源分配、计算资源分配解；S3：每个任务设备根据任务分割结果，拒绝没有被分配任务的协助设备；S4：未被分配的协助设备根据其对任务设备的偏好，再次向任务设备发起协助请求，形成新的协助簇；S5：重复步骤S2-S4，直到协助设备分配达到稳定。到协助设备分配达到稳定。到协助设备分配达到稳定。


技术研发人员：白琳 谢鑫 白桐
受保护的技术使用者：北京航空航天大学
技术研发日：2023.06.26
技术公布日：2023/8/1