Beneath the howling clouds of dust, 120,000 men face each other across the dark featureless sand. Thousands of miles from any major civilisation, and under temperatures as high as 50 degrees Celsius, the two armies are preparing for war. On one side, there are over 100,000 heavily armed conscripts, drafted from coastal cities and temperate mountain valleys, waiting behind a huge, fortified, rubble wall. This wall runs for nearly 1500 kilometres, is surrounded by razor wire, minefields and forts and costs nearly $2 million per day to maintain and protect. On the other, there are less than 20,000 lightly armed and highly mobile guerrillas, swarthy desert nomads who have fought their more numerous opponents to a standstill, in a bloody 24 year war.

The stony Hamada desert in south-western Algeria may seem an unlikely setting for the UN's second longest unresolved conflict (and Africa's last decolonial war). There's no running water; sudden rainfall turns the area into a floodbowl, sweeping everything in its path; stinging sandstorms scour the desert floor; and even livestock have a hard time finding sustenance among the few plants hardy enough to grow in the bleak, flat landscape. Yet everything in this arena is touched by war. From hundreds of thousands of refugees, to unacknowledged prisoners, torture, disappearances, and thunderous military parades in the desert heat, war is all around you.

"It was the worst conditions," the figure says, pinching the ridge of his nose with cracked, pitted fingers, and bowing his head for a moment. "We went by feet, without water or cars. I had to leave my mother and brothers in the city behind me. There were people dying all around us, as we were chased by the Moroccans in the north, and the Mauritanians to the south. Many, many of my friends were killed." H mmad Ali is a slight, wiry figure, a tiny part of his angular, leather-like face just visible through his black "chech" (headscarf). Seemingly older than his 41 years, he fled his native LaYounne city in the Western Sahara when Moroccan troops entered the province in 1975. "It was hard," says Ali, picking his brown, tannin-stained teeth with a traditional "meshwar" (cleaning stick). "Too hard. But now we have a strong army," he says, brightening, and pointing out of the Algerian army tent towards the horizon. "We will fight anyone trying to take our land. It is like a mother to us, not for the soldiers who have to be paid to come here."

Like many other Sahawaris - the curious mix of Arab, Berber and black African nomads who are native to this region - Ali has stories of the "martyrs" from his family who have fallen in the struggle against King Hassan II's Morocco. The Moroccans entered the province in 1975, sending 350,000 volunteers bearing the Koran over the border, in what became known as "The Green March".

Hassan's regime was weak, beset by food riots and assassination attempts, and many critics have since argued that the Western Sahara offered him a useful distraction. The nationalist Istiqlal party, which had won Morocco's independence from France, maintained that a 'Greater Morocco' had encompassed parts of Algeria, Mali, Mauritania and the Western Sahara since the 13th century. And when the Green Marchers quickly withdrew, the Moroccan army moved into their place.

The war which followed was vicious and bloody, sending nearly 170,000 refugees across the desert, under aerial bombardment, to refugee camps in Algeria. Four camps were created under the control of the Polisario Front, the Sahawaris' national liberation movement, which had been created two years earlier to overthrow Spanish colonial rule. Algeria effectively ceded control of the region (near the military town of Tindouf) to Polisario, allowing it to be run as a semi-autonomous province. The self-styled Sahawari Arab Democratic Republic (SADR) is now recognised by some 70 regimes, including other famous liberation movements such as the PLO. Those 65,000 or so Sahawaris that remained in the Western Sahara were either bombed, or subject to harsh political repression in the cities and towns.

In fact, the Moroccans had been invited in by Spain, as it lay in the dying throes of the Franco regime (with Franco himself on his deathbed). It handed over the area to Morocco and Mauritania, allowing them to lay their hands on the region's huge phosphate reserves, and the world's richest fishing grounds which lay off its shores - just 100kms from the Canary Islands.

The war was characterised by Polisario's hit-and-run guerrilla t ctics, using highly mobile, heavily armed jeeps. At one time, it was so successful that it mounted attacks on the Mauritanian capital, Nouakchott, leading to the collapse of the government there. However, the main war with Morocco ended in a stalemate, finally grinding to a halt under a UN-brokered ceasefire in 1991.

It had left thousands of dead on both sides, though no-one knows the exact figures. One Sahawari elder told me "ten dead" in his own family, his voice dry with age as he squatted on a large, Persian-style rug, drinking sweet, frothy tea and reminiscing of his own battles with French and Spanish troops earlier in the century. My interpreter, Said Mohammed Salem, a handsome man in his thirties, added that he remembered his old neighbourhood and friends lost, with sadness. "You cannot know, you cannot calculate, unless you have been there," he says.

The war also left some 2,000 Moroccan prisoners in Polisario's hands, plus a huge amount of captured equipment. However, Morocco has constructed several "walls", or berms - made of fortified rubble and minefields, and protected by artillery - around four-fifths of the territory (about twice the size of England) hemming the Sahawaris into their "Liberated Zone". The Wall remains a vast drain on Moroccan resources, costing nearly $2 million per day, although during the earlier part of the war it received substantial military aid from both France and the US.

Under the UN's plan, the two sides were supposed to agree to a referendum on the area's future; simply, did the Sahawaris want to live under Moroccan control or as a separate nation? But the plans have run into trouble time and again, despite two visits from UN General Secretary Kofi Annan, who has staked his personal credibility on solving the problem, and firefighting by his special representative, former US Secretary of State James Baker.

For years the UN operation drifted as both sides stalled, and became a byword for inefficiency to a hostile US Congress, not least because of the escalating $400 million cost of its MINURSO (United Nations Mission for the Referendum in the Western Sahara) peacekeeping force. Even President Clinton has lent his weight to the dispute, writing to a Republican Representative that "recent progress...lends hope that this crucial issue will soon be resolved."

The referendum was eventually supposed to take place last December, but has now been postponed again until this December. Morocco and Polisario have spent months wrangling over exactly how many Sahawaris should be eligible to vote. Morocco has continually argued for extra voters to be added to the last available census figures, taken by the Spanish in 1974 (which said there were 74,000 Sahawaris in the territory). Polisario maintains that the Moroccans have simply been flooding the territory with impoverished Moroccans from further north, using economic incentives, in order to 'spoil' the vote in its favour.

The UN finally finished sifting through 147,000 possible voters last September. Polisario had originally argued that only 85,000 of these were eligible. In fact, it climbed down two months later and allowed the scrutiny of a further 65,000 potential electors - which has left King Hassan's Moroccan government uncomfortably exposed and without further excuse for progress towards the referendum vote.

"Now that we are saying 'yes', the Moroccans have been left without any excuses," a Sahawari official told me. The UN Security Council has now voted to limit its mandate to the end of March only - seen as a sign of international impatience with the Moroccan regime, which many doubt can afford a return to war.

Yet the Sahawaris do not seem intimidated by the possibility of war, nor the superior firepower ranged against them. During 10 days with Polisario, I watched a huge military parade of their captured equipment, including tanks, surface-to-air missiles and several thousand men (including a company of frogmen!). Howitzers sent thunderous streaks of fire arcing across the desert, causing the various dignitaries to wince and cover their ears, and reminding me, incongruously, of Soviet military parades during the 1970s and 80s.

During one siesta, when the desert is too hot even for the Sahawaris, I found myself talking to a young soldier just back from the front line. Sitting in the single room of his family's mud-baked hut, 18-year-old Cheh told me how he was serving in the radio battalion. He was on short term leave and proudly declared, with a wide grin, that he came from LaYounne city - even though, like 60 percent of all Sahawaris, he wouldn't have been born when the Moroccans invaded.

"Life is hard," he says. "But we have enough to eat and drink, praise God." His skin is baked black by the sun, and he lounges on the ornate rugs (which furnish every dwelling), smoking the ubiquitous traditional tobacco pipe. In between listening to a Walkman, he tells me of the five brothers and sisters in his family, and how "life in the desert is tough - tougher than here. But I'm going back to my home soon." How, I casually ask? "In a big truck," he says quite literally, causing myself and Said to crack up with laughter.

But for most Sahawaris, this is not a joke. I met scores of young women training with AK-47 automatic weapons in a military training school. Ostensibly policewomen, the sign above their training ground read "Independence, Independence, Independence - by Peace or Killing." Wearing khaki uniforms, their faces stained blue by the dye in their shortened black "malaafas", which cover their head and shoulders, they told me they remained ready to die for their country. "We want a just referendum," one young woman told me. "If it is free and fair, we will have our country back. If not..." she said, and let the sentence trail off, before returning to stripping down her weapon. It is a sobering thought, even in the dead heat.

Ahmed Fal, commander of the Second Military Region, stationed on the pinkish sand near the Moroccan wall, also told me: "We are a peace-loving people. But when it is a question of dignity and sovereignty and our own land, we have no option. If there is no choice we will go back to war. We are ready."

The Sahawaris are really one of history's forgotten peoples, a sprawling nomadic collection of tribes, formed by waves of conquest and migration across north Africa. Their most direct descendants are believed to be 13th century Arabs from Yemen, who collided and intermarried with Berbers and black Africans. Today the Sahawaris speak one of the purest forms of Arabic, called Hassaniya, and are Sunni muslims, worshipping without mosques. Although originally nomadic, many had settled into cities by the 1960s, making life in the Algerian desert even more difficult.

Any visitor to these fragile-looking settlements cannot help but be impressed by the organisation and achievements which have taken place over the past two decades. Literacy has risen from five to 95 percent; healthcare and education are free to all, with underground hospitals operating right under the Moroccans' noses; many young Sahawaris go on to study at universities in countries such as France, Spain, Libya, Algeria and Cuba; and desert "gardens" help provide essential fruit and vegetables to the refugees' mineral-poor diet.

I am taken on a tour of these projects, rattling across the blackened desert in a seemingly random direction, watching other jeeps criss-cross the roadless expanse in the distance. Occasionally passing a roadblock - when there is a road - manned by young Sahawari conscripts, my first visit is to one of the gardens which have been carved into the inhospitable environment.

The Sahawari in charge, Said Mohammed Galoui, greets me, his taped spectacles perched precariously across his nose. As he proudly shows me around the walled expanse, he points out fig trees, dates, onions, beetroot, carrots and even peppers, which are fed by underground boreholes. There's a chicken shed too, supplying thousands of eggs. The ground is saline and tons of fresh water must be pumped up to constantly wash the sandy soil, some of which itself has to be imported. Moroccan prisoners of war also work the land, although to the casual eye remain almost indistinguishable from the Sahawaris around them. One smiling, portly prisoner tells me he's from Casablanca. I laugh, thinking he's a Sahawari making a joke - but then see he's deadly serious.

Galoui, a tall, sprightly man, remembers working as a farmer under Spanish colonial rule in Western Sahara - and is already making plans to each others his skills upon their return. He admits, though, that the gardens can only provide a fraction, however impressive, of the Sahawaris' nutritional needs. Ninety percent or more still has to come in from outside, the majority of it supplied once a month by the Algerian Red Crescent (Polisario supplements this with distributions of camel meat, and each family also keeps goats and other livestock). Water is scarce, and drilling crews constantly scour the desert for new sources. Malnutrition, particularly among children, remains high. Next we visit a hospital, named after one of the Sahawari fallen, Martyr Harya Haidara. It's barely up to modern western standards, but is still an impressive achievement out here in the middle of this harsh desert. Sand creeps over the concrete floor, and a single wan electric light battles vainly with the shadows which lurk all over, in corners and in the high rafters overhead.

I chat with a tired but pleasant young doctor, a slim, dark-skinned Sahawari who was trained in Cuba (as were many of his contemporaries, women as well as men). He tells me, on a walkabout, that the hospital has 74 beds and three doctors. However, they lack 80 percent of all necessary drugs and equipment, and only outside aid from NGOs keeps them going. He also adds that all instruments have to be sterilised by boiling in water, sometimes bleach. Without X-rays, the doctors can sometimes only guess what is wrong with a patient.

They treat many eye problems, as well as diabetes, heart disease and outbreaks of cholera, he says, which are caused when sewage leaks into and infects boreholes. An older, fatter doctor - Mohammed Salem Deiya - explains that one of their main problems is getting people to trust in modern, not traditional medicine. He says he was an assistant to a Spanish doctor when Spain ruled Western Sahara, and that there was just one pharmaceutical assistant for 30,000 Sahawaris. "At least that has now changed," he says.

During the early years in the camps, life was particularly hard. Since the men were at the front, the burden of running them fell upon women, which has wrought changes on the Muslim society. One visitor at this time wrote: "The depression felt when visiting these camps is as great as the admiration it arouses. It is depressing because of the misery and the malnutrition, which hits the children in particular. There is a lack of essential medicines and medical equipment. Many families have arrived with little more than the clothes on their backs. The enormous variations in temperature between night and day and the sandstorms are gradually eroding whatever the refugees were able to bring."

Now it is the women who run the tents, fetch the water, raise the children and - in many cases - also hold down jobs as nurses, doctors, administrators and teachers. It is they who keep everything s clean, and conserve the scarce resources. For example, a corner of each tent is converted to a wash area, with a pewter-style bowl and kettle. As one member pours the water, another washes, and the water is collected in the bowl and recycled for later use.

During one evening I sit with Fatma, a light-skinned 28-year-old Sahawari woman. Wearing a pink coloured malaafa which she wraps around her head and body, I watch her make tea on a small portable stove. Fatma is typical of the new breed of Sahawari women - highly educated, a director of a school, divorced and free to remarry as she chooses (part of traditional Sahawari heritage, and reason for concern among some other Muslim nations).

"We have one woman on the National Secretariat," she says, pouring the sweet, mint tea high into each glass and allowing it to collect froth, before serving the traditional three rounds. "But that's not enough. Many years ago, before the revolution, the women's job was very limited - just to deal with her family and tent." As one of her small children runs around beside us, and a radio blares out a mixture of static and Arabic pop music, she tells me that the women played an important role when Polisario was launched in 1973. "They were underground Polisario members, working with different groups and making flags. And the Sahawari women took the place of the men in the camps when they went to fight, dealing with administration and at the same time nursing, teaching, playing several roles. As a result, our society has changed completely."

Her comments are echoed by Maryam Hmada, who runs a women-only training college in the camps. Widowed and then divorced, the 32-year-old says: "It's too late to change our role. It's going to be impossible to bring us back to the kitchen."

But it would be a mistake to think that Sahawaris were somehow divided. Everyone in this environment shares hardships together. The 101 member parliament-in-exile, with its various ministries (including 10 tribal elders, the rest elected) and President Mohammed Abdelaziz, all live in tents and - apart from sharing a habit for chain-smoking Marlboro cigarettes - all have also fought in battles together. In fact, Abdelaziz is famous for his exploits on the battlefield. Although he himself admits, at a 'press conference' held for visiting journalists in a Beau-Geste style fort, that Polisario used to be Communist, he also claims that it has never received a Soviet bullet.

"We all have the same will for our revolution and country, to live like all other dignified peoples in the world," says a member of the SADR embassy in Algiers. "There was no other way to an armed struggle," he adds. "We have a proverb here; the sun cannot be covered by a net. You can't cover up what we are. We will build a democratic system when we return to Western Sahara. This is the kind of state we want." It remains to be seen whether the UN will actually withdraw its presence, or whether some form of compromise will be found at the eleventh hour. However, the Sahawaris are certainly pushing for some form of resolution. As their most famous singer, Umm Deleila, said to Mr Annan during his most recent visit: "We have given blood, the dearest thing that every human has - so we are sure that we will receive something in return." This is certainly not the last chapter in this tragic, yet forgotten, conflict.