非合作博弈模型解决供水不足的通信调度

摘要：现实生活中，突发事件的发生防不胜防，由于突发事件而导致的供水不足问题频繁存在，不当的处理可能会对居民以及工业生产产生严重的影响。因此当突发事件发生后，在救急资源有限的情况下，如何对缺水地区进行合理的资源调度是一个非常现实而棘手的问题。本文基于如上现实场景，将其抽象为存在纳什均衡解的非合作博弈调度模型，从而把资源调度问题转化为求解非合作博弈调度模型的Nash均衡点问题，并给出了相关求解方法。

关键词：资源调度 非合作博弈模型 纳什均衡 迭代

一、引言

水是万物之源。没有水，社会将寸步难行。然而生活中，总会由于各种原因导致临时停水，给人们生活和生产带来不便。解决不可控因素下多方供水需求，单独的救急中心远远不够，必须调度多个救急中心的应急资源。由于各需水点对应急资源存在竞争关系，因此，寻找一种能够反映各个需水点的缺水严重程度和救助响应时间的应急资源调度策略和模型，以达到利益均衡是一个值得研究的课题。

二、调度策略的非合作博弈模型建立

（一）模型假设

在解决本文提出的不可控因素发生时对应急资源合理调度的问题前可以做出如下假设：

1.对各子系统在相同情况下对应急资源的需求量做出分级，1表示严重缺水，2表示重度缺水，3表示中度缺水，4表示轻度缺水。

2.现实中单一救急中心往往无法解决所有需水点对水资源的需求，因此需联合多个救急中心。假设当某一区域的应急资源难以解决问题时，可从邻近区域调水。

3.成本函数作为一个多元复合函数，其影响因素包含很多，比如本事件中子系统的缺水程度，资源调度到救援响应的时间以及需水点到救急中心的距离等。因此在解决问题前需要对各子系统（即需水点）对救急中心的调度成本进行从大到小的排序。

（二）博弈模型的相关参数与数学表达式

1.调度成本函数C■■

理论上以其为调度策略的依据。C■■的函数表达如下所示：

C■■=H■*（■）∞（4）

公式中，H■表示需水点i的缺水级别，Y■■表示需水点i到救急中心k的距离。

2.效益函数Pi

在实际调度过程中，收益函数等于调度成本的倒数：

P■■=■（5）

其中k∈M。公式中，C■表示需水点i在救急中心k未能得到资源而从其他救急中心进行资源调度而产生的额外成本。需水点i从全部救急中心集合M中调度其所需资源的效益函数满足叠加定理。

三、非合作博弈模型的算法求解

（一）求解水资源调度的非合作博弈模型Nash均衡解的步骤

1.对救援资源初始分配，确定各需水点向救急中心调度资源所产生的成本；

2.不考虑各救急中心可提供水资源的上限，按成本最小化原则向各需水点分配资源；

3.考虑各救急中心实际资源量，若可以满足同一级别各需水点，则按需分配。若不能，同级别各需水点对该救急中心的资源将产生竞争，形成博弈；

4.构造非合作博弈调度模型，求解Nash均衡解，并按Nash均衡解对救急中心的水资源进行调度；

5.同一级别的需水点若存在按照Nash均衡解分配后仍不满足需求的部分，则按成本最小化原则从其他救急中心调度资源，直到满足需求；

6.重复步骤（3）。

（二）求解纳什均衡

根据纳什均衡的定义，对所有纯策略组合进行逐一检验，得出纯策略纳什均衡。应用最多的一种算法称为迭代算法。

在实际迭代计算中可以从任意的s（0）∈S（策略空间）开始，假设初始点s（0）与纳什均衡点s*之间的距离为d（0），经过m次迭代以后，d（s（m），s*）≤？灼0d（s（0），s*）=？灼■■d（0），因为0≤？灼0≤1，因此可以采用迭代公式s（m+1）=Xs（m）来任意逼近纳什均衡点s*。

四、实例计算与分析

问题描述如下：现因某地区发生山体滑坡塌方，导致自来水厂源水浑浊度超标，从而导致城市G临时停水，期限不明。城市G有四个区a，b，c，d，分别报告了不同的缺水程度。城市G市内只有一处救急中心A，邻市F有两处救急中心B、C。为了不影响市民的日常生活，现有关部分组织进行水资源救助工作。数据假设如下。

表一 需水点缺水情况表

■

表二 救急中心资源情况表

■

现假设四个区域向各救急中心调度水资源所产生的成本是相同的。运用3.2提出的求解纳什均衡解的迭代方法可以求出该博弈的纯策略Nash均衡解：

s■■=（10，0，0） s■■=（1，5，2）

s■■=（2，5，1） s■■=（0，0，6）

将上述数据代入公式可求得：

总成本Ci，p=Ca，q+Cb，q+Cd，q=10+15+17+18=60是为最优化成本调度策略。

根据公式可求得此组合策略的各个收益函数，将各个需水点的收益函数代入公式，可得总的效益目标函数为：

F=Pa+Pb+Pc+Pd=21

综上所述，利用迭代算法求得的Nash均衡解：

s■■=（10，0，0）；s■■=（1，5，2）；s■■=（2，5，1）s■■=（0，0，6）可以实现向区域a，b，c，d进行水资源公平合理调度，并且能够保证调度策略的成本最小，效益最优。

五、结束语

该论文本着实用性原则针对日常生活中常见的临时供水不足问题进行了相关研究，论文方法通俗易懂，且延展性较强，相关的思想方法也可以用来处理类似求解最优化组合的问题，比如解决自然灾害发生时，不同地区受灾点的资源调配问题或者用于公司经营中解决客户售后服务的技术人员调配问题，商业中物流配送问题等。不足之处仍然存在，但客观讲，本文思想方法仍具有一定的理论及现实意义，具有较好的可操作性，值得广泛推广。

参考文献：

[1]Sun J， Xu WB.A global search strategy of quantum- behaved particle swarm optimization [C].Proceedings of IEEE Conference on Cybernetics and Intelligent Systems， 2009.：111- 116.

[2]HWANG H-S. A food distribution model for famine relief [J]. Computer and industrial Engineering， 2011， 37 （1 /2） ：335-338.

[3]Wan Xiaoyu，Pu Yifei， Li Bingjun， Fractional Differential Amplitude Hierarchical Feature of MPSK Signals[G].8tth INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING PROCEEDINGS，2010，

[4]王万良，蒋一波，李祖欣等.网络控制与调度方法及其应用[M].北京：科学出版社，2009.

[5]杨继军.面向非常规突发事件的应急资源博弈调度模型与优化策略研究[D].上海：同济大学经济与管理学院，2009.

[6]姚杰，计雷，池宏.突发事件应急管理中的动态博弈分析[J].管理评论，2005（3）：46-50.

[7]吴增军. 高校就业统计中的非合作博弈问题研究[J]. 职业教育研究，2009（3）.

[8]唐伟勤，张敏，张隐.大规模突发事件应急资源调度的过程模型[J].中国安全科学学报，2009（1）：33-37.

（责编 赵建荣）