Projects
Radio Frequency Assignment and Coding Theory Research Page
This page contains pdf files of project reports on Radio Frequency Assignment which have been supervised or jointly supervised by Derek Smith. Each file is accompanied by a brief commentary and a list of relevant publications. It also contains information on work on Coding Theory supervised by Derek Smith and Stephanie Perkins. Tables of new constant weight codes constructed by Roberto Montemanni of IDSIA and Derek Smith are included in section L. Additionally, files of codewords of new DNA codes constructed by Roberto Montemanni of IDSIA, Derek Smith, Niema Aboluion and Stephanie Perkins are included in section M.
A. FASoft
This is the final report of a project funded by the UK Radiocommunications Agency in 1995–1997. This project developed the package FASoft. FASoft solves both minimum span and fixed spectrum problems by a variety of algorithms. FASoft contains the first algorithms which were able to solve to optimality the main (hard) variations of the Philadelphia problems. This set of benchmark problems had remained unsolved since 1973. FASoft cannot handle individually weighted constraints or the equality constraints found in CELAR problems. Its data structures can also be improved. Although we now have better software for fixed spectrum problems, it remains probably the most powerful system available for solving minimum span problems.
Related publications:
(1) S. Hurley, D.H. Smith and S.U. Thiel. FASoft: A System for Discrete Channel Frequency Assignment, Radio Science, Vol.32 No. 5, pp 1921–1939, September/October 1997.
(Describes the metaheuristic algorithms in FASoft)
(2) D.H. Smith, S. Hurley and S.U. Thiel. Improving Heuristics for the Frequency Assignment Problem, European Journal of Operations Research, vol. 107/1, pp76–86, 1998.
(Describes the use of subgraphs and the first complete solution of the Philadelphia problems)
(3) S. Hurley, S.U. Thiel and D.H. Smith. A Comparison of Local Search Algorithms for Radio Link Frequency Assignment Problems, 11th Annual ACM Symposium on Applied Computing, pp251–257, Philadelphia, USA, Feb. 1996.
(4) S. Hurley and D.H. Smith. Fixed Spectrum Frequency Assignment using Natural Algorithms, Proceedings IEE/IEEE Int. Conf. on Genetic Algorithms in Engineering Systems (GALESIA ‘95), pp 373–378, Sheffield, U.K., Sept. 1995.
(5) B.E. Turhan, S. Hurley, J.D. Last and D.H. Smith,
Algorithms for Interference Limited Radiobeacon Frequency Assigment,
Proceedings of Second International Conference on Information, Communications and Signal Processing (ICICS’99), 7–10 Dec 1999, Singapore, 2A1.5, 1–5
(6) D.H. Smith, S.M. Allen. S. Hurley, W.J. Watkins, Frequency Assignment: Methods and Algorithms, NATO RTA SET/ISET Symposium on Frequency Assignment, Sharing and Conservation in Systems (Aerospace), Aalborg, Denmark, October 1998, NATO RTO-MP-13, January 1999.
(re-published in “Global Communications”.)
A survey of algorithms, lower bounds for the span and multiple interference
(7) S.M. Allen, S. Hurley, D.H. Smith and W.J. Watkins, Solving Frequency Assignment Problems, Fourteenth International Wroclaw Symposium and Exhibition on Electromagnetic Compatibility, pp703–705, June 23–25 1998.
(8) S. Hurley, D.H. Smith and C. Valenzuela, A Permutation Based Genetic Algorithm for Minimum Span Frequency Assignment, Proceedings 5th International Conference on Problem Solving from Nature, Lecture Notes in Computer Science 1498 (ed. A.E. Eiben, T. Bäck, M. Schoenauer and H.-P. Schwefel, Springer Verlag, pp907–916, 1998.
B. Lower Bounds for the Span
. ... Fap2last.pdf…> 810KB
.. ... hs report with manual.pdf… 349KB
These two reports describe particularly successful methods of determining lower bounds for the span. The first report describes benchmark generation and the mathematical programming methods used. The second report embeds the mathematical programming in a heuristic for determining the best subgraph to use.
Related publications
(9) S.M. Allen, D.H. Smith and S. Hurley, Lower Bounding Techniques for Frequency Assignment, Discrete Mathematics, Vol. 197–198, pp 41–52, February 1999
Describes the mathematical programming techniques for general minimum span problems.
(10) S.M. Allen, S. Hurley, D.H. Smith and S.U. Thiel. Using Lower Bounds in Minimum Span Frequency Assignment, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (ed. A. Voss, S. Martello, I.H. Osman and C. Roucairol), Kluwer, 1999 pp191–204.
(11) D.H. Smith, S. Hurley and S.M. Allen .A New Lower Bound for the Frequency Assignment Problem, IEEE Transactions on Vehicular Technology, Vol. 49, No. 4, July 2000, pp1265–1272.A New Lower Bound
Adapts and simplifies the mathematical programming techniques for cellular minimum span problems.
(12) S. Hurley and D.H. Smith. Bounds for the Frequency Assignment Problem, Discrete Mathematics, Vol 167/168, pp 571–582, 1997.
A theoretical description of some earlier bounds.
C. Non-binary constraints
. .. final.pdf .. 895 KB
.. ... final_temp.pdf .. 690 KB
These reports describe the development of algorithms which can handle non-binary constraints (involving >2 transmitters) for multiple interference. The second report also describes a related problem in private business radio using channel loading constraints.
Related publications
(13) S. Hurley, R. M. Whitaker and D.H. Smith, Analysing Multiple Interference in Radio Networks, 9th International Conference on Telecommunications Systems, Modelling and Analysis, March 15–18, 2001, Dallas, Texas, U.S.A., pp623–628.
Concentrates on co-channel non-binary constraints.
(14) S.Hurley, R.M. Whitaker and D.H. Smith, Channel Assignment in Cellular Networks without Channel Separation Constraints, Proceedings of IEEE Vehicular Technology Conference Fall 2000, pp1714–1718.
Demonstrates the feasibility of a constraint free approach.
D. No report is available
A project with DERA Malvern and BAE SYSTEMS has demonstrated that it is possible to handle intermodulation product constraints for co-sited transmitters, spurious emission and response constraints for co-sited transmitters as well as the traditional frequency separation constraints for co-sited and far sited transmitters. Algorithms have been implemented and proved very effective. No report is available for general circulation, but the work is described in the following related publication.
Related publications
(15) D.H. Smith, R.K. Taplin and S. Hurley, Frequency Assignment with Complex Co-Site Constraints, IEEE Transaction on Electromagnetic Compatibility,Vol. 43, No. 2, , pp210–218, May 2001.Complex Co-Site
E. No report is available
Coding theory is used in CDMA and Frequency Hopping. The first of the following papers gives a short general account of some applications. The second is a preliminary consideration of the application of frequency assignment techniques in spreading code assignment in CDMA systems. A much more fully developed application of this idea has been submitted for publication.
Related publications
(16) D.H. Smith and S. Perkins, Applications of Coding Theory in Mobile Radio Communications, Mathematics Today, Vol. 37, No. 3, pp84–87, June 2001.
(17) R.A. Jones, D.H. Smith and S. Perkins, Assignment of spreading codes in DS-CDMA UWB systems, Proceedings of IEEE Conference on Ultra Wideband Systems and Technologies, Reston, Virginia, C4, November 2003. (ISBN 0–7803–8818–2)
F. No report is available
The following very early paper describes an attempt to improve an exact algorithm. It now looks very impractical for the size of problem that is typical today.
Related publications
(18) D.H. Smith, Graph Colouring and Frequency Assignment, Proceedings of the Eleventh British Combinatorial Conference, Ars Combinatoria, 25-C, pp205–212, 1988.
G. Roberto Montemanni’s thesis and related technical report UG-M-01_1
Montemanni_thesis_diseminate.pdf 897KB
UB.pdf 211 KB
This thesis describes a technique (based on linear programming) for determining a (usually good) lower bound for the cost in a fixed spectrum frequency assignment problem. Efficient implementations of an improved tabu search algorithm and a simulated annealing algorithm for (weighted and unweighted) fixed spectrum problems are also described. The technical report describes the Tabu search algorithm only.
Related Publications
(19) R. Montemanni, D.H. Smith and S.M. Allen, Lower Bounds for Fixed Spectrum Frequency Assignment, Annals of Operations Research, 107, October 2001, pp 237–250, (ISSN 0254–5330).
(20) R. Montemanni, D.H. Smith and S.M. Allen, An ANTS algorithm for the minimum-span frequency-assignment problem with multiple interference, IEEE Transaction on Vehicular Technology, Vol. 51, No. 5, Sept 2002, pp949–953. (ISSN 0018–9545).An ANTS algorithm
(21) R. Montemanni, D.H. Smith and S.M. Allen, An Improved Algorithm to Determine Lower Bounds for the Fixed Spectrum Frequency Assignment Problem, European Journal of Operational Research, 156, August 2004, pp 736–751, (ISSN: 0377–2217).
(22) D.H. Smith, L.A. Hughes, J.N.J. Moon and R. Montemanni, Measuring the Effectiveness of Frequency Assignment Algorithms, IEEE Transaction on Vehicular Technology, Vol. 56, No. 1, (Jan. 2007), pp. 331–341. (ISSN 0018–9545). Measuring the Effectiveness of Frequency Assignment Algorithms
H. No report is available
The following paper describes a very effective tabu search algorithm with a dynamic tabu list and exact cell optimisation for the weighted fixed spectrum frequency assignment problem. The algorithm generated up to five best results for the COST 259 benchmarks, two of which remain the best known assignments.
Related publications
(23) R. Montemanni, J.N.J. Moon and D.H. Smith, An improved tabu search algorithm for the fixed spectrum frequency assignment problem, IEEE Transactions on Vehicular Technology, Vol. 52, No. 4, July 2003, pp891–901. (ISSN 0018–9545).An improved tabu search algorithm
J. Constructions of Frequency Hopping Lists Using Constant Weight Codes
This report considers a number of techniques for constructing frequency hopping lists from constant weight codes. The emphasis is on uniform constructions that can easily be applied in an Engineering environment to construct good hopping lists, rather than on consistently finding the best code possible. However, the report contains some larger codes than previously known, and in particular, extends the tables of known constant weight codes up to length 63. Some results of theoretical interest are also included
Related Publications
(24) J.N.J. Moon, L.A. Hughes and D.H. Smith, Assignment of Frequency Lists in Frequency Hopping Networks, IEEE Transactions on Vehicular Technology, Vol. 54, No. 3, May 2005, pp. 1147–1159.
(ISSN 0018–9545). Assignment of Frequency Lists
(25) D.H. Smith, L.A. Hughes and S. Perkins, A New Table of Constant Weight Codes of Length Greater than 28, The Electronic Journal of Combinatorics, Vol. 13, No. 1, (May 2006), #A2.
(ISSN: 1077–8926).
A New Table of Constant Weight Codes
K. Definition of a Common Formulation of Military Frequency Assignment Problems and the Application of Meta-Heuristic Algorithms
This thesis attempted to create a common formulation for a number of different frequency assignment problems. It also showed how a preliminary use of binary constraints can help to obtain good frequency assignments by SIR methods. This work will appear in the journal Wireless Networks.
L. Research on Constant Weight Codes
Work on constructing constant weight codes has been noted in J above. The results were reported in
(25) D.H. Smith, L.A. Hughes and S. Perkins, A New Table of Constant Weight Codes of Length Greater than 28, The Electronic Journal of Combinatorics, Vol. 13, No. 1, (May 2006), #A2.
(ISSN: 1077–8926).
A New Table of Constant Weight Codes
A table of updated lower and upper bounds for the parameters considered in the above paper can be found at: Updated table Recently Montemanni at IDSIA and Smith at Glamorgan have collaborated to develop new algorithmic approaches for finding good constant weight codes. Many improved codes have been found for cases with 29<=n<=63, 5<=w<=8, 6<=d<=14 with d=2w-2, d=2w-4 and d=2w-6. Ten new optimal codes are included. Files of codewords can be found in the zip archive: new_constant_weight_codes.zip
Note that two slightly different formats are in use.
This work has appeared in:
R. Montemanni and D.H. Smith, Heuristic Algorithms for Constructing Binary Constant Weight Codes,
IEEE Transactions on Information Theory, 55(10):4651–4656, 2009
M. Research on DNA Codes
Montemanni at IDSIA and Smith at Glamorgan have collaborated to develop new algorithmic approaches for finding good DNA codes. DNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes.
The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. Many improved codes have been found. Files of codewords can be found in the zip archive:
new_DNA_codes.zip
Results are reported in the paper:
R. Montemanni and D.H. Smith, Construction of constant GC-content DNA codes via a variable neighbourhood search algorithm, J. Math. Modelling and Algorithms, Vol. 7 (2008) pp. 311–326:
(ISSN: 1570–1166) doi 10.1007/s10852–008-9087–8
Further improvements to these codes were found in 2009. The results were also extended to include lengths n with 21<=n<=30. Files of codewords for these improved and extended codes can be found in DNA09.zip
Further complementary improvements (in the case of Hamming distance constraint and constant GC-content constraint only) were made using algebraic methods implemented in Magma (also in 2009). These results are presented in the paper:
“Linear and nonlinear constructions of DNA codes with constant GC-content” by
Derek H. Smith, Niema Aboluion, Roberto Montemanni and Stephanie Perkins”. The files of codewords
for the cases where these methods match or improve the known best results can be found in the zip archive:
DNA09a.zip
N. Research on Variable Length Codes
Variable length codes offer advantages for data compression, but are susceptible to loss of synchronization if a bit error occurs. Research at Glamorgan has concentrated on adding specific mechanisms for resynchronization. Such mechanisms exist in the codes known as Huffman Equivalent (HE) codes and T-codes, which have been extensively studied in the literature. However, HE-codes and T-codes do not exist for all length vectors. A new class of variable length codes referred to as ordered termination (OT) codes, exist for all length vectors. Experimental results and some theoretical support suggest that OT-codes compare favourably with HE- and T-codes. The work has been published in:
M.B.J. Higgs, S. Perkins, D.H. Smith, The construction of variable length codes with good synchronization properties, IEEE Transactions on Information Theory, Vol. 55, No. 4, (April 2009), pp. 1696–1700 (ISSN: 0018–9448)
doi: 10.1109/TIT.2009.2013050
Fuller information can be found in Matthew Higgs thesis:
Matthew Higgs thesis
