求[最优解分配算法]

A0110A

现有若干AP,由若干频道分配，AP间的模拟量距离可以获得，AP距离和频道间隔是AP之间互相干扰的两个参数。现在有没有什么算法可以获得各AP的频道分配最优解，即一个AP用一个频道，使它们之间干扰最小。
我现在只知道可能需要用图来解，其他的比较乱，想不出什么算法。请各位帮忙想想，或者已经知道算法的帮忙提一下。在此谢谢！

mep

似乎是线性或非线性整数规划规划问题
可以给出干扰的计算公式吗?

A0110A

可以先假设
干扰=距离+频道差。
但当频道差大于三可以认为没有干扰。
如11个频道，可以取3，6，9就没有干扰。

mep

这样的啊。。。
岂不是距离越远干扰越大了。。。
另外，使干扰最小是什么意思？是指指定的两个AP之间？还是总的干扰？
可不可以给出更精确的描述

A0110A

不好意思说错了。
干扰是有距离和频道差两个因素影响，
第一距离如果大于某个数就算频道相同也没有干扰，距离如3以上就认为没有干扰，
或者如果频道相差4或以上不管距离多少也认为没有干扰，
干扰= 1/距离+1/频道差；

干扰最小是指总的AP干扰最小。

mep

按照一般的整数规划思路：
有N个AP；N个频道。我们引入M*N个变量x（i，j），0<=i<M，0<=j<N。
每个变量的可能取值为0或1，0表示频道j被分配到i上。
写出所有的约束：
每个AP只能分配一个频道：
即对于给定的i，有x（i，0）+x（i，1）+...+x（i，N）=1
将总的干扰用x（i，j）的表达式表示出来。要求满足约束关系的
干扰的最小值，这应该是个非线性0-1整数规划问题。
从网上找个软件包来求解这个规划问题。

A0110A

万分感谢mep 提供的思路，
我来想想。

JohnBull

楼主是搞蜂窝网的吧?
我觉得这个问题被楼主简化过头了,你等于假定所有的AP都是等功率发射.
实际上交调干扰于功率关系很大,应该把每个AP抽象为由一对坐标/一个频点和一个发射功率值组成的结构体.
根据空气的介电常数求出接收功率与距离的关系(如果我没记错的话,应该是与距离的平方成反比),再据此求出两个频点之间的交调干扰值.

只有这样才能解决不同基站发射功率不同的情况.

A0110A

原帖由 "JohnBull" 发表：
楼主是搞蜂窝网的吧?
我觉得这个问题被楼主简化过头了,你等于假定所有的AP都是等功率发射.
实际上交调干扰于功率关系很大,应该把每个AP抽象为由一对坐标/一个频点和一个发射功率值组成的结构体.
根据空气的介电常..........

最近两天一直很忙，一直没有上来看这个。

说的差不多，我只是想把复杂的简单一下，只和算法有关，让大家都可以想想算法，我到现在还没想出来。
上面mep提出的整数规划思路我还是难以运用到这个上面，
不知道谁有点子？
谢谢！