本申请涉及通信技术领域，尤其涉及如何提高提取无线接入点的邻居的准确性，和扩大方法的适用范围等的问题。本申请实施例提供无线访问接入点的邻居提取系统、方法及相关装置。该方案中，基于终端设备必然要发送的广播探测请求，来实现对AP邻居关系的提取，这样无需终端支持特殊的协议。因为广播探测请求是终端设备接入AP必然发送的，也不会对终端设备当前的业务造成影响。无需AP扫描，将可以节约AP的处理资源，使得AP能够更好的为终端设备提供服务。服务器通过采集大量的初始信息，基于马尔科夫状态转移矩阵提取出AP之间的邻居关系，由于运用马尔科夫状态转移矩阵的特性，比简单的根据信号强度提前邻居关系更加准确和可靠。
无线访问接入点的邻居提取系统、方法及相关装置
技术领域
[0001] 本申请涉及通信技术领域，尤其涉及无线访问接入点的邻居提取系统、方法及相关装置。
背景技术
[0002] 随着通信技术的不断发展和完善，人们对于AP(Wireless Access Point，无线访问接入点)的使用需求也越来越高。AP之间的邻居关系可以为后续信道规划，功率调整，终端漫游决策等提供数据支撑。
[0003] 相关技术中通常通过以下两种方法来确定AP之间的邻居关系：
[0004] 方法一、通过AP间相互扫描的方式获取邻居信息。例如，假设共有10个AP，分别称为AP1、AP2……AP10。AP1可以扫描到其周围的AP按照信号强度大小的顺序依次为AP2、AP3、AP4。则说明AP2、AP3、AP4距离AP1较近。
[0005] 方法二、通过特殊的协议发起终端扫描请求，终端扫描采集周围AP信息后上报，进而得到AP之间的邻居关系。
[0006] 发明人发现，现有方法一中，AP为终端提供接入的信道和扫描信道不同。故此，AP扫描需要切换信道，当AP切换了信道去扫描其他AP的信息，若有终端在这个AP的原工作信道发起接入请求，将导致AP错过终端此次请求，难以为终端提供服务。此外，AP扫描采集到的邻居信息是以AP角度的信息。现实中，经常可能出现两台AP物理部署点位邻近，但是中间由于障碍物的影响，导致AP相互感知到对方的信号强度较弱，此时若远处AP的信号强度较高，将导致提取的邻居关系中明明距离较近的AP却误认为是距离较远的AP。得到的失真的邻居关系，将导致后续工作的失误。例如，若将错误的邻居关系导入自动化信道规划，很可能导致紧邻的AP同频，造成严重的同频干扰。
[0007] 对于方法二、终端扫描采集周围AP信息，则需要终端支持特殊的协议。故此，该方法的适用范围有限。而终端扫描同样也会占用终端的资源，对终端当前业务造成影响。由于终端的多样性，如不同终端的扫描灵敏度各不相同，或者不同终端可能存在各式各样的限制，这样采集到的AP信息的度量标准亦各不相同。故此，得到邻居关系的准确性也有待提高。
[0008] 此外，方法1和方法2均是简单的根据信号强度提取邻居关系，提取邻居关系的准确性也有待提高。
[0009] 综上所述，需要一种新的无线访问接入点的邻居提取方法，提高邻居概念性确定的准确性和适用性。
发明内容
[0010] 本申请实施例提供无线访问接入点的邻居提取系统、方法及相关装置，用以解决现有技术中存在的AP邻居关系的获取准确性低、适用范围有限等的问题。
[0011] 第一方面，本申请实施例提供一种无线访问接入点的邻居提取系统，所述系统包括：
[0012] 终端设备，用于发送广播探测请求给无线访问接入点AP；广播探测请求中包括终端设备的设备标识以及终端设备的信号强度；
[0013] AP，用于接收广播探测请求后，从广播探测请求中提取设备标识以及信号强度；并生成初始信息发送给邻居提取设备，其中，初始信息中包括设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；
[0014] 邻居提取设备，用于接收多个AP发送的初始信息并存储至初始信息集合中；从初始信息集合中提取指定时间段内的设备标识相同的初始信息；针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，在每个AP排序对应的评分矩阵中、高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；并，针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量；根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0015] 第二方面，本申请实施例提供的一种无线访问接入点的邻居提取方法，包括：
[0016] 接收多个无线访问接入点AP发送的初始信息并存储至初始信息集合中，其中，针对每个AP，该AP的初始信息为该AP根据接收到的广播探测请求生成的；初始信息中包括发送广播探测请求的终端设备的设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；
[0017] 从初始信息集合中提取指定时间段内的设备标识相同的初始信息；
[0018] 针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0019] 确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；
[0020] 确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；并，
[0021] 针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；
[0022] 求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量；
[0023] 根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0024] 进一步的，所述初始信息中还包括AP接收广播探测请求的接收时间，和/或初始信息集合中包括各初始信息的接收时间；所述方法还包括：
[0025] 根据以下方法确定指定时间段：
[0026] 若发送初始信息的多个AP之间时钟同步，则根据所述广播探测请求的接收时间确定指定时间段，或者根据初始信息的接收时间确定指定时间段；
[0027] 若所述多个AP之间时钟不同步，则根据初始信息的接收时间确定指定时间段。
[0028] 进一步的，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序，具体包括：
[0029] 根据信号强度由大到小的顺序、对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0030] 确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1，具体包括：
[0031] 针对AP排序集中的每个AP排序，生成该AP排序对应的评分矩阵pk(i,j)，其中，k表示该AP排序在AP排序集中的序号，i表示评分矩阵中的第i行并表示第i个AP标识，j表示评分矩阵的第j列并表示第j个AP标识，每个AP标识给AP排序集中的所有AP标识评分，将相应评分填入pk(i,j)矩阵；
[0032] 其中，pk(i,j)矩阵的生成满足以下条件：
[0033] 1)、同一AP标识给所有AP标识的评分置于同一行或者同一列；
[0034] 2)、同一AP标识给各所有AP标识的评分之和为1；
[0035] 3)、同一AP标识给所有AP标识的评分，遵循高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分的原则；
[0036] 4)、不在AP排序中的AP标识不具有为所有AP标识评分的资格。
[0037] 进一步的，若同一AP标识给所有AP标识的评分置于同一行，则针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵，具体包括：
[0038] 根据以下公式将AP排序集中各评分矩阵相同位置的元素进行累加得到该位置的元素累加值，由累加值构成累加值矩阵；
[0039]
[0040] Pk＝(pk(i,j))n×n
[0041] 其中，PT表示累加值矩阵；n表示AP排序集中AP标识的个数；Nm表示AP排序集中AP排序的总数；j表示评分矩阵的第j列并表示第j个AP标识；i表示评分矩阵中的第i行并表示第i个AP标识；
[0042] 对累加值矩阵进行归一化，其中，归一化前后各位置元素的相对大小关系不变，且，若同一AP标识给所有AP标识的评分置于同一行，则归一化后矩阵的每一行的和值均为1；若同一AP标识给所有AP标识的评分置于同一列，则归一化后矩阵的每一列的和值均为1。
[0043] 进一步的，所述方法还包括：
[0044] 根据以下公式对得到的马尔可夫矩阵进行优化：
[0045] pM＝α×p+(1-α)×((e*eT)/n)
[0046] 其中，pM表示优化后的马尔可夫状态转移矩阵；α表示权值系数；p表示马尔可夫状态转移矩阵；e表示n维全1向量；n表示AP排序集中所有AP标识的数量；
[0047] 求解马尔可夫状态转移矩阵的稳态平衡条件，具体包括：
[0048] 求解优化后的马尔可夫状态转移矩阵的稳态平衡条件。
[0049] 进一步的，所述方法还包括：
[0050] 接收多个AP发送的邻居信息；该邻居信息中包括扫描到的至少一个AP标识对应的AP的信号强度；
[0051] 根据信号强度由大到小的顺序对各邻居信息中的AP标识进行排序得到AP序列；其中，每条邻居信息对应一个AP序列；
[0052] 针对发送邻居信息的每个AP，将该AP作为基准AP，确定基准AP相同的AP序列作为AP序列集；
[0053] 确定AP序列集中所有AP标识，并针对该AP序列集中的每个AP序列，确定该AP序列中每个AP标识对该AP序列集中所有AP标识的评分得到AP评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP序列集中所有AP标识的评分值之和为1；并，
[0054] 针对AP评分矩阵中每个元素，根据该元素的预设权重因子，求得该元素在马尔可夫概率转移矩阵中的对应值，得到的马尔可夫概率转移矩阵作为附加马尔科夫状态转移矩阵；
[0055] 根据以下公式对马尔可夫状态转移矩阵进行优化得到最终的马尔可夫状态转移矩阵；
[0056] pMnew＝α×pap+β×p+ε×((e*eT)/n)
[0057] 其中，α+β+ε＝1
[0058] pMnew表示最终的马尔可夫状态转移矩阵；pap表示附加马尔科夫状态转移矩阵；p表示马尔可夫状态转移矩阵；e为n维全1向量；n表示AP排序集中所有AP标识的数量，α表示权值系数；β为第一预设系数；ε为第二预设系数。
[0059] 进一步的，确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，所述方法还包括：
[0060] 确定AP排序集满足预设条件，该预设条件包括：AP排序集中的AP排序的数量大于指定数量，和/或，AP排序集中各AP排序中的最大信号强度大于预设强度。
[0061] 进一步的，确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，所述方法还包括：
[0062] 针对每组AP排序，将基准AP标识对应的射频口标识作为基准射频口标识，并将该组AP排序中对应的射频口标识与基准射频口标识不同的AP标识删除。
[0063] 第三方面，本申请实施例提供的一种无线访问接入点的邻居提取装置，包括：
[0064] 存储模块，用于接收多个无线访问接入点AP发送的初始信息并存储至初始信息集合中，其中，针对每个AP，该AP的初始信息为该AP根据接收到的广播探测请求生成的；初始信息中包括发送广播探测请求的终端设备的设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；
[0065] 提取模块，用于从初始信息集合中提取指定时间段内的设备标识相同的初始信息；
[0066] AP排序模块，用于针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0067] AP排序集确定模块，用于确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；
[0068] 评分矩阵确定模块，用于确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；
[0069] 转移矩阵确定模块，用于针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；
[0070] 特征向量确定模块，用于求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量；
[0071] 邻居提取模块，用于根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0072] 进一步的，所述初始信息中还包括AP接收广播探测请求的接收时间，和/或初始信息集合中包括各初始信息的接收时间；所述装置还包括：
[0073] 指定时间段确定模块，用于根据以下装置确定指定时间段：
[0074] 若发送初始信息的多个AP之间时钟同步，则根据所述广播探测请求的接收时间确定指定时间段，或者根据初始信息的接收时间确定指定时间段；
[0075] 若所述多个AP之间时钟不同步，则根据初始信息的接收时间确定指定时间段。
[0076] 进一步的，AP排序集确定模块，具体用于根据信号强度由大到小的顺序、对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0077] 评分矩阵确定模块，具体用于针对AP排序集中的每个AP排序，生成该AP排序对应的评分矩阵pk(i,j)，其中，k表示该AP排序在AP排序集中的序号，i表示评分矩阵中的第i行并表示第i个AP标识，j表示评分矩阵的第j列并表示第j个AP标识，每个AP标识给AP排序集中的所有AP标识评分，将相应评分填入pk(i,j)矩阵；
[0078] 其中，pk(i,j)矩阵的生成满足以下条件：
[0079] 1)、同一AP标识给所有AP标识的评分置于同一行或者同一列；
[0080] 2)、同一AP标识给各所有AP标识的评分之和为1；
[0081] 3)、同一AP标识给所有AP标识的评分，遵循高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分的原则；
[0082] 4)、不在AP排序中的AP标识不具有为所有AP标识评分的资格。
[0083] 进一步的，若同一AP标识给所有AP标识的评分置于同一行，转移矩阵确定模块，具体用于根据以下公式将AP排序集中各评分矩阵相同位置的元素进行累加得到该位置的元素累加值，由累加值构成累加值矩阵；
[0084]
[0085] Pk＝(pk(i,j))n×n
[0086] 其中，PT表示累加值矩阵；n表示AP排序集中AP标识的个数；Nm表示AP排序集中AP排序的总数；j表示评分矩阵的第j列并表示第j个AP标识；i表示评分矩阵中的第i行并表示第i个AP标识；
[0087] 对累加值矩阵进行归一化，其中，归一化前后各位置元素的相对大小关系不变，且，若同一AP标识给所有AP标识的评分置于同一行，则归一化后矩阵的每一行的和值均为1；若同一AP标识给所有AP标识的评分置于同一列，则归一化后矩阵的每一列的和值均为1。
[0088] 进一步的，所述装置还包括：
[0089] 第一优化模块，用于根据以下公式对得到的马尔可夫矩阵进行优化：
[0090] pM＝α×p+(1-α)×((e*eT)/n)
[0091] 其中，pM表示优化后的马尔可夫状态转移矩阵；α表示权值系数；p表示马尔可夫状态转移矩阵；e表示n维全1向量；n表示AP排序集中所有AP标识的数量；
[0092] 特征向量确定模块，具体用于求解优化后的马尔可夫状态转移矩阵的稳态平衡条件。
[0093] 进一步的，所述装置还包括：
[0094] 邻居信息接收模块，用于接收多个AP发送的邻居信息；该邻居信息中包括扫描到的至少一个AP标识对应的AP的信号强度；
[0095] AP序列确定模块，用于根据信号强度由大到小的顺序对各邻居信息中的AP标识进行排序得到AP序列；其中，每条邻居信息对应一个AP序列；
[0096] AP序列集确定模块，用于针对发送邻居信息的每个AP，将该AP作为基准AP，确定基准AP相同的AP序列作为AP序列集；
[0097] AP评分矩阵确定模块，用于确定AP序列集中所有AP标识，并针对该AP序列集中的每个AP序列，确定该AP序列中每个AP标识对该AP序列集中所有AP标识的评分得到AP评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP序列集中所有AP标识的评分值之和为1；
[0098] 附加转移矩阵确定模块，用于针对AP评分矩阵中每个元素，根据该元素的预设权重因子，求得该元素在马尔可夫概率转移矩阵中的对应值，得到的马尔可夫概率转移矩阵作为附加马尔科夫状态转移矩阵；
[0099] 第二优化模块，用于根据以下公式对马尔可夫状态转移矩阵进行优化得到最终的马尔可夫状态转移矩阵；
[0100] pMnew＝α×pap+β×p+ε×((e*eT)/n)
[0101] 其中，α+β+ε＝1
[0102] pMnew表示最终的马尔可夫状态转移矩阵；pap表示附加马尔科夫状态转移矩阵；p表示马尔可夫状态转移矩阵；e为n维全1向量；n表示AP排序集中所有AP标识的数量，α表示权值系数；β为第一预设系数；ε为第二预设系数。
[0103] 进一步的，所述装置还包括：
[0104] 第三优化模块，用于在评分矩阵确定模块确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，确定AP排序集满足预设条件，该预设条件包括：AP排序集中的AP排序的数量大于指定数量，和/或，AP排序集中各AP排序中的最大信号强度大于预设强度。
[0105] 进一步的，所述装置还包括：
[0106] 第四优化模块，用于在评分矩阵确定模块确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，针对每组AP排序，将基准AP标识对应的射频口标识作为基准射频口标识，并将该组AP排序中对应的射频口标识与基准射频口标识不同的AP标识删除。
[0107] 第四方面，本申请另一实施例还提供了一种计算设备，其包括存储器和处理器，其中，所述存储器用于存储程序指令，所述处理器用于调用所述存储器中存储的程序指令，按照获得的程序指令执行本申请实施例中的任一无线访问接入点的邻居提取方法。
[0108] 第五方面，本申请另一实施例还提供了一种计算机存储介质，其中，所述计算机存储介质存储有计算机可执行指令，所述计算机可执行指令用于使所述计算机执行本申请实施例中的任一无线访问接入点的邻居提取方法。
[0109] 本申请实施例中，基于终端设备必然要发送的广播探测请求，来实现对AP邻居关系的提取，这样无需终端支持特殊的协议。因为广播探测请求是终端设备接入AP必然发送的，也不会对终端设备当前的业务造成影响。无需AP扫描，将可以节约AP的处理资源，使得AP能够更好的为终端设备提供服务。服务器通过采集大量的初始信息，基于马尔科夫状态转移矩阵提取出AP之间的邻居关系，由于运用马尔科夫状态转移矩阵的特性，比简单的根据信号强度提前邻居关系更加准确和可靠。
附图说明
[0110] 图1所示为本申请实施例提供的无线访问接入点的邻居提取方法的应用场景示意图；
[0111] 图2所示为本申请实施例一提供的无线访问接入点的邻居提取方法的流程示意图；
[0112] 图3所示为本申请实施例二提供的无线访问接入点的邻居提取装置的结构示意图；
[0113] 图4所示为本申请实施例三提供的无线访问接入点的邻居提取系统的结构示意图；
[0114] 图5所示为本申请实施例四提供的计算设备的结构示意图。
具体实施方式
[0115] 为了便于理解本申请实施例提供的技术方案，下面结合说明书附图对本申请实施例作进一步详细描述。
[0116] 发明人研究发现，终端设备接入AP之前，在短时间(如1秒内)在多个信道发起广播探测请求(probe request)，终端设备周围各AP将接收到该终端设备的广播探测请求。该广播探测请求中将包括终端设备的设备标识以及终端设备的信号强度。多个AP接收的同一终端设备的广播探测请求将是对于该终端设备来说其周围的AP的邻居关系。此外，实际使用过程中，同一终端设备在同一个点位可以每间隔几分钟甚至更短的频率发起探测请求，同一终端设备同样可在不同点位发起探测请求，以及不同终端设备亦可在不同地点，不同时间发起广播探测请求。这样，发起广播探测请求的点位有可能位于网络的边缘，有可能位于网络的中心。故此，汇集同一终端设备的广播探测请求可以从中挖掘出不同地点、不同时间的AP的邻居关系。
[0117] 基于这一原理，首先参考图1其为本申请实施例提供的无线访问接入点的邻居提取方法的应用场景示意图。该场景例如可以包括用户10、终端设备11、服务器12和AP13。其中，所述终端设备11中可安装有各种客户端，如新闻客户端、视频客户端、网购客户端等。终端设备11通过AP13接入网络。AP13与服务器12建立通信连接。终端设备11发送广播探测请求，其周围的AP13接收到该广播探测请求后，从广播探测请求中提取设备标识以及信号强度；并生成初始信息发送给服务器12，其中，初始信息中包括设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识。服务器12接收多个AP发送的初始信息并存储至初始信息集合中；从初始信息集合中提取指定时间段内的设备标识相同的初始信息；针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，在每个AP排序对应的评分矩阵中、高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；并，针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量；根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0118] 这样，相当于实现了基于终端设备必然要发送的广播探测请求，来实现对AP邻居关系的提取，这样无需终端支持特殊的协议。因为广播探测请求是终端设备接入AP必然发送的，也不会对终端设备当前的业务造成影响。无需AP扫描，将可以节约AP的处理资源，使得AP能够更好的为终端设备提供服务。服务器12通过采集大量的初始信息，基于马尔科夫状态转移矩阵提取出AP之间的邻居关系，由于运用马尔科夫状态转移矩阵的特性，比简单的根据信号强度提前邻居关系更加准确和可靠。
[0119] 其中，服务器12可以为任何能够支持相应的无线访问接入点的邻居提取方法的服务器设备。
[0120] 实施例一
[0121] 参照图2，为本申请实施例一提供的无线访问接入点的邻居提取方法流程图，应用于邻居提取设备中，该邻居提取设备可以如前述的服务器，当然也可以是任何能够提供大数据分析计算的设备。
[0122] 此外，需要说明的是，本申请实施例提供的方法，能够适用于胖AP也能够适用于瘦AP。
[0123] 具体的，该方法包括以下步骤：
[0124] 步骤201：接收多个无线访问接入点AP发送的初始信息并存储至初始信息集合中，其中，针对每个AP，该AP的初始信息为该AP根据接收到的广播探测请求生成的；初始信息中包括发送广播探测请求的终端设备的设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识。
[0125] 其中，为了便于读取和处理信息，初始信息集合可以为数据库的形式构建。
[0126] 步骤202：从初始信息集合中提取指定时间段内的设备标识相同的初始信息。
[0127] 其中，在一个实施例中，AP之间的邻居关系最终还是为终端设备服务的。所以本申请实施例是从终端设备的视角来确定AP之间的邻居关系，为了能够准确确定同一时间段内相对于终端设备而言AP之间的邻居关系，提高确定邻居关系的准确性，所述初始信息中还包括AP接收广播探测请求的接收时间，和/或初始信息集合中包括各初始信息的接收时间。则，具体实施时，可以根据以下方法确定指定时间段：
[0128] 方法1：若发送初始信息的多个AP之间时钟同步，则根据所述广播探测请求的接收时间确定指定时间段，或者根据初始信息的接收时间确定指定时间段。
[0129] 方法2：若所述多个AP之间时钟不同步，则根据初始信息的接收时间确定指定时间段。
[0130] 这样，通过统一的时间标准获取指定时间段，相当于实现对同一时期各终端设备的广播探测请求进行处理，从而提高确定邻居关系的准确性。
[0131] 步骤203：针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序。
[0132] 具体实施时，可以按照信号强度从大到小的顺序进行排序，也可以按照信号强度从小到大的顺序进行排序。
[0133] 例如，终端设备1来说，其对不同AP的信号强度如表1所示。
[0134] 表1终端设备1对不同AP的信号强度
[0135]AP1 50
AP2 60
AP3 30
[0136] 则，按照信号强度从大到小的顺序，根据表1得到的一组AP排序为(AP2、AP1、AP3)。AP1对应的信号强度为50、AP2对应的信号强度为60、AP3对应的信号强度为30。
[0137] 步骤204：确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集。
[0138] 例如，按照信号强度由大到小的顺序排序时，AP排序共有三组包括：
[0139] 第一组：(AP1、AP2、AP3)
[0140] 第二组：(AP1、AP3、AP4、AP5)
[0141] 第三组：(AP2、AP3、AP5、AP6)
[0142] 则，由于第一组和第二组最大信号强度对应的AP标识相同、均为AP1，则由第一组和第二组构成AP排序集。
[0143] 步骤205：确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1。
[0144] 继续上面的例子，第一组和第二组构成AP排序集。则，AP排序集中所有AP标识包括AP1、AP2、AP3、AP4、AP5。
[0145] 则，针对第一组，以AP1对AP1、AP2、AP3、AP4、AP5进行评分为例，AP1对应信号强度最大，故此，其自身评分最高，然后依次评分由高到底的顺序为AP2、AP3，由于第一组AP排序中不包含AP4和AP5，所以AP4和AP5得到的评分最低。
[0146] 进一步的，具体实施时，一般获取同频段的AP邻居关系，具有更高的使用价值，故此，执行步骤205之前，所述方法还包括：针对每组AP排序，将基准AP标识对应的射频口标识作为基准射频口标识，并将该组AP排序中对应的射频口标识与基准射频口标识不同的AP标识删除。射频口标识不同，即频段不同，这样，实现了保证AP排序集中都是同频段的数据。
[0147] 步骤206：针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵。
[0148] 步骤207：求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量。
[0149] 其中，具体实施时，可以根据矩阵分解例如奇异值分解或特征值分解得到该特征向量，当然也可以采取现有技术的其它求得马尔可夫状态转移矩阵的稳态平衡条件的方法确定特征向量，均适用于本申请实施例。
[0150] 步骤208：根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0151] 例如，AP1为基准AP标识，其特征向量[0.3643,0.3381,0.3390,0.3286,0.3135,0.3035,0.2939,0.2848,0.2762,0.3097]T，表示AP1的邻居相对远近关系为：AP3>AP2>AP4>AP5>AP10>AP6>AP7>AP8>AP9。
[0152] 综上所述，采用该种方式确定邻居关系的原理：通俗的说就是将终端设备探测的信号强度归一化为可以反映不同AP的转移概率，一次探测里，感知到信号强度大的AP距离相对就近，信号强度弱的就相对远，但是不同终端不同时间点发起探测位于的点位各不同，马尔可夫状态转移矩阵的特性提供了融合这些数据的理论基础。使得AP邻居关系的确定不仅依赖于信号强度，提高了确定邻居关系的准确性。
[0153] 为了便于进一步理解本申请实施例提供的技术方案，下面对此进行进一步说明。
[0154] 其，在一个实施例中，若根据信号强度由大到小的顺序、对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；则，步骤205中确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1，可具体包括：
[0155] 针对AP排序集中的每个AP排序，生成该AP排序对应的评分矩阵pk(i,j)，其中，k表示该AP排序在AP排序集中的序号，i表示评分矩阵中的第i行并表示第i个AP标识，j表示评分矩阵的第j列并表示第j个AP标识，每个AP标识给AP排序集中的所有AP标识评分，将相应评分填入pk(i,j)矩阵；
[0156] 其中，pk(i,j)矩阵的生成满足以下条件：
[0157] 1)、同一AP标识给所有AP标识的评分置于同一行或者同一列。
[0158] 2)、同一AP标识给各所有AP标识的评分之和为1。
[0159] 3)、同一AP标识给所有AP标识的评分，遵循高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分的原则。
[0160] 4)、不在AP排序中的AP标识不具有为所有AP标识评分的资格。
[0161] 为便于理解，上述1)-4)的规则，这里举例进行说明：
[0162] 假设整网存在10个AP，AP标识分别为1-10。若存在一个AP排序为1，4，6，3(以后简称为排序1)。表示对于终端的此次探测，AP1感知到的信号强度大于AP4，AP4感知到的信号强度大于AP6，AP6感知到的信号强度又大于AP3。对于未出现在该排序1中的其他AP，说明没有探测到终端的此次探测，因此形成排序1中的成员仅包括1，4，6，3。
[0163] 参照表1为得到的排序1的评分矩阵。下面结合表1对确定该评分矩阵pk(i,j)的方法进行说明。这里设排序1在AP排序集合中的序号k为1，要计算的矩阵pk(i,j)为p1(i,j)，同时，下面的例子中以同一AP标识给所有AP标识的评分置于同一行为例，
[0164] 由于AP2，AP5，AP7，AP8，AP9，AP10不出现在排序1中，这些AP不给其他AP打分。为了便于矩阵运算，保证评分矩阵的行数和列数相同，可以假设这些AP不给其他AP的评分为0。因此，在排序1的评分矩阵中第二行，即p1(2,1)～p1(2,10)的各元素均为0。同理，p1(5,1)～p1(5,10)各元素也均为0，依次类推，第7，8，9，10行各元素也均为0。
[0165] 表1中第1行，为AP1给出的评分，由于AP1排在第一个，没有其他AP排名超过AP1，因此，AP1给自己评分为1，给其余AP评分可以均为0。因此，矩阵p1(i,j)第一行，p1(1,1)为1，其余为0。
[0166] 表1中第4行为AP4给出的评分，由于AP1排名最前，AP4可给AP1的评分为1/10，AP4给其他AP的评分均为0，剩余9/10的分数可归为AP4给自己的评分，因此p1(4,1)为1/10，p1(4,4)为9/10，此行其他各元素均为0。
[0167] 表1中第6行为AP6给出的评分，AP6可给AP1可打分1/10，AP6可给AP4可打分1/10，AP6给其他AP打分均为0，剩余8/10的分数可归为自己给自己打分，因此p1(6,1)为1/10，p1(6,4)为1/10，p1(6,6)为9/10，此行其他各元素分数为0。
[0168] 表1中第3行为AP3给出的评分，AP3给AP1打分p1(3,1)1/10，AP3给AP4打分p1(3,4)1/10，AP3给AP6打分p1(3,6)1/10，AP3给其他AP打分为0分，剩余7/10得分可归属为自身p1(3,3)。
[0169] 经过以上说明，生成p1(i,j)矩阵。
[0170] 表2排序1对应的评分矩阵
[0171]
[0172] 进一步的，由以上说明可知，AP排序集中每个AP排序对应1个评分矩阵。接下来，本申请实施例中步骤206可具体执行为：
[0173] 将各评分矩阵相同位置的元素进行累加得到该位置的元素累加值，由元素累加值按照原有位置排列得到累计值矩阵，并对累加值矩阵进行归一化后，进一步得到马尔可夫状态转移矩阵。具体的包括以下步骤A1-步骤A：
[0174] 步骤A1：根据以下公式将各评分矩阵相同位置的元素进行累加得到该位置的元素累加值：
[0175]
[0176] Pk＝(pk(i,j))n×n
[0177] 其中，n表示AP排序集中AP标识的个数；Nm表示AP排序集中AP排序的总数；j表示评分矩阵的第j列并表示第j个AP标识；i表示评分矩阵中的第i行并表示第i个AP标识。
[0178] 步骤A2：对累加值矩阵进行归一化，其中，归一化前后各位置元素的相对大小关系不变，且，若同一AP标识给所有AP标识的评分置于同一行，则归一化后矩阵的每一行的和值均为1；若同一AP标识给所有AP标识的评分置于同一列，则归一化后矩阵的每一列的和值均为1。
[0179] 例如：以同一AP标识给所有AP标识的评分置于同一行(即按行评分方式为例)，假设Nm为4，说明排序集合存在4组排序。这四组排序分别为：
[0180] {(1，4，6，3)，(1，6，4，3，8)，(1，4，6)，(1，6，5)}
[0181] 同样，这里选取按行评分方式，第一组AP排序数据(1，4，6，3)得到的评分矩阵p1(i,j)如表3所示：
[0182] 表3第一组AP排序的评分矩阵
[0183] 1.0000 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0.1000 0 0.7000 0.1000 0 0.1000 0 0 0 0
0.1000 0 0 0.9000 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0 0.1000 0 0.8000 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
[0184] 第二组AP排序数据(1，6，4，3，8)得到的评分矩阵p2(i,j)如表4所示：
[0185] 表4第二组AP排序的评分矩阵
[0186]
[0187]
[0188] 第三组AP排序数据(1，4，6)得到的评分矩阵p3(i,j)如表5所示：
[0189] 表5第三组AP排序的评分矩阵
[0190] 1.0000 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0 0.9000 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0 0.1000 0 0.8000 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
[0191] 第四组AP排序数据(1，6，5)得到的评分矩阵p4(i,j)如表6所示：
[0192] 表6第四组AP排序的评分矩阵
[0193]1.0000 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0 0 0.8000 0.1000 0 0 0 0
0.1000 0 0 0 0 0.9000 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
[0194] 根据公式(1)，表3-表6四个评分矩阵相同位置得到的累加值构成的PT矩阵如表7所示：
[0195] 表7 PT矩阵
[0196]4.0000 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.2000 0 1.4000 0.2000 0 0.2000 0 0 0 0
0.3000 0 0 2.6000 0 0.1000 0 0 0 0
0.1000 0 0 0 0.8000 0.1000 0 0 0 0
0.4000 0 0 0.2000 0 3.4000 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0.1000 0.1000 0 0.1000 0 0.6000 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
[0197] 由于采用按行打分方式(即以同一AP标识给所有AP标识的评分置于同一行)，计算得到的VTO采用矩阵PT各行的累加，得到VTO向量为：
[0198] VTO＝[4,0,2,3,1 , 4,0,1,0,0]T
[0199] 将VTO为0元素替换为1后的VT为：
[0200] VT＝[4,1,2,3,1 , 4,1,1,1,1]T
[0201] 对VT各元素取倒数，得到向量V为：
[0202]
[0203] 进一步，可得到diag(V)对角矩阵如表8所示：
[0204] 表8 diag(V)对角矩阵
[0205]
[0206]
[0207] 根据公式(2)可得到以行为评分的归一化矩阵如表9所示：
[0208] P＝(p(i,j))n×n＝diag(V)×PT (2)
[0209] 表9以行为评分的归一化矩阵
[0210] 1.0000 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0
0.1000 0 0.7000 0.1000 0 0.1000 0 0 0 0
0.1000 0 0 0.8667 0 0.0333 0 0 0 0
0.1000 0 0 0 0.8000 0.1000 0 0 0 0
0.1000 0 0 0.0500 0 0.8500 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0.1000 0 0.1000 0.1000 0 0.1000 0 0.6000 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
[0211] 由于评分矩阵采用行作为同一AP给出的评分，因此再对表9的矩阵做转置，最终可得到马尔可夫状态转移矩阵P如表10所示：
[0212] 表10马尔可夫状态转移矩阵
[0213]
[0214]
[0215] 需要说明的是，归一化的方式可以根据实际需求确定即可，不限于本申请实施例提供的方法。
[0216] 进一步的，为了提高增加确定邻居关系的容错能力，本申请实施例中还可以根据以下公式(3)对得到的马尔可夫矩阵进行优化：
[0217] pM＝α×p+(1-α)×((e*eT)/n) (3)
[0218] 其中，pM表示优化后的马尔可夫状态转移矩阵；α表示权值系数；p表示马尔可夫状态转移矩阵；e表示n维全1向量；n表示AP排序集中所有AP标识的数量。这里，公式的后半部分为平滑系数矩阵，可用于消除矩阵中的非0元素。
[0219] 其中，较佳的，α可以取值0.8。当然具体实施时，可以根据实际情况确定，这里不做限定。
[0220] 则在公式(3)的基础上，求解马尔可夫状态转移矩阵的稳态平衡条件，可具体包括：求解优化后的马尔可夫状态转移矩阵的稳态平衡条件。
[0221] 进一步的，本申请实施例中还可以融合AP相互扫描获得的数据，来得到AP之间的邻居关系，该方法可包括：
[0222] 接收多个AP发送的邻居信息；该邻居信息中包括扫描到的至少一个AP标识对应的AP的信号强度；
[0223] 根据信号强度由大到小的顺序对各邻居信息中的AP标识进行排序得到AP序列；其中，每条邻居信息对应一个AP序列；
[0224] 针对发送邻居信息的每个AP，将该AP作为基准AP，确定基准AP相同的AP序列作为AP序列集；
[0225] 确定AP序列集中所有AP标识，并针对该AP序列集中的每个AP序列，确定该AP序列中每个AP标识对该AP序列集中所有AP标识的评分得到AP评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP序列集中所有AP标识的评分值之和为1；并，
[0226] 针对AP评分矩阵中每个元素，根据该元素的预设权重因子，求得该元素在马尔可夫概率转移矩阵中的对应值，得到的马尔可夫概率转移矩阵作为附加马尔科夫状态转移矩阵；
[0227] 也即对AP相互扫描的结果的进行处理的方法可以参照对初始信息的处理方法，原则上同样实现根据信号强度实现AP之间的评分。适用的原则包括：
[0228] 1)、同一AP标识给所有AP标识的评分置于同一行或者同一列。
[0229] 2)、同一AP标识给各所有AP标识的评分之和为1。
[0230] 3)、同一AP标识给所有AP标识的评分，遵循高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分的原则。
[0231] 4)、不在AP序列中的AP标识不具有为所有AP标识评分的资格。
[0232] 根据以下公式(4)对马尔可夫状态转移矩阵进行优化得到最终的马尔可夫状态转移矩阵；
[0233] pMnew＝α×pap+β×p+ε×((e*eT)/n) (4)
[0234] 其中，α+β+ε＝1
[0235] 在公式(3)中，pMnew表示最终的马尔可夫状态转移矩阵；pap表示附加马尔科夫状态转移矩阵；p表示马尔可夫状态转移矩阵；e表示n维全1向量；n表示AP排序集中所有AP标识的数量，α表示权值系数；β为第一预设系数；ε为第二预设系数。
[0236] 通过融合AP相互扫描得到的邻居关系，可以实现对AP邻居关系的更新。
[0237] 当然，具体实施时，可以获取最近一段时间的初始信息进行处理得到邻居关系。同样，也能够实现对AP邻居关系的更新。
[0238] 进一步的，公式(4)也同意适用于得到的初始信息数量少的情况，来弥补原始数据的不足，提高邻居关系确定的准确性。
[0239] 进一步的，为了滤除噪声数据，节约处理资源的同时得到准确的邻居关系，本申请实施例中并非对所有的拍续集分别进行处理。而是在确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，确定AP排序集满足预设条件，该预设条件包括：AP排序集中的AP排序的数量大于指定数量，和/或，AP排序集中各AP排序中的最大信号强度大于预设强度。
[0240] 这样，对于信号强度较小，或者邻居较少或者基本没有邻居的AP并不提取以其为基准的邻居关系。
[0241] 进一步的，需要说明的是，本申请实施例中构建马尔可夫状态转移矩阵的方法并不唯一，具体实施时，可以根据本申请实施例提供的原理进行构建。例如，可进一步深入量化马尔科夫状态转移矩阵，如考虑信号强度的具体数值的影响等。具体如公式(5)：在pk中每个成员pk(i,j)的计算方式：
[0242]
[0243] 其中，Rssi表示信号强度，Rssi越大,则相分占比相对于公式(1)越大，并且最终行向量的和值相加也为1；i表示AP标识；j表示AP标识。
[0244] 例如：对于终端的一次探测k，表11表示3个AP探测到信号强度。
[0245]AP1感知到的RSSI 50
AP2感知到的RSSI 60
AP3感知到的RSSI 30
[0246] 其余同行的元素为0，
[0247] 第二行其他元素为0，
[0248]第三行其他元素为0。
[0249] 实施例二
[0250] 基于相同的发明构思，本申请实施例还提供一种无线访问接入点的邻居提取装置，该装置的原理和有益效果与上述方法实施例中所述内容相似，在此不再赘述。
[0251] 如图3所示，为该装置的结构示意图，所述装置包括：
[0252] 存储模块301，用于接收多个无线访问接入点AP发送的初始信息并存储至初始信息集合中，其中，针对每个AP，该AP的初始信息为该AP根据接收到的广播探测请求生成的；初始信息中包括发送广播探测请求的终端设备的设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；
[0253] 提取模块302，用于从初始信息集合中提取指定时间段内的设备标识相同的初始信息；
[0254] AP排序模块303，用于针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0255] AP排序集确定模块304，用于确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；
[0256] 评分矩阵确定模块305，用于确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；
[0257] 转移矩阵确定模块306，用于针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；
[0258] 特征向量确定模块307，用于求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的最大特征值所对应的特征向量；
[0259] 邻居提取模块308，用于根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0260] 其中，在一个实施例中，所述初始信息中还包括AP接收广播探测请求的接收时间，和/或初始信息集合中包括各初始信息的接收时间；所述装置还包括：
[0261] 指定时间段确定模块，用于根据以下装置确定指定时间段：
[0262] 若发送初始信息的多个AP之间时钟同步，则根据所述广播探测请求的接收时间确定指定时间段，或者根据初始信息的接收时间确定指定时间段；
[0263] 若所述多个AP之间时钟不同步，则根据初始信息的接收时间确定指定时间段。
[0264] 其中，在一个实施例中，AP排序集确定模块，具体用于根据信号强度由大到小的顺序、对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；
[0265] 评分矩阵确定模块，具体用于针对AP排序集中的每个AP排序，生成该AP排序对应的评分矩阵pk(i,j)，其中，k表示该AP排序在AP排序集中的序号，i表示评分矩阵中的第i行并表示第i个AP标识，j表示评分矩阵的第j列并表示第j个AP标识，每个AP标识给AP排序集中的所有AP标识评分，将相应评分填入pk(i,j)矩阵；
[0266] 其中，pk(i,j)矩阵的生成满足以下条件：
[0267] 1)、同一AP标识给所有AP标识的评分置于同一行或者同一列；
[0268] 2)、同一AP标识给各所有AP标识的评分之和为1；
[0269] 3)、同一AP标识给所有AP标识的评分，遵循高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分的原则；
[0270] 4)、不在AP排序中的AP标识不具有为所有AP标识评分的资格。
[0271] 其中，在一个实施例中，若同一AP标识给所有AP标识的评分置于同一行，转移矩阵确定模块，具体用于根据以下公式将AP排序集中各评分矩阵相同位置的元素进行累加得到该位置的元素累加值，由累加值构成累加值矩阵；
[0272]
[0273] Pk＝(pk(i,j))n×n
[0274] 其中，PT表示累加值矩阵；n表示AP排序集中AP标识的个数；Nm表示AP排序集中AP排序的总数；j表示评分矩阵的第j列并表示第j个AP标识；i表示评分矩阵中的第i行并表示第i个AP标识；
[0275] 对累加值矩阵进行归一化，其中，归一化前后各位置元素的相对大小关系不变，且，若同一AP标识给所有AP标识的评分置于同一行，则归一化后矩阵的每一行的和值均为1；若同一AP标识给所有AP标识的评分置于同一列，则归一化后矩阵的每一列的和值均为1。
[0276] 其中，在一个实施例中，所述装置还包括：
[0277] 第一优化模块，用于根据以下公式对得到的马尔可夫矩阵进行优化：
[0278] pM＝α×p+(1-α)×((e*eT)/n)
[0279] 其中，pM表示优化后的马尔可夫状态转移矩阵；α表示权值系数；p表示马尔可夫状态转移矩阵；e表示n维全1向量；n表示AP排序集中所有AP标识的数量；
[0280] 特征向量确定模块，具体用于求解优化后的马尔可夫状态转移矩阵的稳态平衡条件。
[0281] 其中，在一个实施例中，所述装置还包括：
[0282] 邻居信息接收模块，用于接收多个AP发送的邻居信息；该邻居信息中包括扫描到的至少一个AP标识对应的AP的信号强度；
[0283] AP序列确定模块，用于根据信号强度由大到小的顺序对各邻居信息中的AP标识进行排序得到AP序列；其中，每条邻居信息对应一个AP序列；
[0284] AP序列集确定模块，用于针对发送邻居信息的每个AP，将该AP作为基准AP，确定基准AP相同的AP序列作为AP序列集；
[0285] AP评分矩阵确定模块，用于确定AP序列集中所有AP标识，并针对该AP序列集中的每个AP序列，确定该AP序列中每个AP标识对该AP序列集中所有AP标识的评分得到AP评分矩阵，其中，高信号强度对应的AP标识得到的评分不低于低信号强度对应的AP标识得到的评分、且同一AP标识对AP序列集中所有AP标识的评分值之和为1；
[0286] 附加转移矩阵确定模块，用于针对AP评分矩阵中每个元素，根据该元素的预设权重因子，求得该元素在马尔可夫概率转移矩阵中的对应值，得到的马尔可夫概率转移矩阵作为附加马尔科夫状态转移矩阵；
[0287] 第二优化模块，用于根据以下公式对马尔可夫状态转移矩阵进行优化得到最终的马尔可夫状态转移矩阵；
[0288] pMnew＝α×pap+β×p+ε×((e*eT)/n)
[0289] 其中，α+β+ε＝1
[0290] pMnew表示最终的马尔可夫状态转移矩阵；pap表示附加马尔科夫状态转移矩阵；p表示马尔可夫状态转移矩阵；e为n维全1向量；n表示AP排序集中所有AP标识的数量，α表示权值系数；β为第一预设系数；ε为第二预设系数。
[0291] 其中，在一个实施例中，所述装置还包括：
[0292] 第三优化模块，用于在评分矩阵确定模块确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，确定AP排序集满足预设条件，该预设条件包括：AP排序集中的AP排序的数量大于指定数量，和/或，AP排序集中各AP排序中的最大信号强度大于预设强度。
[0293] 其中，在一个实施例中，所述装置还包括：
[0294] 第四优化模块，用于在评分矩阵确定模块确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵之前，针对每组AP排序，将基准AP标识对应的射频口标识作为基准射频口标识，并将该组AP排序中对应的射频口标识与基准射频口标识不同的AP标识删除。
[0295] 实施例三
[0296] 基于相同的发明构思，本申请实施例还提供一种无线访问接入点的邻居提取系统，如图4所示，所述系统包括：
[0297] 终端设备401，用于发送广播探测请求给无线访问接入点AP；广播探测请求中包括终端设备的设备标识以及终端设备的信号强度；
[0298] AP402，用于接收广播探测请求后，从广播探测请求中提取设备标识以及信号强度；并生成初始信息发送给邻居提取设备，其中，初始信息中包括设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；
[0299] 邻居提取设备403，用于接收多个AP发送的初始信息并存储至初始信息集合中；从初始信息集合中提取指定时间段内的设备标识相同的初始信息；针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，在每个AP排序中、信号强度越高对应的AP标识获得的评分越高、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；并，针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的特征向量；根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0300] 实施例四
[0301] 本申请实施例三还提供了一种计算设备，该计算设备具体可以为桌面计算机、便携式计算机、智能手机、平板电脑、个人数字助理(Personal Digital Assistant，PDA)等。如图5所示，该计算设备可以包括中央处理器(Center Processing Unit，CPU)501、存储器
502、输入设备503，输出设备504等，输入设备可以包括键盘、鼠标、触摸屏等，输出设备可以包括显示设备，如液晶显示器(Liquid Crystal Display，LCD)、阴极射线管(Cathode Ray Tube，CRT)等。
[0302] 存储器可以包括只读存储器(ROM)和随机存取存储器(RAM)，并向处理器提供存储器中存储的程序指令和数据。在本申请实施例中，存储器可以用于存储无线访问接入点的邻居提取方法的程序指令。处理器通过调用存储器存储的程序指令，处理器用于按照获得的程序指令执行：接收多个无线访问接入点AP发送的初始信息并存储至初始信息集合中，其中，针对每个AP，该AP的初始信息为该AP根据接收到的广播探测请求生成的；初始信息中包括发送广播探测请求的终端设备的设备标识、终端设备的信号强度、AP标识和AP接收探测请求报文的射频口的射频口标识；从初始信息集合中提取指定时间段内的设备标识相同的初始信息；针对每个设备标识，根据信号强度大小对提取的该设备标识的各初始信息中的AP标识进行排序得到一组AP排序；确定各AP排序中最大信号强度对应的AP标识作为基准AP标识，并获取基准AP标识相同的AP排序构成AP排序集；确定AP排序集中所有AP标识，并针对该AP排序集中的每个AP排序，确定该AP排序中每个AP标识对该AP排序集中所有AP标识的评分得到评分矩阵，其中，在每个AP排序中、信号强度越高对应的AP标识获得的评分越高、且同一AP标识对AP排序集中所有AP标识的评分值之和为1；并，针对评分矩阵中每个元素，根据该元素的预设加权因子，求得该元素在马尔可夫状态转移矩阵中的对应值，得到马尔可夫状态转移矩阵；求解马尔可夫状态转移矩阵的稳态平衡条件，获得用于表示AP之间位置远近关系的特征向量；根据获得的特征向量，确定基准AP标识对应的AP与AP排序集中其它AP标识对应的AP之间的邻居关系。
[0303] 实施例四
[0304] 本申请实施例四提供了一种计算机存储介质，用于储存为上述计算设备所用的计算机程序指令，其包含用于执行上述无线访问接入点的邻居提取方法的程序。
[0305] 所述计算机存储介质可以是计算机能够存取的任何可用介质或数据存储设备，包括但不限于磁性存储器(例如软盘、硬盘、磁带、磁光盘(MO)等)、光学存储器(例如CD、DVD、BD、HVD等)、以及半导体存储器(例如ROM、EPROM、EEPROM、非易失性存储器(NAND FLASH)、固态硬盘(SSD))等。
[0306] 最后应说明的是：以上实施例仅用以说明本申请的技术方案，而非对其限制；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围。
