Achievements in forest tree improvement in Australia and New Zealand 6: Genetic improvement and conservation of Araucaria cunninghamii in Queensland

Araucaria cunninghamii (hoop pine) typically occurs as an emergent tree over subtropical and tropical rainforests, in a discontinuous distribution that extends from West Irian Jaya at about 0°30'S, through the highlands of Indonesian New Guinea and Papua New Guinea, along the east coast of Australia from 11°39'S in Queensland to 30°35'S in northern New South Wales. Plantations established in Queensland since the 1920s now total about 44000 ha, and constitute the primary source for the continuing supply of hoop pine quality timber and pulpwood, with a sustainable harvest exceeding 440 000 m3 y-1. Establishment of these managed plantations allowed logging of all native forests of Araucaria species (hoop pine and bunya pine, A. bidwillii) on state-owned lands to cease in the late 1980s, and the preservation of large areas of araucarian forest types within a system of state-owned and managed reserves. The successful plantation program with this species has been strongly supported by genetic improvement activities since the late 1940s - through knowledge of provenance variation and reproductive biology, the provision of reliable sources of improved seed, and the capture of substantial genetic gains in traits of economic importance (for example growth, stem straightness, internode length and spiral grain). As such, hoop pine is one of the few tropical tree species that, for more than half a century, has been the subject of continuous genetic improvement. The history of commercialisation and genetic improvement of hoop pine provides an excellent example of the dual economic and conservation benefits that may be obtained in tropical tree species through the integration of gene conservation and genetic improvement with commercial plantation development. This paper outlines the natural distribution and reproductive biology of hoop pine, describes the major achievements of the genetic improvement program in Queensland over the past 50+ y, summarises current understanding of the genetic variation and control of key selection traits, and outlines the means by which genetic diversity in the species is being conserved.

Work Stress and Early Atherosclerosis: Do Genetic Background and Pre-Employment Risk Factors Explain Conflicting Findings?

According to the models conceptualizing work stress, increased risk of health problems arise when high job demands co-occur with low job control (the demand-control model) or the efforts invested by the employee are disproportionately high compared to the rewards received (effort-reward imbalance model). This study examined the association between work stress and early atherosclerosis with particular attention to the role of pre-employment risk factors and genetic background in this association. The subjects were young healthy adults aged 24-39 who were participating in the 21-year follow-up of the ongoing prospective "Cardiovascular Risk in Young Finns" study in 2001-2002. Work stress was evaluated with questionnaires on demand-control model and on effort-reward model. Atherosclerosis was assessed with ultrasound of carotid artery intima-media thickness (IMT). In addition, risk for enhanced atherosclerotic process was assessed by measuring with heart rate variability and heart rate. Pre-employment risk factors, measured at age 12 to 18, included such as body mass index, blood lipids, family history of coronary heart disease, and parental socioeconomic position. Variants of the neuregulin-1 were determined using genomic DNA. The results showed that higher work stress was associated with higher IMT in men. This association was not attenuated by traditional risk factors of atherosclerosis and coronary heart disease or by pre-employment risk factors measured in adolescence. Neuregulin-1 gene moderated the association between work stress and IMT in men. A significant association between work stress and IMT was found only for the T/T genotype of the neuregulin-1 gene but not for other genotypes. Among women an association was found between higher work stress and lower heart rate variability, suggesting higher risk for developing atherosclerosis. These associations could not be explained by demographic characteristics or coronary risk factors. The present findings provide evidence for an association between work stress and atherosclerosis in relatively young population. This association seems to be modified by genetic influences but it does not appear to be confounded by pre-employment adolescent risk factors.

Genetic variation and responses in reproductive performance of sows in lines selected for growth rate under restricted feeding

The objective of this study was to examine genetic changes in reproduction traits in sows (total number born (TNB), number born alive (NBA), average piglet birth weight (ABW) and number of piglets weaned (NW), body weight prior to mating (MW), gestation length (GL) and daily food intake during lactation (DFI)) in lines of Large White pigs divergently selected over 4 years for high and low post-weaning growth rate on a restricted ration. Heritabilities and repeatabilities of the reproduction traits were also determined. The analyses were carried out on 913 litter records using average information-restricted maximum likelihood method applied to single trait animal models. Estimates of heritability for most traits were small, except for ABW (0·33) and MW (0·35). Estimates of repeatability were slightly higher than those of heritability for TNB, NBA and NW, but they were almost identical for ABW, MW, GL and DFI. After 4 years of selection, the high growth line sows had significantly heavier body weight prior to mating and produced significantly more piglets born alive with heavier average birth weight than the low line sows. There were, however, no statistical differences between the selected lines in TNB or NW. The lower food intake of high relative to low line sows during lactation was not significant, indicating that daily food intake differences found between grower pigs in the high and low lines (2·71 v. 2·76 kg/day, s.e.d. 0·024) on ad libitum feeding were not fully expressed in lactating sows. It is concluded that selection for growth rate on the restricted ration resulted in beneficial effects on important measures of reproductive performance of the sows.

Genetic erosion and changes in distribution of sorghum (Sorghum bicolor L. (Moench)) landraces in north-eastern Ethiopia

Ethiopia is believed to be the centre of origin and domestication for sorghum, where sorghum remains one of the main staple crops. Loss of biodiversity is occurring at an alarming rate in Ethiopia and crops, including sorghum, have long been recognized as vulnerable to genetic erosion. A major collection of sorghum germplasm was made in 1973 by Gebrekidan and Ejeta from north-eastern Ethiopia. A new collection of landraces was made in 2003, and these were field evaluated at Sirinka in 2004 along with representative samples from the 1973 collection. Farmer surveys and soil and climate surveys were also performed. Preliminary analysis demonstrated that some important landraces have disappeared either locally or regionally in the past 30 years and many other landraces have become marginalized. Landraces which are less preferred in terms of agronomic value and end use, and introductions, have become increasingly important. Late maturing landraces were found to be particularly vulnerable, with a number disappearing altogether. Farmers have become more risk averse, and factors such as declining soil fertility, more frequent drought and unreliable rainfall, and increased pest infestation have contributed to a change in farmer landrace selection. Data are presented on the variability and unique characters of some of the Ethiopian landraces, and implications for conservation are discussed.

Understanding invasion history: genetic structure and diversity of two globally invasive plants and implications for their management

Aim: Resolving the origin of invasive plant species is important for understanding the introduction histories of successful invaders and aiding strategies aimed at their management. This study aimed to infer the number and origin(s) of introduction for the globally invasive species, Macfadyena unguis-cati and Jatropha gossypiifolia using molecular data. Location: Native range: Neotropics; Invaded range: North America, Africa, Europe, Asia, Pacific Islands and Australia. Methods: We used chloroplast microsatellites (cpSSRs) to elucidate the origin(s) of introduced populations and calculated the genetic diversity in native and introduced regions. Results: Strong genetic structure was found within the native range of M. unguis-cati, but no genetic structuring was evident in the native range of J. gossypiifolia. Overall, 27 haplotypes were found in the native range of M. unguis-cati. Only four haplotypes were found in the introduced range, with more than 96% of introduced specimens matching a haplotype from Paraguay. In contrast, 15 haplotypes were found in the introduced range of J. gossypiifolia, with all invasive populations, except New Caledonia, comprising multiple haplotypes. Main conclusions: These data show that two invasive plant species from the same native range have had vastly different introduction histories in their non-native ranges. Invasive populations of M. unguis-cati probably came from a single or few independent introductions, whereas most invasive J. gossypiifolia populations arose from multiple introductions or alternatively from a representative sample of genetic diversity from a panmictic native range. As introduced M. unguis-cati populations are dominated by a single haplotype, locally adapted natural enemies should make the best control agents. However, invasive populations of J. gossypiifolia are genetically diverse and the selection of bio-control agents will be considerably more complex.

Population genetic structure and genetic diversity of three critically endangered Pristis sawfishes in Australian waters.

Northern Australia is considered to be one of the last strongholds for three critically endangered sawfishes, Pristis zijsron, Pristis clavata, and Pristis microdon, making these populations of global significance. Population structure and levels of genetic diversity were assessed for each species across northern Australia using a portion of the mitochondrial control region. Statistically significant genetic structure was detected in all three species, although it was higher in P. microdon (F-ST = 0.811; N = 149) than in either P. clavata (F-ST = 0.419; N = 73) or P. zijsron (F-ST = 0.202; N = 49), possibly due to a much higher and/or localized level of female philopatry in P. microdon. The overall levels of haplotype diversity in P. zijsron (h = 0.555), P. clavata (h = 0.489), and P. microdon (h = 0.650) were moderate, although it appears to be reduced in the assemblages of P. zijsron and P. clavata in the Gulf of Carpentaria (h = 0.342 and h = 0.083, respectively). Since female migration (replenishment) between regions is unlikely, conservation plans should strive to maintain current levels of diversity and abundances in the regional assemblages of each species.

Genetic effects and genetic relationships among shrunken (sh2) sweet corn lines and F1 hybrids

The objectives of this study were to quantify the components of genetic variance and the genetic effects, and to examine the genetic relationship of inbred lines extracted from various shrunken2(sh2) breeding populations. Ten diverse inbred lines developed from genetic background, were crossed in half diallel. Parents and their F1 hybrids were evaluated at three environments. The parents were genotyped using 20 polymorphic simple sequence repeats (SSR). Agronomic and quality traits were analysed by a mixed linear model according to additive-dominance genetic model. Genetic effects were estimated using an adjusted unbiased prediction method. Additive variance was more important than dominance variance in the expression of traits related to ear aspects (husk ratio and percentage of ear filled) and eating quality (flavour and total soluble solids). For agronomic traits, however, dominance variance was more important than additive variance. The additive genetic correlation between flavour and tenderness was strong (r = 0.84, P <0.01). Flavour, tenderness and kernel colour additive genetic effects were not correlated with yield related traits. Genetic distance (GD), estimated from SSR profiles on the basis of Jaccard's similarity coefficient varied from 0.10 to 0.77 with an average of 0.56. Cluster analysis classified parents according to their pedigree relationships. In most studied traits, F1 performance was not associated with GD.

Genetic Diversity and Adaptation of Date Palm (Phoenix dactylifera L.)

Acquiring sufficient information on the genetic variation, genetic differentiation, and the ecological and genetic relationships among individuals and populations are essential for establishing guidelines on conservation and utilization of the genetic resources of a species, and more particularly when biotic and abiotic stresses are considered. The aim of this study was to assess the extent and pattern of genetic variation in date palm (Phoenix dacttylifera L) cultivars; the genetic diversity and structure in its populations occurring over geographical ranges; the variation in economically and botanically important traits of it and the variation in its drought adaptive traits, in conservation and utilization context. In this study, the genetic diversity and relationships among selected cultivars from Sudan and Morocco were assessed using microsatellite markers. Microsatellite markers were also used to investigate the genetic diversity within and among populations collected from different geographic locations in Sudan. In a separate investigation, fruits of cultivars selected from Sudan, involved morphological and chemical characterization, and morphological and DNA polymorphism of the mother trees were also investigated. Morphological and photosynthetic adjustments to water stress were studied in the five most important date palm cultivars in Sudan, namely, Gondaila, Barakawi, Bitamoda, Khateeb and Laggai; and the mechanism enhancing photosynthetic gas exchange in date palm under water stress was also investigated. Results showed a significant (p < 0.001, t-test) differentiation between Sudan and Morocco groups of cultivars. However, the major feature of all tested cultivars was the complete lack of clustering and the absence of cultivars representing specific clones. The results indicated high genetic as well as compositional and morphological diversity among cultivars; while, compositional and morphological traits were found to be characteristic features that strongly differentiate cultivars as well as phenotypes. High genetic diversity was observed also in different populations. Slight but significant (p < 0.01, AMOVA) divergence was observed for soft and dry types; however, the genetic divergence among populations was relatively weak. The results showed a complex genetic relationships between some of the tested populations especially when isolation by distance was considered. The results of the study also revealed that date palm cultivars and phenotypes possess specific direct or interaction effects due to water availability on a range of morphological and physiological traits. Soft and dry phenotypes responded differently to different levels of water stress, while the dry phenotype was more sensitive and conservative. The results indicated that date palm has high fixation capacity to photosynthetic CO2 supply with interaction effect to water availability, which can be considered as advantageous when coping with stresses that may arise with climate change. In conclusion, although a large amount of diversity exists among date palm germplasm, the findings in this study show that the role of biological nature of the tree, isolation by distance and environmental effects on structuring date palm genome was highly influenced by human impacts. Identity of date palm cultivars as developed and manipulated by date palm growers, in the absence of scientific breeding programmes, may continue to mainly depend on tree morphology and fruit characters. The pattern of genetic differentiation may cover specific morphological and physiological traits that contribute to adaptive mechanisms in each phenotype. These traits can be considered for further studies related to drought adaptation in date palm.

Genetic diversity and microcystin production by Anabaena in the Gulf of Finland, Baltic Sea

Syanobakteerit (sinilevät) ovat olleet Itämeressä koko nykymuotoisen Itämeren ajan, sillä paleolimnologiset todisteet niiden olemassaolosta Itämeren alueella ovat noin 7000 vuoden takaa. Syanobakteerien massaesiintymät eli kukinnat ovat kuitenkin sekä levinneet laajemmille alueille että tulleet voimakkaimmiksi viimeisten vuosikymmenien aikana. Tähän on osasyynä ihmisten aiheuttama kuormitus, joka rehevöittää Itämerta. Suomenlahti, jota tämä tutkimus käsittelee, on kärsinyt tästä rehevöitymiskehityksestä muita Itämeren altaita enemmän. Syanobakteerit muodostavat jokakesäisiä kukintoja Suomenlahdella - niin sen avomerialueilla kuin rannoillakin. Yleisimmät kukintoja muodostavat syanobakteerisuvut ovat Nodularia, Anabaena ja Aphanizomenon. Kukinnat aiheuttavat paitsi esteettistä haittaa myös terveydellisen riskitekijän. Niiden myrkyllisyys liitetään usein Nodularia-suvun tuottamaan nodulariini-maksamyrkkyyn. Itämeren Aphanizomenon-suvun on todettu olevan myrkytön. Vaikka Itämeren kukintoja aiheuttavista Nodularia- ja Aphanizomenon-syanobakteereista tiedetään varsin paljon, on molekyylimenetelmiin pohjautuva syanobakteeritutkimus ohittanut Itämeren Anabaena-suvun monelta osin. Tämän työn tarkoituksena oli syventää käsitystämme Itämeren Anabaena-syanobakteerista, sen mahdollisesta myrkyllisyydestä, geneettisestä monimuotoisuudesta ja fylogeneettisista sukulaisuussuhteista. Tässä työssä eristettiin 49 planktista Anabaena-kantaa, joista viisi tuottivat mikrokystiinejä. Tämä oli ensimmäinen yksiselitteinen todiste, että Itämeren Anabaena tuottaa maksamyrkyllisiä mikrokystiini-yhdisteitä. Jokainen eristetty myrkyllinen Anabaena-kanta tuotti useita mikrokystiini-variantteja. Lisäksi mikrokystiinejä löydettiin kukintanäytteistä, joissa oli myrkkyä syntetisoivia geenejä sisältäneitä Anabaena-syanobakteereita. Myrkkyjä löydettiin molempina tutkimusvuosina 2003 ja 2004. Myrkkyjen esiintyminen ei siten ollut vain yksittäinen ilmiö. Tässä työssä saimme viitteitä siitä, että maksamyrkyllinen Anabaena-syanobakteeri esiintyisi vähäsuolaisissa vesissä. Tämä riippuvuussuhde jää kuitenkin tulevien tutkimuksien selvitettäväksi. Tässä työssä havaittiin mikrokystiinisyntetaasi-geenien inaktivoituminen Itämeren Anabaena-kannassa ja kukintanäytteissä. Kuvasimme Anabaena-kannan mikrokystiinisyntetaasigeenien sisältä insertioita, jotka hyvin todennäköisesti inaktivoivat myrkyntuoton. Insertion sisältäneeltä kannalta löysimme kuitenkin kaikki mikrokystiinisyntetaasigeenit osoittaen, että geenien olemassaolo ei välttämättä varmista kannan mikrokystiinintuottoa. Mielenkiintoista oli se, että inaktivaation aiheuttavia insertioita löytyi kukintanäytteistä molemmilta tutkimusvuosilta. Vastaavia insertioita ei kuitenkaan löydetty makean veden Anabaena-kannoista tai järvinäytteistä. On yleistä, että syanobakteerikukinnoista löytyy usean syanobakteerisuvun edustajia. Myrkyllisiä sukuja tai lajeja ei voida kuitenkaan erottaa mikroskooppisesti myrkyttömistä. Käsillä olevassa tutkimuksessa kehitettiin molekyylimenetelmä, jolla on mahdollista määrittää kukinnan mahdollisesti maksamyrkylliset syanobakteerisuvut. Tätä menetelmää sovellettiin Itämeren kukintojen tutkimiseen. Itämeren pintavesistä ja ranta-alueiden pohjasta eristetyt Anabaena-kannat osoittautuivat geneettisesti monimuotoisiksi. Tämä Anabaena-syanobakteerien geneettinen monimuotoisuus vahvistettiin monistamalla geenejä suoraan kukintanäytteistä ilman kantojen eristystä. Makeiden vesien ja Itämeren Anabaena-kannat ovat geneettisesti hyvin samankaltaisia. Geneettisissä vertailuissa kävi kuitenkin ilmi, että pohjassa elävien Anabaena-kantojen geneettinen monimuotoisuus oli suurempaa kuin pintavesistä eristettyjen kantojen. Itämeren Anabaena-kantojen sekvenssit muodostivat omia ryhmiä sukupuun sisällä, jolloin on mahdollista, että nämä edustavat Itämeren omia Anabaena-ekotyyppejä. Tämä tutkimus oli ensimmäinen, jossa uusin molekyylimenetelmin systemaattisesti selvitettiin Itämeren Anabaena-syanobakteerin geneettistä populaatiorakennetta, fylogeniaa ja myrkyntuottoa. Tulevaisuudessa monitorointitutkimuksissa on otettava huomioon myös Itämeren Anabaena-syanobakteerin mahdollinen maksamyrkyntuotto – erityisesti vähäsuolaisemmilla rannikkovesillä.

Combining ability, genetic diversity and heterosis in relation to F1 performance of tropically adapted shrunken (sh2) sweet corn lines

With 6 tables Abstract The objectives of this study were to evaluate the importance of heterosis for agronomic and quality traits in shrunken (sh2) sweet corn, assess the usefulness of combining ability to predict the value of parents and their crosses for further genetic improvement and examine whether genetic divergence can predict heterosis or F1 performance. Ten genetically diverse shrunken (sh2) sweet corn inbred lines were used to generate 45 F1s. F1s and parents were evaluated for agronomic and quality traits across environments. Heterosis was more important for yield-related traits than it was for ear aspects and eating quality. Heterosis for most traits was mostly dependent on dominance genetic effects of parental lines. Parents and F1per se performance were highly correlated with general combining ability effects and mid-parent values, respectively, for most traits. Hybrid performance for flavour and plant height was significantly but weakly related to simple sequence repeat (SSR)-based genetic distance (GD). Phenotypic distance (PD), estimated from phenotypic traits was correlated with heterosis for total soluble solids, ear length and flavour. © 2012 State of Queensland.

The study of genetic diversity and population structure of the Korean fleshy shrimp, Fenneropenaeus chinensis, using newly developed microsatellite markers

The fleshy shrimp, Fenneropenaeus chinensis, is the family of Penaeidae and one of the most economically important marine culture species in Korea. However, its genetic characteristics have never been studied. In this study, a total of 240 wild F. chinensis individuals were collected from four locations as follows: Narodo (NRD, n = 60), Beopseongpo (BSP, n = 60), Chaesukpo (CSP, n = 60), and Cheonsuman (CSM, n = 60). Genetic variability and the relationships among four wild F. chinensis populations were analyzed using 13 newly developed microsatellite loci. Relatively high levels of genetic variability (mean allelic richness = 16.87; mean heterozygosity = 0.845) were found among localities. Among the 52 population loci, 13 showed significant deviation from the Hardy–Weinberg equilibrium. Neighbor-joining, principal coordinate, and molecular variance analyses revealed the presence of three subpopulations (NRD, CSM, BSP and CSP), which was consistent with clustering based on genetic distance. The mean observed heterozygosity values of the NRD, CSM, BSP, and CSP populations were 0.724, 0.821, 0.814, and 0.785 over all loci, respectively. These genetic variability and differentiation results of the four wild populations can be applied for future genetic improvement using selective breeding and to design suitable management guidelines for Korean F. chinensis culture.

Genetic diversity and epidemiology of Tobacco streak virus and related subgroup 1 Ilarviruses

A quarter of Australia’s sunflower production is from the central highlands region of Queensland and is currently worth six million dollars ($AUD) annually. From the early 2000s a severe necrosis disorder of unknown aetiology was affecting large areas of sunflower crops in central Queensland, leading to annual losses of up to 20%. Other crops such as mung bean and cotton were also affected. This PhD study was undertaken to determine if the causal agent of the necrosis disorder was of viral origin and, if so, to characterise its genetic diversity, biology and disease cycle, and to develop effective control strategies. The research described in this thesis identified Tobacco streak virus (TSV; genus Ilarvirus, family Bromoviridae) as the causal agent of the previously unidentified necrosis disorder of sunflower in central Queensland. TSV was also the cause of commonly found diseases in a range of other crops in the same region including cotton, chickpea and mung bean. This was the first report from Australia of natural field infections of TSV from these four crops. TSV strains have previously been reported from other regions of Australia in several hosts based on serological and host range studies. In order to determine the relatedness of previously reported TSV strains with TSV from central Queensland, we characterised the genetic diversity of the known TSV strains from Australia. We identified two genetically distinct TSV strains from central Queensland and named them based on their major alternative hosts, TSV-parthenium from Parthenium hysterophorus and TSV-crownbeard from Verbesina encelioides. They share only 81 % total-genome nucleotide sequence identity. In addition to TSV-parthenium and TSV-crownbeard from central Queensland, we also described the complete genomes of two other ilarvirus species. This proved that previously reported TSV strains, TSV-S isolated from strawberry and TSV-Ag from Ageratum houstonianum, were actually the first record of Strawberry necrotic shock virus from Australia, and a new subgroup 1 ilarvirus, Ageratum latent virus. Our results confirmed that the TSV strains found in central Queensland were not related to previously described strains from Australia and may represent new incursions. This is the first report of the genetic diversity within subgroup 1 ilarviruses from Australia. Based on field observations we hypothesised that parthenium and crownbeard were acting as symptomless hosts of TSV-parthenium and TSV-crownbeard, respectively. We developed strain-specific multiplex PCRs for the three RNA segments to accurately characterise the range of naturally infected hosts across central Queensland. Results described in this thesis show compelling evidence that parthenium and crownbeard are the major (symptomless) alternative hosts of TSV-parthenium and TSV-crownbeard. While both TSV strains had wide natural host ranges, the geographical distribution of each strain was closely associated with the respective distribution of their major alternative hosts. Both TSV strains were commonly found across large areas of central Queensland, but we only found strong evidence for the TSV-parthenium strain being associated with major disease outbreaks in nearby crops. The findings from this study demonstrate that both TSV-parthenium and TSV-crownbeard have similar life cycles but some critical differences. We found both TSV strains to be highly seed transmitted from their respective major alternative hosts from naturally infected mother plants and survived in seed for more than 2 years. We conclusively demonstrated that both TSV strains were readily transmitted via virus-infected pollen taken from the major alternative hosts. This transmission was facilitated by the most commonly collected thrips species, Frankliniella schultzei and Microcephalothrips abdominalis. These results illustrate the importance of seed transmission and efficient thrips vector species for the effective survival of these TSV strains in an often harsh environment and enables the rapid development of TSV disease epidemics in surrounding crops. Results from field surveys and inoculation tests indicate that parthenium is a poor host of TSV-crownbeard. By contrast, crownbeard was naturally infected by, and an experimental host of TSV-parthenium. However, this infection combination resulted in non-viable crownbeard seed. These differences appear to be an effective biological barrier that largely restricts these two TSV strains to their respective major alternative hosts. Based on our field observations we hypothesised that there were differences in relative tolerance to TSV infection between different sunflower hybrids and that seasonal variation in disease levels was related to rainfall in the critical early crop stage. Results from our field trials conducted over multiple years conclusively demonstrated significant differences in tolerance to natural infections of TSV-parthenium in a wide range of sunflower hybrids. Glasshouse tests indicate the resistance to TSV-parthenium identified in the sunflower hybrids is also likely to be effective against TSV-crownbeard. We found a significant negative association between TSV disease incidence in sunflowers and accumulated rainfall in the months of March and April with increasing rainfall resulting in reduced levels of disease. Our results indicate that the use of tolerant sunflower germplasm will be a critical strategy to minimise the risk of TSV epidemics in sunflower.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.