论文部分内容阅读
【摘 要】提出基于模拟退火算法的WLAN组网信道选择算法，仿真结果表明采用此算法进行信道选择是行之有效的。
【关键词】模拟退火算法 信道选择
一、引言
无线通信技术为人们生活带了便利和高效率。作为传统有线网络的一种替代方案和延伸，无线通信技术用无线空口替代网线，把人们固定有线接入解放出来，随时随地方便的获取信息和提供娱乐。随着智能手机和Pad的大规模普及，基于移动智能终端的数据业务爆发式增长，传统运营商采用的2G/3G宏基站網络无法支持移动互联网海量数据流量，移动运营商开始关注利用微基站接入点作为容量吸收层承载数据业务。微基站接入点包括家庭用Femto、WLAN等。在国内，中国电信、中国移动、中国联通自2008年以来都大范围的部署和推广微蜂窝接入点，将其作为现有无线网络的补充，吸收容量。微蜂窝由于数量众多，部署场景千差万别，微蜂窝与宏蜂窝的差别之一就是要能够实现自动的频段规划，否则依靠人工规划部署，巨大的工作量将导致不可能进行实际部署。
二、数学建模和求解
运营商部署WLAN网络面临的一个重要问题就是，如何进行WLAN网络频率资源的规划，频谱规划的好坏关系到网络的性能。简单的说为了网络获取更好的性能，频率规划的原则应该使得相邻微基站尽量使用不同的频点尽量错开，整个网络的平均干扰水平最小。
以WLAN微蜂窝为例，WLAN一般使用20MHz工作带宽，工作在2.4GHz和5GHz频段非授权频谱。在2.4GHz频段WLAN有3个不重叠的20MHz信道，信道之间相互不会干扰。
为了使得问题具有通用性，假设有N个相互不干扰的工作频点，N为确定常数。在一定区域内要部署M个微基站接入点，最终求解是使得M个AP形成的网络性能最好，即干扰最小。在第n个频点工作的PAni对PAnj的干扰为。这个问题就变成求解最小。这是个问题可归结为一个数学上的NP问题。使用穷举求解这个问题，需要的实验次数为M^N，即求解该问题的复杂度O（M^N）。
通过穷举遍历试验可以求得NP问题的最优解，但一般情况下，遍历的复杂度即实验时间往往会是一个天文数字，使得实际中根本无法通过这种方法获得最优解。爬山算法是一种局部最优化解，其复杂度为线性，但往往会导致只搜索到局部最优解。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。1989 年 Johnson 等人通过详尽的实验证实了采用模拟退火算法求解NP问题的优点。爬山法每次都选择一个当前局部最优解，因此只能搜索到局部的最优值。模拟退火在搜索过程引入了随机因素，以一定的概率来接受一个比当前解要差的解，所以可能会跳出这个局部的最优解，到达全局最优解。模拟退火算法在搜索到局部最优解后，会以一定的概率接受到非局部最优的移动。也许经过几次这样的不是局部最优的移动后会跳出了局部最优向全局最优方向进行搜索。
模拟退火算法基本思想和过程如下：
假设代价函数为J（Y），第i次迭代过程代价函数为J（Y（i））；
若J（ Y（i+1） ）>= J（ Y（i） ），即移动后得到更优解，则总是接受该移动；
若J（ Y（i+1） ）< J（ Y（i） ），即移动后的解比当前解要差，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低，以使得该过程收敛。
这里的“一定的概率”计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P（dE），表示为，P（dE） = exp（ dE/（kT） ）。
其中k是一个常数，exp表示自然指数，且dE<0。这条公式说明：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0，因此dE/kT < 0 ，所以P（dE）的函数取值范围是（0，1） 。随着温度T的降低，P（dE）会逐渐降低。将一次向较差解的移动看做一次温度跳变过程，以概率P（dE）来接受这样的移动，最终搜索得趋向于最优解。
假设在1000平方米区域随机布放200个接入点，有4个可用信道频率。使用穷举法，需要进行200^4=1.6x10^9次试验。
使用模拟退火算法，构建代价函数，
其中，代表工作在第n个频点的PAni对PAnj的干扰。
通过仿真证明，使用模拟退火算法能够以较小的复杂度得到与穷举法几乎一致的最优解。
三、总结
本文分析了WLAN频率规划中的数学问题，归结为NP问题求解，证明了模拟退火算法解决这一类问题的实际可行性。
参考文献：
[1]Optimization by Simulated Annealing： An Experimental Evaluation； Part I， Graph Partitioning， David S. Johnson， Cecilia R. Aragon， Lyle A. McGeoch， Catherine Schevon；
[2]模拟退火算法与遗传算法的结合，王雪梅，王义和， 《计算机学报》1997年04期；
[3]新型遗传模拟退火算法求解物流配送路径问题， 阎庆， 鲍远律， 计算机应用 2004年z1期；
[4]一种属性约简的探测性贪婪算法，李 旻， 陈卫东， 计 算 机 工 程2012年10月第38卷第19期；
[5]基于模拟退火算法的布局问题研究，张和君，张 跃， 计算机工程与设计，2006年6月， 第27卷第11期；
【关键词】模拟退火算法 信道选择
一、引言
无线通信技术为人们生活带了便利和高效率。作为传统有线网络的一种替代方案和延伸，无线通信技术用无线空口替代网线，把人们固定有线接入解放出来，随时随地方便的获取信息和提供娱乐。随着智能手机和Pad的大规模普及，基于移动智能终端的数据业务爆发式增长，传统运营商采用的2G/3G宏基站網络无法支持移动互联网海量数据流量，移动运营商开始关注利用微基站接入点作为容量吸收层承载数据业务。微基站接入点包括家庭用Femto、WLAN等。在国内，中国电信、中国移动、中国联通自2008年以来都大范围的部署和推广微蜂窝接入点，将其作为现有无线网络的补充，吸收容量。微蜂窝由于数量众多，部署场景千差万别，微蜂窝与宏蜂窝的差别之一就是要能够实现自动的频段规划，否则依靠人工规划部署，巨大的工作量将导致不可能进行实际部署。
二、数学建模和求解
运营商部署WLAN网络面临的一个重要问题就是，如何进行WLAN网络频率资源的规划，频谱规划的好坏关系到网络的性能。简单的说为了网络获取更好的性能，频率规划的原则应该使得相邻微基站尽量使用不同的频点尽量错开，整个网络的平均干扰水平最小。
以WLAN微蜂窝为例，WLAN一般使用20MHz工作带宽，工作在2.4GHz和5GHz频段非授权频谱。在2.4GHz频段WLAN有3个不重叠的20MHz信道，信道之间相互不会干扰。
为了使得问题具有通用性，假设有N个相互不干扰的工作频点，N为确定常数。在一定区域内要部署M个微基站接入点，最终求解是使得M个AP形成的网络性能最好，即干扰最小。在第n个频点工作的PAni对PAnj的干扰为。这个问题就变成求解最小。这是个问题可归结为一个数学上的NP问题。使用穷举求解这个问题，需要的实验次数为M^N，即求解该问题的复杂度O（M^N）。
通过穷举遍历试验可以求得NP问题的最优解，但一般情况下，遍历的复杂度即实验时间往往会是一个天文数字，使得实际中根本无法通过这种方法获得最优解。爬山算法是一种局部最优化解，其复杂度为线性，但往往会导致只搜索到局部最优解。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。1989 年 Johnson 等人通过详尽的实验证实了采用模拟退火算法求解NP问题的优点。爬山法每次都选择一个当前局部最优解，因此只能搜索到局部的最优值。模拟退火在搜索过程引入了随机因素，以一定的概率来接受一个比当前解要差的解，所以可能会跳出这个局部的最优解，到达全局最优解。模拟退火算法在搜索到局部最优解后，会以一定的概率接受到非局部最优的移动。也许经过几次这样的不是局部最优的移动后会跳出了局部最优向全局最优方向进行搜索。
模拟退火算法基本思想和过程如下：
假设代价函数为J（Y），第i次迭代过程代价函数为J（Y（i））；
若J（ Y（i+1） ）>= J（ Y（i） ），即移动后得到更优解，则总是接受该移动；
若J（ Y（i+1） ）< J（ Y（i） ），即移动后的解比当前解要差，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低，以使得该过程收敛。
这里的“一定的概率”计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P（dE），表示为，P（dE） = exp（ dE/（kT） ）。
其中k是一个常数，exp表示自然指数，且dE<0。这条公式说明：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0，因此dE/kT < 0 ，所以P（dE）的函数取值范围是（0，1） 。随着温度T的降低，P（dE）会逐渐降低。将一次向较差解的移动看做一次温度跳变过程，以概率P（dE）来接受这样的移动，最终搜索得趋向于最优解。
假设在1000平方米区域随机布放200个接入点，有4个可用信道频率。使用穷举法，需要进行200^4=1.6x10^9次试验。
使用模拟退火算法，构建代价函数，
其中，代表工作在第n个频点的PAni对PAnj的干扰。
通过仿真证明，使用模拟退火算法能够以较小的复杂度得到与穷举法几乎一致的最优解。
三、总结
本文分析了WLAN频率规划中的数学问题，归结为NP问题求解，证明了模拟退火算法解决这一类问题的实际可行性。
参考文献：
[1]Optimization by Simulated Annealing： An Experimental Evaluation； Part I， Graph Partitioning， David S. Johnson， Cecilia R. Aragon， Lyle A. McGeoch， Catherine Schevon；
[2]模拟退火算法与遗传算法的结合，王雪梅，王义和， 《计算机学报》1997年04期；
[3]新型遗传模拟退火算法求解物流配送路径问题， 阎庆， 鲍远律， 计算机应用 2004年z1期；
[4]一种属性约简的探测性贪婪算法，李 旻， 陈卫东， 计 算 机 工 程2012年10月第38卷第19期；
[5]基于模拟退火算法的布局问题研究，张和君，张 跃， 计算机工程与设计，2006年6月， 第27卷第11期；