WLAN 中基于加权一阶局域法的站点数预测 http://www.paper.edu.cn 孙长欣 北京邮电大学电子工程学院，北京（100876） E-mail：changxin.sun@gmail.com 摘 要：大量研究无线局域网的文献集中于站点数对吞吐量等性能影响的分析，对于站点数 预测的相关研究则显得不够充分，而精确估计实时站点数目对无线局域网的性能控制起着重 要的作用。因此，本文从一个全新的角度，利用预测统计学中的最新方法——加权一阶局域 法，对在某个特定环境中无线局域网中的站点数进行了预测，并通过实验仿真，验证了本预 测方法是很有效的。 关键词：混沌时间序列，加权一阶局域法，关联维，邻近点 中图分类号：TN919 1. 引言 无线局域网中的站点数是影响网络服务质量的重要因素，大量与无线局域网相关的研究 论文是针对站点数的预测方法，以及在已知站点数的情况下求解最优的竞争窗口大小[1]。然 而，由于隐藏站点的存在，以及影响网络中站点数的因素是多方面的，现在并不存在很好的 解决站点数预测的方法。本文提出了用混沌时间序列加权一阶局域法作预测，根据已知的站 点数对无线局域网中的站点数进行了预测。 2. 混沌时间序列知识 混沌系统是一种可以从无序和复杂中产生出有序和规律的系统，应该说混沌是介于随机 和规律之间的。一个混沌系统的行为应由许多有序行为组合而成，并且在一般情况下，任何 一个单独的行为均不在系统中占主导地位。由于混沌系统具有“蝴蝶效应”[2]，所以混沌时 间序列是长期不可预测的。但是这并不是说混沌系统是不可预测的，事实上在短期内，系统 运动轨道散发应该较小，从而利用观测资料进行短期预报是可行的。由 D.J.Farmer 等提出， Takens 用拓扑学为奠定坚实基础的时间延迟相空间重构方法，为时间序列预测提供了一条崭 新的途径。 当我们对混沌时间序列进行预测时，应该注意到混沌是确定的，即混沌服从一定的法则。 实际上它具有有限的预测能力。虽然它们对处事条件极为敏感，同时，我们也不可能得到完 全准确的测量，然而在它们的可预测能力丢失之前，对一个短时间长度，它的预测性还是可 以获得的，并可能比基于一般统计方法的预测能力要好。 在无线局域网中为了得到我们需要的混沌时间序列，我们需要对网络中的时间进行划 分，我们令 T 为一个单位时间（可假设为一分钟，这个时间不能太长，太长的话导致最小 竞争窗口无法及时更新，也不能太短，太短的话无法真实反映网络中站点数的情况），在一 个特定的环境中（比如一栋办公大楼里的一个 AP 接入点范围内），每经过一个 T 时间片， 就记录下网络中与 AP 有数据交互的站点（不重复记录，且需要这 AP 中有一定的存储空间， 以便记录足够多的值，其大小将在后面的具体实现中讨论），这样，在经过 N 个时间片后， 就会得到一组站点数统计数值，并记录在 AP 中。当有新数据加入 AP 的记录空间时，AP 利用混沌的算法，预测出下一个时间片网络中的站点数，并发布一条消息给网络中的所有站 点，并让这些站点依据站点数更新它们的竞争窗口。 -1- 

http://www.paper.edu.cn 3. 加权一阶局域法预测法 人们一般用线性方法来预测时间序列，然而任何一个系统都是一个开放的系统，而且绝 大部分系统都是不可逆的，这两个基本特征决定了站点数量是一个复杂的非线性系统。因此， 要客观的分析站点量，就必须正确研究系统中的非线性。混沌理论正好为这些现象提供了理 论和方法。事实上，用混沌来处理时间序列已经得到广泛应用，比如在电力，证券市场和水 利项目等。 常用的混沌系统的预测方法有[3]：全域预测法、局域法、加权零阶局域法、加权一阶局 域法，基于神经网络的混沌预测法等。大量的实际应用和数值表明：一般情况下，局域法的 预测效果要好于全域法；一阶局域法的预测效果要好于零阶局域法；而且全域法预测也有其 缺点：一般计算比较复杂，特别是当嵌入维数很高或者 f 很复杂时。 局域法是将相空间轨迹的最后一点作为中心点，把离中心最近的若干轨迹点作为相关 点，然后对这些 相关点作出拟合，再估计下一点的走向，最后从预测出的轨迹点的坐标中 分离出所需要的预测值。 加权一阶局域法的具体算法是[4]： （1）重构相空间。根据 G-P 算法计算出序列的关联维数 d,再由 Takens 定理选取嵌入维 数 m,得到我们想要的空间。 （2）寻找邻近点。在相空间中计算各点到中心点 kY 的参考向量为 kiY , i=1,2,…,q ,并且 点 kiY 到 kY 的距离为 id ,设 md 是 id 中的最小值，定义点 kiY 的权值为 Pi = ( − α di dm − )] ( α − di dm − )] exp[ q ∑ exp[ i 1 = ⎞ ⎟ a ⎛ ⎞ ⎟ ⎜ ⎟ ⎟⎝ ⎠ b ⎟ ⎟ ⎠ , M Y kq+1 M e M Y kq α为参数，一般取α=1 （3）进行计算预测。一阶加权局域线形拟合为 Y k1 Y k2 Y k1 1 + Y k2 1 + e e ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 其中 e = 1 ⎛ ⎞ ⎜ ⎟ 1 ⎜ ⎟ ⎜ ⎟ M ⎜ ⎟ 1 ⎝ ⎠ m 我们就 m=2 的情况进行讨论 -2- 

http://www.paper.edu.cn X X X X M X X ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ k1 1 + k1 2 + k2 1 + k1 2 + kq+1 k1 2 + ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ = ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Xe Xe e X e X k1 k1+1 k2 k2+1 M M e X e X kq kq+1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ （*） a ⎛ ⎞ ⎜ ⎟ b ⎝ ⎠ , 应用加权最小二乘法有 q m ∑ ∑ Pi i 1 = j 1 = (X ki + j − − a bX ki j 1 + − ) min 2 = 将上式看成是关于未知数 a ,b 的二元函数，两边求偏导得到: q m ∑ ∑ Pi i 1 = j 1 = q m ∑ ∑ Pi i 1 = j 1 = (X ki + j − − a bX ki j 1 + − ) 0 = (X ki + j − − a bX ki j 1 + − )X ki j 1 + − = 0 ⎧ ⎪ ⎪ ⎨ ⎪ ⎪⎩ 化简得到关于未知数 a, b 的方程为: q m q m a ∑∑ ∑∑ P b + i PX i ki j 1 + − i 1 j 1 = = q m a ∑∑ PX i ki j 1 + − b + i 1 j 1 = = q m ∑∑ Pi X 2 ki j 1 + − q m i ∑∑ 1 j 1 = = q m ∑∑ = = PX i ki + j ki + j-1 PiX X ki + j ⎧ ⎪ ⎪ ⎨ ⎪ ⎪⎩ i 1 j 1 = = i 1 j 1 = = 解方程组得到 a、b, 然后带入式 （*）得预测公式。 （4）根据预测公式进行预测 1 j 1 = = i 每次计算出的向量 k 1Y + 的最后一个数值即为要预测的数值。将预测的数值加入到已知数 Y + = k 1 Y ae b k + 据数组的最后，继续预测下一个数值。 4. 预测结果 我们以我们学校 2006 年某月 1 号到 25 号站点数的数据为基础，对该月后 5 天的站点数 m + = 。为了提高精度，每预测出一 进行预测。我们选取嵌入维数为 7，相邻点的个数为 1 8 个月的值之后，重新计算权值，根据已经预测的数值在进行下一点的预测，在一定程度上提 高了预测精度。 下图是根据加权一阶局域法进行仿真的结果： -3- 

http://www.paper.edu.cn 图 1 根据加权一阶局域法仿真的结果 5. 结论 影响站点数的因素是多方面的，本文用混沌时间序列加权一阶局域法做预测，并以某月 前 25 天的站点数为基础，对后 5 天的站点数进行预测，收到了比较满意的效果。遗憾的是 没有动态计算嵌入维数和邻近点数，从而使得预测数值随真实数值的变化趋势不是很明显， 一定程度上影响了预测误差。 -4- 

http://www.paper.edu.cn 参考文献 [1] F.Cali, M.Conti and E.Gregori, “IEEE 802.11 Wireless Lan: Capacity Analysis and Protocol Enhancement.” In Proceedings of INFOCOM[J]: 142-149, March 1998. [2]黎春兰.论混沌理论在 MIS 中的应用[J].现代情报，2004 年 第 11 期：216－217。 [3]吕金虎，陆君安，陈士华.《混沌时间序列分析及其应用》[M], 武汉：武汉大学出版社，2002。 [4]利小玲，邓兵 基于混沌方法的预测技术及其应用[J].技术与市场（上半月），2006 年 第 5 期：60－61。 WLAN station number forecast based on adding-weight one-rank local-region method School of Electronic engineering, Beijing University of Posts and Telecommunications, Sun Changxin Beijing (100876) Abstract Much research of WLAN had focused on analysis of station number’s influence on the system throughput, while the station number forecast study stayed inadequate. Precise forecast of the real-time station number is very important in the WLAN performance control. In this paper, we use the latest method of the forecast statics-- adding-weight one-rank local-region method, and forecast the station number. The experiment simulation proved the forecast is very effective. Keywords: Chaotic Time Series, Adding-weight One-rank Local-region Method,Correlation Dimension, Proximal Point -5-